欢迎来到天天文库
浏览记录
ID:14388954
大小:43.00 KB
页数:3页
时间:2018-07-28
《第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;}
此文档下载收益归作者所有