第6章 树和二叉树

《第6章 树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、6.1若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。(1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。ABCDEFGHI(2)已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。(3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。AABB实例2：试编写算法交换二叉树中所有结点的左、右

2、子树（自选存储结构）。voidexchg_tree(bitreptrBT)/*本算法采用后根遍历递归访问的方法，交换每一个结点的左右子树。*/{if(BT!=null)/*非空*/{exchg_tree(BT->lchild);/*交换左子树所有结点指针*/exchg_tree(BT->rchild);/*交换右子树所有结点指针*/p=BT->lchild;/*交换根结点左右指针*/BT->lchild=BT->rchild;BT->rchild=p;}}实例3：有一二叉链表，按后根遍历时输出的结点顺序为a1,a2,…aa

3、n。试编写一算法，要求输出后根序列的逆序an,an-1…，a2,a1。voidpreorder(treeT){if(T!=NULL){printf(“%f”,T->data);preorder(T->rchild);preorder(T->lchild);}}实例4:有一二叉链表，试编写按层次顺序遍历二叉树的算法。本算法要借用队列来完成，其基本思想是，若二叉树非空，先将根结点进队列。然后进入循环：只要队列不空，就出队列，遍历该结点，然后判断出队列的结点是否有左孩子和右孩子，如有就让左、右孩子进队列。voidlayorder

4、(treeT){initqueue(q)/*队列初始化*/if(T!=NULL){enqueue(q,T);/*入队列*/while(notemptyqueue(q))/*若队列非空*/{outqueue(q,p);/*出队*/printf(“%f”,p->data);if(p->lchild!=NULL)enqueue(q,p->lchild);/*入队列*/if(p->rchild!=NULL)enqueue(q,p->rchild);/*入队列*/}/*endofwhile(notemptyqueue(q))*/}}

5、实例5：设n个元素的先序序列已存在数组A中，试建立起二叉树的二叉链表存储结构。treecreate(r,A)treer;charA[n];{charc;statici=0;c=A[i];i++;if(c==’’)r=null;else{r=(tree*)malloc(sizeof(treenode))if(!r)exit(0);r->data=c;r->lchild=create(r->lchild,A);/*递归建立左子树*/r->rchild=create(r->rchild,A);/*递归建立右子树*/}return

6、(r);}实例6：求二叉树的叶子数。intcountleaf(r);treer;{statici=0;if(r){if((r->lchild==null)&&(r->rchild==null))i++;/*叶子结点*/countleaf(r->lchild);/*递归求左子树中叶子数*/countleaf(r->rchild);/*递归求右子树中叶子数*/}return(i);}实例7：统计二叉树中结点的个数voidCountnode(BiTreeT,int&node){//在实际使用时，node作为全局变量，其初始值为0

7、if(T){node++;Countnode(T->lchild,node);Countnode(T->rchild,node);}//if}//Countnode实例8：求二叉树的深度的算法(后序遍历)intDepth(BiTreeT){//返回二叉树的深度if(T){depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}elsedepthval=0;re

8、turndepthval;}