数据结构六树与叉树.pptVIP

本章主要内容： 本章重点难点： 逻辑结构： 一对二（1:2） 基本特征: ① 每个结点最多只有两棵子树（不存在度大于2的结点）； ② 左子树和右子树次序不能颠倒。 3、二叉树的抽象数据类型定义 设二叉树中结点总数为n，n1为二叉树中度为1的结点总数。因为二叉树中所有结点的度小于等于2，所以有 n= n0+ n1+n2 设二叉树中分支数目为B，因为除根结点外，每个结点均对应一个进入它的分支，所以有：n=B+1。 又因为二叉树中的分支都是由度为1和度为2的结点发出，所以分支数目为： B=n1+2n2 整理上述两式可得到：n=B+1=n1+2n2+1 将n= n0+ n1+n2代入上式得出n0+n1+n2=n1+2n2+1，整理后得n0= n2+1，故结论成立。 研究生试题 【2009】已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是A.39??B.52??C.111??D.119?? ?? 【2010】在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是 A.41???? B.82?? C.113?? D.122 【2011】若一个完全二叉树有768个结点，则该二叉树中叶子结点的个数是A.257??B.258??C.384??D.385 若u和v是二叉树的两个结点 u是v的祖先结点 u在v的左边 u和v是叶子结点 研究生试题 【2009】给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是A．LRN??B.NRL??C.RLN??D.RNL?? 先序和中序序列相同二叉树的树形 后序和中序序列相同二叉树的树形 先序和后序序列相同二叉树的树形 先序和中序序列相反二叉树的树形 后序和中序序列相反二叉树的树形 先序和后序序列相反二叉树的树形 研究生试题 【2011】若一个二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的后序遍历序列不会是（） A.1,2,3,4 B.2,3,4,1 C.3,2,4,1 D.4,3,2,1 先序遍历统计叶子结点个数 后序遍历统计叶子结点个数 int leaf(BiTree root) { int Leafcount; if(root==NULL) LeafCount=0; else if((root-lchild==NULL) (root-rchild==NULL)) LeafCount=1; else LeafCount=leaf(root-lchild)+leaf(root-rchild); return Leafcount; } 4、建立二叉树的存储结构 五、中序遍历算法的非递归描述 Status InorderTraverse(BiTree T,Status (*Visit)(TElemType e)) {//中序遍历二叉树T的非递归算法，采用二叉链表存储结构 Inistack(S);Push(S,T);//根指针进栈 while(!StackEmpty(S)) { while(GetTop(S,p) p) Push(S,p-lchild);//向左走到尽头 Pop(S,p);//空指针退栈 if(!StackEmpty(S))//访问结点，向右一步 { Pop(S,p); if(!Visit(p-data)) return error; Push(S,p-rchild); } } return OK; } 五、中序遍历算法的非递归描述 Status InorderTraverse(BiTree T,Status (*Visit)(TElemType e)) {//中序遍历二叉树T的非递归算法，采用二叉链表存储结构 Inistack(S); p=T; while(p || !StackEmpty(S)) { if(p) {Push(S,p); p=p-lchild);}//根指针进栈，遍历左子树 else {Pop(S,p);//根指针退栈，访问根结点，遍历右子树