关于二叉树的一些操作(C源码).doc

/* 调试环境VS2008、VC+6.0 */*关于二叉树的一些操作，包括二叉树的建立，输出，遍历*/*判断是否为完全二叉树，求二叉树的层数，求叶子结点数*/#include #include #include #define MAX(x,y) (x)(y)?(x):(y)typedef struct BiTNodeint data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree CreateBiTree(BiTree T) / 按先序次序输入二叉树中结点的值(int类型) /构造二叉链表表示的二叉树T，结点值为int型，表示空（子）树int num;scanf(%d,&num);if(0 = num) / 空T=NULL; else T=(BiTree)malloc(sizeof(BiTNode);if(!T)exit(0);T-data = num; / 生成根结点printf(请输入结点%d的左子结点: ,T-data);T-lchild = CreateBiTree(T-lchild); / 构造左子树printf(请输入结点%d的右子结点: ,T-data);T-rchild = CreateBiTree(T-rchild); / 构造右子树 return T;void PrintBiTree(BiTree T) /先序遍历输出二叉树，其中NULL表示空结点 /输出其嵌套括号表示格，即形如A(T1,T2)，其中A为根结点，T1，T2分别为A的左子树和右子树if(T != NULL)printf(%d,T-data); /若结点非空，输出结点的值if(T-lchild != NULL | T-rchild != NULL)printf();PrintBiTree(T-lchild); /判断左子树，非空则输出根结点的值printf(,);if(T-rchild != NULL)PrintBiTree(T-rchild); /判断右子树，非空则输出根结点的值else printf(NULL);printf();elseprintf(NULL);int FullBiTree(BiTree T) /判断二叉树是否为完全二叉树，完全二叉树需满足两个条件 /一是某结点缺失左或右孩子，则其后续结点均无孩子结点 /二是某结点无左孩子，则一定无右孩子 /需按层次遍历二叉树，故设一队列，用queue表示该队列 /用bj表示是否所以结点均有左孩子和右孩子，若是bj=1,否则bj=0BiTree queue50,p;int first = 0,rear = 0,cm = 1,bj = 1;if(T != NULL)queue+rear = T; /根结点入队while(first != rear)p = queue+first; /p按入队先后顺序依次指向队列中的结点if(p-lchild = NULL)bj = 0;/p的左孩子为空，bj=0if(p-rchild != NULL) /p的左孩子为空，右孩子却不为空，不可能是完全二叉树了cm = 0; break;elsecm = bj;if(!cm)break;queue+rear = p-lchild; /p的左孩子不为空，入队if(p-rchild = NULL) /p的左孩子非空，右孩子空，则其左孩子必须无后续结点bj = 0; /否则不可能为完全二叉树elsequeue+rear = p-rchild;/p的右孩子非空，入队return cm; return 1;void preorder(BiTree T) /先序遍历二叉树并输出if(T != NULL)printf(%d,T-data);preorder(T-lchild);preorder(T-rchild);void inorder(BiTree T) /中序遍历二叉树并输出if(T != NULL)preorder(T-lchild);printf(%d,T-data);preorder(T-rchild);void postorder(BiTree T) /后序遍历二叉树并输出if(T != NULL)preorder(T-lchild);preorder(T-rchild);printf(%d,T-data);void layorder(BiTree T) /按层次遍历二叉树，利用队列先进先出性质即可int head=0,tail=0;BiTree queue50,p;p = T;if(p != NULL)queuetail+ = p; while(head != tail)if(p-lchild != NULL)queuetail+ = p-lchild;if(p-rchild != NULL)queuetail+ = p-rchild;printf(%d,p-data);p = queue+head;int leaf_num(BiTree T) /计算叶子结点数，并输出叶子结点 /f(T)=0,如果T=NULL /f(T)=1,如果T-lchild=T-rchild=NULL /f(T)=f(T-lchild)+f(T-rchild),其他情况int num1,num2;if(T = NULL)return 0;else if(T-lchild = NULL & T-rchild = NULL)printf( 结点%d,T-data);return 1;elsenum1 = leaf_num(T-lchild);num2 = leaf_num(T-rchild);return (num1+num2);int layer_num(BiTree T) /f(T)=0,如果T=NULL /f(T)=1,如果T-lchild=T-rchild=NULL /f(T)=maxf(T-lchild)+1,f(T-rchild)+1,其他情况int num1,num2;if(T = NULL)return 0;else if(T-lchild = NULL & T-rchild = NULL)return 1;elsenum1 = layer_num(T-lchild)+1;num2 = layer_num(T-rchild)+1;return MAX(num1,num2);int main(void)int k;BiTree T=NULL;printf(n建立二叉树n请输入树的根结点：);T = CreateBiTree(T);printf(n输出二叉树：n);PrintBiTree(T);if(FullBiTree(T)printf(nn这是一棵完全二叉树);elseprintf(nn这不是一棵完全二叉树);printf(nn先序遍历二叉树：); preorder(T);printf(nn中序遍历二叉树：); inorder(T);printf(nn后序遍历二叉树：); postorder(T);printf(