二叉树的基本操作代码

二叉树的创建和遍历代码

#include\"stdio.h\"

#include\"string.h\"

#include \"stdlib.h\"

#define Max 20 /*结点的最大个数*/

typedef struct node{

char data;

struct node *lchild,*rchild;

}BinTNode; /*自定义二叉树的结点类型*/

typedef BinTNode *BinTree; /*定义二叉树的指针*/

int NodeNum,leaf; /*NodeNum为结点数，leaf为叶子数*/

/*基于先序遍历算法创建二叉树*/

/*要求输入先序序列，其中加入虚结点\"@\"以示空指针的位置*/

BinTree CreatBinTree(void)

{

BinTree T;

char ch;

if((ch=getchar())=='@')

return(NULL); /*读入@，返回空指针*/

else{

T=(BinTNode *)malloc(sizeof(BinTNode)); /*生成结点*/

T->data=ch;

T->lchild=CreatBinTree(); /*构造左子树*/

T->rchild=CreatBinTree(); /*构造右子树*/

return(T);

}

}

/*DLR 先序遍历*/

void Preorder(BinTree T)

{

if(T) {

printf(\"%c\访问结点*/

Preorder(T->lchild); /*先序遍历左子树*/

Preorder(T->rchild); /*先序遍历右子树*/

}

}

/*LDR 中序遍历*/

void Inorder(BinTree T)

{

if(T) {

Inorder(T->lchild); /*中序遍历左子树*/

printf(\"%c\访问结点*/

Inorder(T->rchild); /*中序遍历右子树*/

}

}

/*LRD 后序遍历*/

void Postorder(BinTree T)

{

if(T) {

Postorder(T->lchild); /*后序遍历左子树*/

Postorder(T->rchild); /*后序遍历右子树*/

printf(\"%c\访问结点*/

}

}/*采用后序遍历求二叉树的深度、结点数及叶子数的递归算法*/

int TreeDepth(BinTree T)

{

int hl,hr,max;

if(T){

hl=TreeDepth(T->lchild); /*求左深度*/

hr=TreeDepth(T->rchild); /*求右深度*/

max=hl>hr? hl:hr; /*取左右深度的最大值*/

NodeNum=NodeNum+1; /*求结点数*/

if(hl==0&&hr==0) leaf=leaf+1; /*若左右深度为0，即为叶子。*/

return(max+1);

}

else return(0);

}/*利用\"先进先出\"（FIFO）队列，按层次遍历二叉树*/

void Levelorder(BinTree T)

{

int front=0,rear=1;

BinTNode *cq[Max],*p; /*定义结点的指针数组cq*/

cq[1]=T; /*根入队*/

while(front!=rear)

{

front=(front+1)%NodeNum;

p=cq[front]; /*出队*/

printf(\"%c\出队，输出结点的值*/

if(p->lchild!=NULL){

rear=(rear+1)%NodeNum;

cq[rear]=p->lchild; /*左子树入队*/

}

if(p->rchild!=NULL){

rear=(rear+1)%NodeNum;

cq[rear]=p->rchild; /*右子树入队*/

}

}

}

void main()

{

BinTree root;

int i,depth;

printf(\"\\n\");

printf(\"input yuan su:\"); /*输入完全二叉树的先序序列，*/

/*用@代表虚结点，如ABD@@@CE@@F@@@*/

root=CreatBinTree(); /*创建二叉树，返回根结点*/

do { /*从菜单中选择遍历方式，输入序号。*/

printf(\"\********** select ************\\n\");

printf(\"\1: 先序遍历\\n\");

printf(\"\2: 中序遍历\\n\");

printf(\"\3: 后序遍历\\n\");

printf(\"\4: 求深度\\n\");

printf(\"\5: 层次遍历\\n\"); /*按层次遍历之前，先选择4，求出该树的结点数。*/

printf(\"\0: exit\\n\");

printf(\"\*******************************\\n\");

scanf(\"%d\输入菜单序号（0-5）*/

switch (i){

case 1: printf(\" 先序 : \");

Preorder(root); /*break;

case 2: printf(\" 中序 : \");

Inorder(root); /*break;

case 3: printf(\" 后序 : \");

Postorder(root); /*break;

case 4: depth=TreeDepth(root); /*printf(\"深度=%d\

先序遍历*/

中序遍历*/

后序遍历*/

求树的深度及叶子数*/

printf(\"叶子数=%d\

break;

case 5: printf(\"层次遍历结果: \");

Levelorder(root); /*break;

default: exit(1);

}

printf(\"\\n\");

}while(i!=0);

}

按层次遍历*/