四章节二叉树.ppt

第四章 二叉树,任课教员：张 铭 http:/db.pku.edu.cn/mzhang/DS/ mzhangdb.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有，转载或翻印必究,北京大学信息学院 版权所有，转载或翻印必究 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+ 2·n2，于是 n = e + 1= n1 + 2·n2 + 1 （公式4.4） 因此由公式（1）（2）得 n0 + n1 + n2 = n1 + 2·n2 + 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,深度优先周游二叉树（递归实现）,template void 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中的stack stack* 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中的stack stack* 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,非递归后序周游二叉树,template void 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,广度优先周游二叉树,template Void 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,用指针实现二叉树,二叉链表表示的二叉树成员函数实现 template bool BinaryTree: isEmpty() const /判定二叉树是否为空树 return (root)? false :true); template BinaryTreeNode*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,用指针实现二叉树,template BinaryTreeNode* BinaryTree:Parent(BinaryTreeNode* current) /返回current结点的父结点指针 if(current=NULL)|(current=root) return NULL;/空结点或者current为根结点时 /调用递归函数寻找父结点 return GetParent(root,current); ,北京大学信息学院 版权所有，转载或翻印必究 Page 62,用指针实现二叉树,template BinaryTreeNode*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 if return NULL; ,北京大学信息学院 版权所有，转载或翻印必究 Page 63,用指针实现二叉树,template BinaryTreeNode* 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 if return NULL; ,北京大学信息学院 版权所有，转载或翻印必究 Page 64,用指针实现二叉树,templatevoid BinaryTree: 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