四章节二叉树.ppt

第四章 二叉树,任课教员：张 铭http:/,北京大学信息学院 版权所有，转载或翻印必究 Page 2,主要内容,4.1 二叉树的概念4.2 二叉树的主要性质 4.3 二叉树的抽象数据类型4.4 周游二叉树4.5 二叉树的实现4.6 二叉搜索树4.7 堆与优先队列4.8 Huffman编码树,北京大学信息学院 版权所有，转载或翻印必究 Page 3,4.1 二叉树的概念,4.1.1 二叉树的定义及相关概念4.1.2 满二叉树 完全二叉树 扩充二叉树,北京大学信息学院 版权所有，转载或翻印必究 Page 4,二叉树的定义,二叉树由结点的有限集合构成:或者为空集或者由一个根结点及两棵不相交的分别称作这个根的左子树和右子树的二叉树(它们也是结点的集合)组成这是个递归的定义。二叉树可以是空集合，因此根可以有空的左子树或右子树，或者左右子树皆为空,北京大学信息学院 版权所有，转载或翻印必究 Page 5,二叉树的五种基本形态,(a)空(b)独根(c)空右(d)空左(e)左右都不空,北京大学信息学院 版权所有，转载或翻印必究 Page 6,满二叉树,如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树,北京大学信息学院 版权所有，转载或翻印必究 Page 7,完全二叉树,若一颗二叉树最多只有最下面的两层结点度数可以小于2最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树在许多算法和算法分析中都明显地或隐含地用到完全二叉树的概念,北京大学信息学院 版权所有，转载或翻印必究 Page 8,完全二叉树,北京大学信息学院 版权所有，转载或翻印必究 Page 9,扩充二叉树,当二叉树里出现空的子树时，就增加新的、特殊的结点空树叶对于原来二叉树里度数为1的分支结点，在它下面增加一个空树叶对于原来二叉树的树叶，在它下面增加两个空树叶扩充的二叉树是满二叉树，新增加的空树叶(外部结点)的个数等于原来二叉树的结点(内部结点)个数加1,北京大学信息学院 版权所有，转载或翻印必究 Page 10,扩充二叉树,北京大学信息学院 版权所有，转载或翻印必究 Page 11,扩充二叉树,外部路径长度E 从扩充的二叉树的根到每个外部结点的路径长度之和 内部路径长度I 扩充的二叉树里从根到每个内部结点的路径长度之和 E和I两个量之间的关系为 E=I+2n,北京大学信息学院 版权所有，转载或翻印必究 Page 12,4.2 二叉树的主要性质,1.满二叉树定理：非空满二叉树树叶数等于其分支结点数加1。证明：设二叉树结点数为n，叶结点数为m，分支结点数为b。有n（总结点数=m（叶)+b（分支）(公式4.1)每个分支，恰有两个子结点（满），故有2*b条边；一颗二叉树，除根结点外，每个结点都恰有一条边联接父结点，故共有n-1条边。即n-1=2b(公式4.2)由(公式4.1)，(公式4.2)得 n-1=m+b-1=2b，得出 m(叶)=b（分支）+1,北京大学信息学院 版权所有，转载或翻印必究 Page 13,4.2 二叉树的性质,2.满二叉树定理推论：一个非空二叉树的空子树(指针)数目等于其结点数加1。证明：设二叉树T，将其所有空子树换为树叶，记新 的扩充满二叉树为T。所有原来T的结点现在是T的分支结点。根据满二叉树定理，新添加的树叶数目等于T结点个数加1。而每个新添加的树叶对应T的一个空子树。因此T中空子树数目等于T中结点数加1。,北京大学信息学院 版权所有，转载或翻印必究 Page 14,4.2 二叉树的性质,3.任何一颗二叉树，度为0的结点比度为2的结点多一个证明：设有n个结点的二叉树的度为0、1、2的结点数分别为=n0，n1，n2，则n=n0+n1+n2(公式4.3)设边数为e。因为除根以外，每个结点都有一条边进入，故n=e+1。由于这些边是有度为1和2的的结点射出的，因此e=n1+2n2，于是n=e+1=n1+2n2+1（公式4.4）因此由公式（1）（2）得 n0+n1+n2=n1+2n2+1 即 n0=n2+1,北京大学信息学院 版权所有，转载或翻印必究 Page 15,4.2 二叉树的性质,4.二叉树的第i层（根为第0层，i1）最多有2i个结点5.高度为k(深度为k-1。只有一个根结点的二叉树的高度为1，深度为0)的二叉树至多有2k-1个结点6.有n个结点（n0）的完全二叉树的高度为log2(n+1)(深度为log2(n+1)-1),北京大学信息学院 版权所有，转载或翻印必究 Page 16,4.2 二叉树的性质,二叉树的高度定义为二叉树中层数最大的叶结点的层数加1二叉树的深度定义为二叉树中层数最大的叶结点的层数,北京大学信息学院 版权所有，转载或翻印必究 Page 17,4.3 二叉树的抽象数据类型,定义了二叉树的逻辑结构之后，我们需要考虑在二叉树逻辑结构之上的各种可能运算，这些运算应该适合二叉树的各种应用：二叉树的某些运算是针对整棵树的初始化二叉树合并两棵二叉树二叉树的大部分运算都是围绕结点进行的访问某个结点的左子结点、右子结点、父结点访问结点存储的数据。,北京大学信息学院 版权所有，转载或翻印必究 Page 18,4.3 二叉树的抽象数据类型,二叉树结点抽象数据类型BinaryTreeNode是带有参数 T 的模板，T是存储在结点中的数据类型每个元素结点都有leftchild()和rightchild()左右子结点结构另外每个结点还包含一个数据域value()。为了强调抽象数据类型与存储无关，我们并没有具体规定该抽象数据类型的存储方式,北京大学信息学院 版权所有，转载或翻印必究 Page 19,4.3 二叉树的抽象数据类型,template class BinaryTreeNode/申明二叉树为结点类的友元类，便于访问私有/数据成员 friend class BinaryTree;private:/二叉树结点数据域T element;/实现时，可以补充private的左子结点/右子结点定义,北京大学信息学院 版权所有，转载或翻印必究 Page 20,4.3 二叉树的抽象数据类型,public:BinaryTreeNode();/缺省构造函数 BinaryTreeNode(const T,北京大学信息学院 版权所有，转载或翻印必究 Page 21,4.3 二叉树的抽象数据类型,/设置当前结点的左子树 void setLeftchild(BinaryTreeNode*);/设置当前结点的右子树 void setRightchild(BinaryTreeNode*);/设置当前结点的数据域 void setValue(const T,北京大学信息学院 版权所有，转载或翻印必究 Page 22,4.3 二叉树的抽象数据类型,二叉树的抽象数据类型的C+定义BinaryTree，没有具体规定该抽象数据类型的存储方式 template class BinaryTree private:/二叉树根结点指针BinaryTreeNode*root;/从二叉树的root结点开始/查找current结点的父结点BinaryTreeNode*GetParent(BinaryTreeNode*root,BinaryTreeNode*current);,北京大学信息学院 版权所有，转载或翻印必究 Page 23,4.3 二叉树的抽象数据类型,public:BinaryTree(root=NULL);/构造函数 BinaryTree()DeleteBinaryTree(root);/析构函数 bool isEmpty()const;/判定二叉树是否为空树/返回二叉树根结点 BinaryTreeNode*Root()return root;/返回current结点的父结点 BinaryTreeNode*Parent(BinaryTreeNode*current);/返回current结点的左兄弟 BinaryTreeNode*LeftSibling(BinaryTreeNode*current);,北京大学信息学院 版权所有，转载或翻印必究 Page 24,4.3 二叉树的抽象数据类型,/返回current结点的右兄弟BinaryTreeNode*RightSibling(BinaryTreeNode*current);/以elem作为根结点，leftTree作为树的左子树,/rightTree作为树的右子树，构造一棵新的二叉树void CreateTree(const T/前序周游二叉树或其子树void PreOrder(BinaryTreeNode*root)；/中序周游二叉树或其子树void InOrder(BinaryTreeNode*root)；,北京大学信息学院 版权所有，转载或翻印必究 Page 25,4.3 二叉树的抽象数据类型,/后序周游二叉树或其子树void PostOrder(BinaryTreeNode*root)；/按层次周游二叉树或其子树void LevelOrder(BinaryTreeNode*root)；/删除二叉树或其子树void DeleteBinaryTree(BinaryTreeNode*root);,北京大学信息学院 版权所有，转载或翻印必究 Page 26,4.4 周游二叉树,周游系统地访问数据结构中的结点。每个结点都正好被访问到一次。周游一棵二叉树的过程实际上就是把二叉树的结点放入一个线性序列的过程，或者说把二叉树进行线性化,北京大学信息学院 版权所有，转载或翻印必究 Page 27,4.4 周游二叉树,二叉树周游4.4.1 深度优先周游二叉树4.4.2 非递归深度优先周游二叉树4.4.3 广度优先周游二叉树,北京大学信息学院 版权所有，转载或翻印必究 Page 28,深度优先周游二叉树,我们变换一下根结点的周游顺序，可以得到以下三种方案：前序周游(tLR次序)：访问根结点；前 序周游左子树；前序周游右子树。中序周游(LtR次序)：中序周游左子 树；访问根结点；中序周游右子树。后序周游(LRt次序)：后序周游左子 树；后序周游右子树；访问根结点。,北京大学信息学院 版权所有，转载或翻印必究 Page 29,深度优先周游二叉树,深度周游如下二叉树,北京大学信息学院 版权所有，转载或翻印必究 Page 30,深度优先周游二叉树,深度周游二叉树结果 前序周游：ABDCEGFHI 中序周游：DBAEGCHFI 后序周游：DBGEHIFCA,北京大学信息学院 版权所有，转载或翻印必究 Page 31,深度优先周游二叉树（递归实现）,templatevoid BinaryTree:DepthOrder(BinaryTreeNode*root)if(root!=NULL)Visit(root);/前序DepthOrder(root-leftchild();/访问左子树Visit(root);/中序DepthOrder(root-rightchild();/访问右子树Visit(root);/后序,北京大学信息学院 版权所有，转载或翻印必究 Page 32,非递归深度优先周游二叉树,栈是实现递归的最常用的结构深度优先二叉树周游是递归定义的利用一个栈来记下尚待周游的结点或子树，以备以后访问。,北京大学信息学院 版权所有，转载或翻印必究 Page 33,非递归前序周游二叉树,思想：遇到一个结点，就访问该结点，并把此结点推入栈中，然后下降去周游它的左子树；周游完它的左子树后，从栈顶托出这个结点，并按照它的右链接指示的地址再去周游该结点的右子树结构。template void BinaryTree:PreOrderWithoutRecusion(BinaryTreeNode*root)/非递归前序遍历二叉树或其子树,北京大学信息学院 版权所有，转载或翻印必究 Page 34,非递归前序周游二叉树,using std:stack;/使用STL中的stackstack*aStack;BinaryTreeNode*pointer=root;while(!aStack.empty()|pointer)if(pointer)/访问当前结点 Visit(pointer-value();/当前结点地址入栈 aStack.push(pointer);,北京大学信息学院 版权所有，转载或翻印必究 Page 35,非递归前序周游二叉树,/当前链接结构指向左孩子pointer=pointer-leftchild();else/左子树访问完毕，转向访问右子树 pointer=aStack.top();aStack.pop();/栈顶元素退栈/当前链接结构指向右孩子 pointer=pointer-rightchild();/end while,北京大学信息学院 版权所有，转载或翻印必究 Page 36,非递归中序周游二叉树,思想：遇到一个结点，就把它推入栈中，并去周游它的左子树周游完左子树后，从栈顶托出这个结点并访问之，然后按照它的右链接指示的地址再去周游该结点的右子树。template void BinaryTree:InOrderWithoutRecusion(BinaryTreeNode*root)/非递归中序遍历二叉树或其子树,北京大学信息学院 版权所有，转载或翻印必究 Page 37,非递归中序周游二叉树,using std:stack;/使用STL中的stackstack*aStack;BinaryTreeNode*pointer=root;while(!aStack.empty()|pointer)if(pointer)/当前结点地址入栈 aStack.push(pointer);/当前链接结构指向左孩子 pointer=pointer-leftchild();,北京大学信息学院 版权所有，转载或翻印必究 Page 38,非递归中序周游二叉树,/end if else/左子树访问完毕，转向访问右子树 pointer=aStack.top();Visit(pointer-value();/访问当前结点/当前链接结构指向右孩子 pointer=pointer-rightchild();aStack.pop();/栈顶元素退栈/end else/end while,北京大学信息学院 版权所有，转载或翻印必究 Page 39,非递归后序周游二叉树,思想:遇到一个结点，把它推入栈中，周游它的左子树周游结束后，还不能马上访问处于栈顶的该结点，而是要再按照它的右链接结构指示的地址去周游该结点的右子树周游遍右子树后才能从栈顶托出该结点并访问之,北京大学信息学院 版权所有，转载或翻印必究 Page 40,非递归后序周游二叉树,解决方案：需要给栈中的每个元素加上一个特征位，以便当从栈顶托出一个结点时区别是从栈顶元素左边回来的(则要继续周游右子树)，还是从右边回来的(该结点的左、右子树均已周游)特征为Left表示已进入该结点的左子树，将从左边回来；特征为Right表示已进入该结点的右子树，将从右边回来,北京大学信息学院 版权所有，转载或翻印必究 Page 41,非递归后序周游二叉树,栈中的元素类型定义StackElement enum TagsLeft,Right;/特征标识定义template class StackElement/栈元素的定义public:/指向二叉树结点的链接BinaryTreeNode*pointer;/特征标识申明Tags tag;,北京大学信息学院 版权所有，转载或翻印必究 Page 42,非递归后序周游二叉树,templatevoid BinaryTree:PostOrderWithoutRecusion(BinaryTreeNode*root)/非递归后序遍历二叉树或其子树using std:stack;/使用STL栈部分StackElement element;stack aStack;/栈申明BinaryTreeNode*pointer;if(root=NULL)return;/空树即返回,北京大学信息学院 版权所有，转载或翻印必究 Page 43,非递归后序周游二叉树,/else pointer=root;while(true)/进入左子树 while(pointer!=NULL)element.pointer=pointer;element.tag=Left;aStack.push(element);/沿左子树方向向下周游pointer=pointer-leftchild();/托出栈顶元素 element=aStack.top();,北京大学信息学院 版权所有，转载或翻印必究 Page 44,非递归后序周游二叉树,aStack.pop();pointer=element.pointer;/从右子树回来while(element.tag=Right)Visit(pointer-value();/访问当前结点 if(aStack.empty()return;/else element=aStack.top();,北京大学信息学院 版权所有，转载或翻印必究 Page 45,非递归后序周游二叉树,aStack.pop();/弹栈 pointer=element.pointer;/end else/end while/从左子树回来element.tag=Right;aStack.push(element);/转向访问右子树pointer=pointer-rightchild();/end while,北京大学信息学院 版权所有，转载或翻印必究 Page 46,问题讨论,前序周游算法是否还可以简洁一些？前序、中序、后序框架的算法通用性？例如后序框架是否支持前序、中序访问？若支持，怎么改动？非递归周游的意义？栈中存放了什么？,北京大学信息学院 版权所有，转载或翻印必究 Page 47,思考题,习题4.8:给定结点类型为BinaryTreeNode的三个指针p、q、rt，假设rt为根结点，求距离结点p和结点q最近的这两个结点的共同祖先结点。上机题4.2：表达式二叉树。把计算机内部的一棵表达式二叉树，输出为相应的中缀表达式（可以带括号，但不允许冗余括号）,北京大学信息学院 版权所有，转载或翻印必究 Page 48,非递归前序周游二叉树简洁,思想：遇到一个结点，就访问该结点，并把此结点的非空右结点推入栈中，然后下降去周游它的左子树；周游完左子树后，从栈顶托出一个结点，并按照它的右链接指示的地址再去周游该结点的右子树结构。template void BinaryTree:PreOrderWithoutRecusion(BinaryTreeNode*root)/非递归前序遍历二叉树或其子树,北京大学信息学院 版权所有，转载或翻印必究 Page 49,非递归前序周游二叉树,using std:stack;/使用STL中的stack stack*aStack;BinaryTreeNode*pointer=root;aStack.push(NULL);/栈底监视哨 while(pointer)/或者!aStack.empty()Visit(pointer-value();/访问当前结点 if(pointer-rightchild()!=NULL)/右孩子入栈 aStack.push(pointer-rightchild();if(pointer-leftchild()!=NULL)pointer=pointer-leftchild();/左路下降 else/左子树访问完毕，转向访问右子树 pointer=aStack.top();aStack.pop();/栈顶元素退栈,北京大学信息学院 版权所有，转载或翻印必究 Page 50,广度优先周游二叉树,从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。例如：ABCDEFGHI,北京大学信息学院 版权所有，转载或翻印必究 Page 51,广度优先周游二叉树,templateVoid BinaryTree:LevelOrder(BinaryTreeNode*root)using std:queue;/使用STL的队列queue*aQueue;BinaryTreeNode*pointer=root;if(pointer)aQueue.push(pointer);while(!aQueue.empty(),北京大学信息学院 版权所有，转载或翻印必究 Page 52,广度优先周游二叉树,/取队列首结点pointer=aQueue.front();Visit(pointer-value();/访问当前结点aQueue.pop();/左子树进队列if(pointer-leftchild()aQueue.push(pointer-leftchild();/右子树进队列if(pointer-rightchild()aQueue.push(pointer-rightchild();/end while,北京大学信息学院 版权所有，转载或翻印必究 Page 53,4.5 二叉树的实现,4.5.1 用指针实现二叉树 4.5.2 空间开销分析4.5.3 用数组实现完全二叉树4.5.4 穿线二叉树,北京大学信息学院 版权所有，转载或翻印必究 Page 54,用指针实现二叉树,二叉树是非线性的树形结构，在存储器里表示树形结构的最自然的方法是链接的方法 在每个结点中除存储结点本身的数据外再设置两个指针字段llink和rlink，分别指向结点的左子女和右子女当结点的某个子女为空时，则相应的指针为空指针结点的形式为,北京大学信息学院 版权所有，转载或翻印必究 Page 55,用指针实现二叉树,北京大学信息学院 版权所有，转载或翻印必究 Page 56,用指针实现二叉树,二叉树还可以有其他的链接表示法例如，在树的每个结点中除用llink和rlink分别指向子女和兄弟外，再增加一个指向父母的指针parent，形成三重链接的二叉树，称为“三叉链表”有了指向父母的指针就给了我们“向上”访问的能力，这在一些复杂的应用中是需要的,北京大学信息学院 版权所有，转载或翻印必究 Page 57,用指针实现二叉树,扩展二叉树结点抽象数据类型BinaryTreeNode,为每个元素结点添加left和right左右子结点结构 private:/二叉树结点指向左子树的指针BinaryTreeNode*left;/二叉树结点指向左子树的指针BinaryTreeNode*right;,北京大学信息学院 版权所有，转载或翻印必究 Page 58,用指针实现二叉树,二叉链表表示的二叉树成员函数实现 templatebool BinaryTree:isEmpty()const/判定二叉树是否为空树return(root)?false:true);templateBinaryTreeNode*BinaryTree:GetParent(BinaryTreeNode*root,BinaryTreeNode*current),北京大学信息学院 版权所有，转载或翻印必究 Page 59,用指针实现二叉树,/从二叉树的root结点开始，查找current结点/父结点BinaryTreeNode*temp;if(root=NULL)return NULL;/找到父结点if(root-leftchild()=current)|(root-rightchild()=current)return root;,北京大学信息学院 版权所有，转载或翻印必究 Page 60,用指针实现二叉树,/递归寻找父结点if(temp=GetParent(root-leftchild(),current)!=NULL)return temp;else return GetParent(root-rightchild(),current);,北京大学信息学院 版权所有，转载或翻印必究 Page 61,用指针实现二叉树,templateBinaryTreeNode*BinaryTree:Parent(BinaryTreeNode*current)/返回current结点的父结点指针if(current=NULL)|(current=root)return NULL;/空结点或者current为根结点时/调用递归函数寻找父结点return GetParent(root,current);,北京大学信息学院 版权所有，转载或翻印必究 Page 62,用指针实现二叉树,templateBinaryTreeNode*BinaryTree:LeftSibling(BinaryTreeNode*current)/返回current结点的左兄弟if(current)/current不为空/返回current结点的父结点BinaryTreeNode*temp=Parent(current);/如果父结点为空，或者current没有左兄弟 If(temp=NULL)|current=temp-leftchild()return NULL;else return temp-leftchild();/end ifreturn NULL;,北京大学信息学院 版权所有，转载或翻印必究 Page 63,用指针实现二叉树,templateBinaryTreeNode*BinaryTree:RightSibling(BinaryTreeNode*current)/返回current结点的右兄弟if(current)/返回current结点的父结点BinaryTreeNode*temp=Parent(current);/如果父结点为空，或者current没有右兄弟if(temp=NULL)|current=temp-rightchild()return NULL;else return temp-rightchild();/end ifreturn NULL;,北京大学信息学院 版权所有，转载或翻印必究 Page 64,用指针实现二叉树,templatevoidBinaryTree:CreateTree(const T,北京大学信息学院 版权所有，转载或翻印必究 Page 65,用指针实现二叉树,templatevoid BinaryTree:DeleteBinaryTree(BinaryTreeNode*root)/以后序周游的方式删除二叉树if(root)DeleteBinaryTree(root-left);/递归删除左子树DeleteBinaryTree(root-right);/递归删除右子树delete root;/删除根结点,北京大学信息学院 版权所有，转载或翻印必究 Page 66,空间开销分析,结构性开销是指为了实现数据结构而花费的辅助空间比例。这些辅助空间不是用来存储数据记录，而是为了保存数据结构的逻辑特性或为了方便运算。,北京大学信息学院 版权所有，转载或翻印必究 Page 67,空间开销分析,存储密度(1)表示数据结构存储的效率 显然=1-如果所有的存储空间都分配给了数据，则这个存储结构叫紧凑结构，否则叫非紧凑结构，紧凑结构的存储密度为1，非紧凑结构的存储密度小于1显然二叉链表的存储是非紧凑结构。存储密度越大，则存储空间的利用效率越高,北京大学信息学院 版权所有，转载或翻印必究 Page 68,空间开销分析,根据满二叉树定理：一半的指针是空的如果只有叶结点存储数据，分支结点为内部结构结点（如Huffman树），则开销取决于二叉树是否满（越满存储效率越高）对于简单的每个结点存两个指针、一个数据域总空间(2p+d)n结构性开销：2pn如果 p=d，则 2p/(2p+d)=2/3,北京大学信息学院 版权所有，转载或翻印必究 Page 69,空间开销分析,去掉满二叉树叶结点中的指针 n/2(2p)p n/2(2p)+dn p+d 则结构性开销为 1/2（假设p=d）如果只在叶结点存数据，则结构性开销为2pn/(2pn+d(n+1)2/3（假设p=d）注意：区分叶结点和分支结点又需要额外的算法时间。,=,北京大学信息学院 版权所有，转载或翻印必究 Page 70,空间开销分析,在C+中，可以用两种方法来实现不同的分支结点与叶结点：用union联合类型定义使用C+的子类来分别实现分支结点与叶结点，并采用虚函数isLeaf来区别分支结点与叶结点早期有人利用结点指针的一个空闲位（一个bit就可以）来存储结点所属的类型也有人利用指向叶结点的指针或者叶结点中的指针域来存储该叶结点的值。目前，计算机内存资源并不紧张的时候，一般不提倡这种单纯追求效率，而丧失可读性的做法,北京大学信息学院 版权所有，转载或翻印必究 Page 71,用数组实现完全二叉树,当我们要求一个二叉树紧凑存储，并且在处理过程中，该二叉树结构的大小和形状不发生激烈的动态变化时，可以采用顺序的方法存储 用顺序方法存储二叉树，就是要把所有结点按照一定的次序顺序存储到一片连续的存储单元中适当安排这个结点的线性序列，可以使结点在序列中的相互位置反映出二叉树结构的部分信息但一般说来这样的信息是不足以刻画整个结构的，还要在结点中附加一些其他的必要信息，以完全地反映整个结构,北京大学信息学院 版权所有，转载或翻印必究 Page 72,用数组实现完全二叉树,按层次顺序将一棵有n个结点的完全二叉树的所有结点从0到n-1编号，就得到结点的一个线性序列,北京大学信息学院 版权所有，转载或翻印必究 Page 73,完全二叉树的下标公式,完全二叉树中除最下面一层外，各层都被结点充满了，每一层结点个数恰是上一层结点个数的两倍。因此，从一个结点的编号就可以推知它的父母，左、右子女，兄弟等结点的编号当2i+1n时，结点i的左子女是结点2i+1，否则结点i没有左子女 当2i+2n时，结点i的右子女是结点2i+2，否则结点i没有右子女,北京大学信息学院 版权所有，转载或翻印必究 Page 74,完全二叉树的下标公式,当0in时，结点i的父母是结点(i-1)/2 当i为偶数且0in时，结点i的左兄弟是结点i-1，否则结点i没有左兄弟 当i为奇数且i+1n时，结点i的右兄弟是结点i+1，否则结点i没有右兄弟,北京大学信息学院 版权所有，转载或翻印必究 Page 75,完全二叉树的顺序存储总结,完全二叉树结点的层次序列足以反映二叉树的结构所有结点按层次顺序依次存储在一片连续的存储单元中，则根据一个结点的存储地址就可算出它的左右子女，父母的存储地址，就好像明显地存储了相应的指针一样存储完全二叉树的最简单，最节省空间的存储方式完全二叉树的顺序存储，在存储结构上是线性的，但在逻辑结构上它仍然是二叉树型结构,北京大学信息学院 版权所有，转载或翻印必究 Page 76,穿线二叉树,穿线树：在二叉链表存储形式的二叉树中，把结点中空指针利用成为周游线索原来为空的左指针指向结点在某种周游序列下的前驱原来为空的右指针指向结点在同一种周游序列下的后继这样的二叉树称为穿线树可以有中序穿线树，前序穿线树，后序穿线树。每种穿线树可以只穿一半目的：利用空指针的存储空间，建立周游线索,北京大学信息学院 版权所有，转载或翻印必究 Page 77,穿线二叉树,为了区分线索和指针，需在每个结点中增加两个标志位，分别标识左右指针域是实际指针还是线索lTag=0,left为左子女指针lTag=1,left为前驱线索rTag=0,right为右子女指针rTag=1,right为后继指针,北京大学信息学院 版权所有，转载或翻印必究 Page 78,中序穿线二叉树：示例,北京大学信息学院 版权所有，转载或翻印必究 Page 79,template class ThreadBinaryTreeNode private:int lTag,rTag;/左右标志位/线索或左右子树ThreadBinaryTreeNode*left,*right;Telement;public:ThreadBinaryTreeNode();/缺省构造函数ThreadBinaryTreeNode(const T)/拷贝构造函数:element(T),left(NULL),right(NULL),lTag(0),rTag(0);,穿线二叉树结点类,北京大学信息学院 版权所有，转载或翻印必究 Page 80,穿线二叉树结点类,T,北京大学信息学院 版权所有，转载或翻印必究 Page 81,中序穿线二叉树类,template class ThreadBinaryTreeprivate:ThreadBinaryTreeNode*root;/根结点指针public:ThreadBinaryTree()root=NULL;/构造函数virtual ThreadBinaryTree()DeleteTree(root);/返回根结点指针ThreadBinaryTreeNode*getroot()return root;/中序线索化二叉树void InThread(ThreadBinaryTreeNode*root);/中序周游 void InOrder(ThreadBinaryTreeNode*root);,北京大学信息学院 版权所有，转载或翻印必究 Page 82,中序线索化二叉树：递归实现,template void ThreadBinaryTree:InThread(ThreadBinaryTreeNode*root,ThreadBinaryTreeNode*,北京大学信息学院 版权所有，转载或翻印必究 Page 83,中序线索化二叉树：递归实现,if(pre)root-lTag=1;if(pre)/中序线索化右子树/end if,北京大学信息学院 版权所有，转载或翻印必究 Page 84,周游穿线树,中序周游中序穿线树：先从穿线树的根出发，一直沿左指针，找到“最左”(它一定是中序的第一个结点)；然后反复地找结点的中序后继一个结点的右指针如果是线索，则右指针就是下一个要周游的结点，如果右指针不是线索，则它的中序后继是其右子树的“最左”结点,北京大学信息学院 版权所有，转载或翻印必究 Page 85,中序周游穿线树,templatevoid ThreadBinaryTree:InOrder(ThreadBinaryTreeNode*root)ThreadBinaryTreeNode*pointer;/是否为空二叉树if(root=NULL)return;else pointer=root;/找“最左下”结点while(pointer-leftchild()!=NULL)pointer=pointer-leftchild();/访问当前结点并找出当前结点的中序后继,北京大学信息学院 版权所有，转载或翻印必究 Page 86,中序周游穿线树,while(1)Visit(pointer-value();/访问当前结点if(pointer-rightchild()=NULL)return;if(pointer-rTag=1)pointer=pointer-rightchild();/按照线索寻找后继else/按照指针寻找后继 pointer=pointer-rightchild();while(pointer-lTag=0)pointer=pointer-leftchild();/沿左链下降/end else/end while,北京大学信息学院 版权所有，转载或翻印必究 Page 87,问题讨论,是否能够改进第一次找“最左下”结点的代码？是否能够改进整个代码？,北京大学信息学院 版权所有，转载或翻印必究 Page 88,穿线二叉树,中序穿线树里找指定结点在前序下的后继结点 算法中需要用到的一个重要事实：若一个树叶是某子树的中序下的最后一个结点，则它必是该子树的前序下最后一个结点,北京大学信息学院 版权所有，转载或翻印必究 Page 89,穿线二叉树,情况一：当指定结点不是树叶时若指定结点有左子女，则左子女是它的前序后继若指定结点没有左子女，则右子女是它