四章节二叉树.ppt

四章节二叉树 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望主要内容主要内容n4.1 二叉树的概念二叉树的概念n4.2 二叉树的主要性质二叉树的主要性质 n4.3 二叉树的抽象数据类型二叉树的抽象数据类型n4.4 周游二叉树周游二叉树n4.5 二叉树的实现二叉树的实现n4.6 二叉搜索树二叉搜索树n4.7 堆与优先队列堆与优先队列n4.8 Huffman编码树编码树北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.1 二叉树的概念二叉树的概念n4.1.1 二叉树的定义及相关概念二叉树的定义及相关概念n4.1.2 满二叉树满二叉树 完全二叉树完全二叉树 扩充二叉树扩充二叉树北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 二叉树的定义二叉树的定义n二叉树由结点的有限集合构成二叉树由结点的有限集合构成:n或者为空集或者为空集n或者由或者由一个根结点一个根结点及及两棵不相交两棵不相交的分别称作这个根的的分别称作这个根的左左子树子树和和右子树右子树的二叉树的二叉树(它们也是结点的集合它们也是结点的集合)组成组成n这是个递归的定义。二叉树可以是空集合，因此根这是个递归的定义。二叉树可以是空集合，因此根可以有空的左子树或右子树，或者左右子树皆为空可以有空的左子树或右子树，或者左右子树皆为空北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 二叉树的五种基本形态二叉树的五种基本形态(a)空空(b)独根独根 (c)空右空右(d)空左空左 (e)左右都不空左右都不空北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 满二叉树满二叉树n如果一棵二叉树的如果一棵二叉树的任何任何结点，或者是结点，或者是树叶树叶，或者恰有或者恰有两棵非空两棵非空子树，则此二叉树称作子树，则此二叉树称作满二叉树满二叉树 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 完全二叉树完全二叉树n若一颗二叉树若一颗二叉树n最多最多只有只有最下面的两层最下面的两层结点度数可以小于结点度数可以小于2 2n最下面一层的结点都集中在该层最下面一层的结点都集中在该层最左边最左边的若干位置上，的若干位置上，则称此二叉树为则称此二叉树为完全二叉树完全二叉树n在许多算法和算法分析中都明显地或隐含地用到完在许多算法和算法分析中都明显地或隐含地用到完全二叉树的概念全二叉树的概念北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 完全二叉树完全二叉树北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 扩充二叉充二叉树n当二叉树里出现空的子树时，就增加新的、特当二叉树里出现空的子树时，就增加新的、特殊的结点殊的结点空树叶空树叶n对于原来二叉树里度数为对于原来二叉树里度数为1的分支结点，在它下面的分支结点，在它下面增加一个空树叶增加一个空树叶n对于原来二叉树的树叶，在它下面增加两个空树叶对于原来二叉树的树叶，在它下面增加两个空树叶n扩充的二叉树是满二叉树扩充的二叉树是满二叉树，新增加的空树叶，新增加的空树叶(外部结点外部结点)的个数等于原来二叉树的结点的个数等于原来二叉树的结点(内内部结点部结点)个数加个数加1 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 扩充二叉充二叉树北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 扩充二叉充二叉树n外部路径长度外部路径长度E 从扩充的二叉树的根到每个外从扩充的二叉树的根到每个外部结点的路径长度之和部结点的路径长度之和 n内部路径长度内部路径长度I 扩充的二叉树里从根到每个扩充的二叉树里从根到每个内部结点的路径长度之和内部结点的路径长度之和 nE和和I两个量之间的关系为两个量之间的关系为 E=I+2n 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.2 二叉树的主要性质二叉树的主要性质1.1.满二叉树定理满二叉树定理：非空满二叉树树叶数等于其分支结点数：非空满二叉树树叶数等于其分支结点数加加1 1。证明：设二叉树结点数为证明：设二叉树结点数为n n，叶结点数为，叶结点数为m m，分支结点数，分支结点数为为b b。有有n n（总结点数（总结点数=m=m（叶（叶)+b)+b（分支）（分支）(公式公式4.1)4.1)每个分支，恰有两个子结点（满），故有每个分支，恰有两个子结点（满），故有2*b2*b条边；条边；一颗二叉树，除根结点外，每个结点都恰有一条边联接一颗二叉树，除根结点外，每个结点都恰有一条边联接父结点，故共有父结点，故共有n-1n-1条边。即条边。即n-1=2b (n-1=2b (公式公式4.2)4.2)由由(公式公式4.1)4.1)，(公式公式4.2)4.2)得得 n-1=m+b-1=2b n-1=m+b-1=2b，得出，得出 m(m(叶叶)=b)=b（分支）（分支）+1+1北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.2 二叉树的性质二叉树的性质2.2.满二叉树定理推论满二叉树定理推论：一个非空二叉树的空子树：一个非空二叉树的空子树(指针指针)数目等于其结点数加数目等于其结点数加1 1。证明证明：设二叉树：设二叉树T T，将其所有空子树换为树叶，记新，将其所有空子树换为树叶，记新 的的扩充满二叉树为扩充满二叉树为TT。所有原来。所有原来T T的结点现在是的结点现在是TT的分的分支结点。根据支结点。根据满二叉树定理满二叉树定理，新添加的树叶数目等于新添加的树叶数目等于T T结点个数加结点个数加1 1。而每个。而每个新添加的树叶新添加的树叶对应对应T T的一个空子树的一个空子树。因此因此T T中空子树数目等于中空子树数目等于T T中结点数加中结点数加1 1。北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.2 二叉树的性质二叉树的性质3.3.任何一颗二叉树，度为任何一颗二叉树，度为0 0的结点比度为的结点比度为2 2的结点多一个的结点多一个证明证明：设有：设有n n个结点的二叉树的度为个结点的二叉树的度为0 0、1 1、2 2的结点数的结点数分别为分别为=n=n0 0，n n1 1，n n2 2，则，则n=nn=n0 0+n+n1 1+n+n2 2 (公式公式4.3)4.3)设边数为设边数为e e。因为除根以外，每个结点都有一条边进入，故。因为除根以外，每个结点都有一条边进入，故n=e+1n=e+1。由于这些边是有度为。由于这些边是有度为1 1和和2 2的的结点射出的，的的结点射出的，因此因此e=ne=n1 1+2n+2n2 2，于是，于是n=e+1=nn=e+1=n1 1+2n+2n2 2+1 +1 （公式（公式4.44.4）因此由公式（因此由公式（1 1）（）（2 2）得）得 n n0 0+n+n1 1+n+n2 2=n=n1 1+2n+2n2 2+1+1 即即 n n0 0=n=n2 2+1+1 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.2 二叉树的性质二叉树的性质n4.二叉树的第二叉树的第i层（根为第层（根为第0层，层，i1）最多有）最多有2i个结点个结点n5.高度为高度为k(深度为深度为k-1。只有一个根结点的二叉。只有一个根结点的二叉树的高度为树的高度为1，深度为，深度为0)的二叉树至多有的二叉树至多有2k-1个个结点结点n6.有有n个结点（个结点（n0）的完全二叉树的高度为）的完全二叉树的高度为 log2(n+1)(深度为深度为 log2(n+1)-1)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.2 二叉树的性质二叉树的性质n二叉树的二叉树的高度高度定义为二叉树中层数最定义为二叉树中层数最大的叶结点的层数加大的叶结点的层数加1n二叉树的二叉树的深度深度定义为二叉树中层数最定义为二叉树中层数最大的叶结点的层数大的叶结点的层数北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.3 二叉树的抽象数据类型二叉树的抽象数据类型n定义了二叉树的定义了二叉树的逻辑结构逻辑结构之后，我们需要考虑在二叉树逻辑之后，我们需要考虑在二叉树逻辑结构之上的各种可能结构之上的各种可能运算运算，这些运算应该适合二叉树的各种，这些运算应该适合二叉树的各种应用应用：n二叉树的某些运算是二叉树的某些运算是针对整棵树针对整棵树的的n初始化二叉树初始化二叉树n合并两棵二叉树合并两棵二叉树n二叉树的大部分运算都是二叉树的大部分运算都是围绕结点围绕结点进行的进行的n访问某个结点的左子结点、右子结点、父结点访问某个结点的左子结点、右子结点、父结点n访问结点存储的数据。访问结点存储的数据。北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.3 二叉树的抽象数据类型二叉树的抽象数据类型n二叉树结点抽象数据类型二叉树结点抽象数据类型BinaryTreeNode是带有是带有参数参数 T 的模板，的模板，T是存储在结点中的数据类型是存储在结点中的数据类型n每个元素结点都有每个元素结点都有leftchild()和和rightchild()左右子结点左右子结点结构结构n另外每个结点还包含一个数据域另外每个结点还包含一个数据域value()。n为了强调抽象数据类型与存储无关，我们并没有具体为了强调抽象数据类型与存储无关，我们并没有具体规定该抽象数据类型的存储方式规定该抽象数据类型的存储方式 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.3 二叉树的抽象数据类型二叉树的抽象数据类型template class BinaryTreeNode/申明二叉树为结点类的友元类，便于访问私有申明二叉树为结点类的友元类，便于访问私有/数据成员数据成员 friend class BinaryTree;private:/二叉树结点数据域二叉树结点数据域T element;/实现时，可以补充实现时，可以补充private的左子结点的左子结点/右子结点定义右子结点定义北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.3 二叉树的抽象数据类型二叉树的抽象数据类型public:BinaryTreeNode();/缺省构造函数缺省构造函数 BinaryTreeNode(const T&ele);/拷贝构造函数拷贝构造函数 /给定了结点值和左右子树的构造函数给定了结点值和左右子树的构造函数 BinaryTreeNode(const T&ele,BinaryTreeNode*l,BinaryTreeNode*r);T value()const;/返回当前结点的数据返回当前结点的数据/返回当前结点指向左子树返回当前结点指向左子树 BinaryTreeNode*leftchild()const;/返回当前结点指向右子树返回当前结点指向右子树 BinaryTreeNode*rightchild()const;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.3 二叉树的抽象数据类型二叉树的抽象数据类型/设置当前结点的左子树设置当前结点的左子树 void setLeftchild(BinaryTreeNode*);/设置当前结点的右子树设置当前结点的右子树 void setRightchild(BinaryTreeNode*);/设置当前结点的数据域设置当前结点的数据域 void setValue(const T&val);/判定当前结点是否为叶结点判定当前结点是否为叶结点,若是返回若是返回true bool isLeaf()const;/重载赋值操作符重载赋值操作符 BinaryTreeNode&operator=(const BinaryTreeNode&Node);北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.3 二叉树的抽象数据类型二叉树的抽象数据类型n二叉树的抽象数据类型的二叉树的抽象数据类型的C+定义定义BinaryTree，没有具体规，没有具体规定该抽象数据类型的存储方式定该抽象数据类型的存储方式 template class BinaryTree private:/二叉树根结点指针二叉树根结点指针BinaryTreeNode*root;/从二叉树的从二叉树的root结点开始结点开始/查找查找current结点的父结点结点的父结点BinaryTreeNode*GetParent(BinaryTreeNode*root,BinaryTreeNode*current);北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 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 4.3 二叉树的抽象数据类型二叉树的抽象数据类型/返回返回current结点的右兄弟结点的右兄弟BinaryTreeNode*RightSibling(BinaryTreeNode*current);/以以elem作为根结点，作为根结点，leftTree作为树的左子树作为树的左子树,/rightTree作为树的右子树，构造一棵新的二叉树作为树的右子树，构造一棵新的二叉树void CreateTree(const T&elem,BinaryTree&leftTree,BinaryTree&rightTree);/前序周游二叉树或其子树前序周游二叉树或其子树void PreOrder(BinaryTreeNode*root)；/中序周游二叉树或其子树中序周游二叉树或其子树void InOrder(BinaryTreeNode*root)；北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.3 二叉树的抽象数据类型二叉树的抽象数据类型/后序周游二叉树或其子树后序周游二叉树或其子树void PostOrder(BinaryTreeNode*root)；/按层次周游二叉树或其子树按层次周游二叉树或其子树void LevelOrder(BinaryTreeNode*root)；/删除二叉树或其子树删除二叉树或其子树void DeleteBinaryTree(BinaryTreeNode*root);北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.4 周游二叉树周游二叉树 n周游周游系统地访问数据结构中的结点。系统地访问数据结构中的结点。每个结点都正好被访问到一次。每个结点都正好被访问到一次。n周游一棵二叉树的过程实际上就是把二周游一棵二叉树的过程实际上就是把二叉树的结点放入一个线性序列的过程，叉树的结点放入一个线性序列的过程，或者说把或者说把二叉树进行线性化二叉树进行线性化 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4.4 周游二叉树周游二叉树 n二叉二叉树周游周游n4.4.1 深度优先周游二叉树深度优先周游二叉树n4.4.2 非递归深度优先周游二叉树非递归深度优先周游二叉树n4.4.3 广度优先周游二叉树广度优先周游二叉树北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 深度优先周游二叉树深度优先周游二叉树我们变换一下根结点的周游顺序，可以得到我们变换一下根结点的周游顺序，可以得到以下三种方案：以下三种方案：前序周游前序周游(tLR(tLR次序次序)：访问根结点；前：访问根结点；前 序周游左子树；前序周游右子树。序周游左子树；前序周游右子树。中序周游中序周游(LtR(LtR次序次序)：中序周游左子：中序周游左子 树；访问根结点；中序周游右子树。树；访问根结点；中序周游右子树。后序周游后序周游(LRt(LRt次序次序)：后序周游左子：后序周游左子 树；后序周游右子树；访问根结点。树；后序周游右子树；访问根结点。北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 深度优先周游二叉树深度优先周游二叉树n深度周游如下二叉树深度周游如下二叉树北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 深度优先周游二叉树深度优先周游二叉树n深度周游二叉树结果深度周游二叉树结果n 前序周游：前序周游：ABDCEGFHI n 中序周游：中序周游：DBAEGCHFI n 后序周游：后序周游：DBGEHIFCA 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 深度优先周游二叉树（递归实现）深度优先周游二叉树（递归实现）templatevoid BinaryTree:DepthOrder (BinaryTreeNode*root)if(root!=NULL)Visit(root);/前序前序DepthOrder(root-leftchild();/访问左子树访问左子树Visit(root);/中序中序DepthOrder(root-rightchild();/访问右子树访问右子树Visit(root);/后序后序北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归深度优先周游二叉树非递归深度优先周游二叉树 n栈栈是实现递归的最常用的结构是实现递归的最常用的结构n深度优先二叉树周游是递归定义的深度优先二叉树周游是递归定义的n利用一个栈来记下尚待周游的结点或利用一个栈来记下尚待周游的结点或子树，以备以后访问。子树，以备以后访问。北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归前序周游二叉树非递归前序周游二叉树 n思想：思想：n遇到一个结点，就访问该结点，并把此结点推入栈中，然遇到一个结点，就访问该结点，并把此结点推入栈中，然后下降去周游它的左子树；后下降去周游它的左子树；n周游完它的左子树后，从栈顶托出这个结点，并按照它的周游完它的左子树后，从栈顶托出这个结点，并按照它的右链接指示的地址再去周游该结点的右子树结构。右链接指示的地址再去周游该结点的右子树结构。template void BinaryTree:PreOrderWithoutRecusion(BinaryTreeNode*root)/非递归前序遍历二叉树或其子树非递归前序遍历二叉树或其子树北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归前序周游二叉树非递归前序周游二叉树 using std:stack;/使用使用STL中的中的stackstackBinaryTreeNode*aStack;BinaryTreeNode*pointer=root;while(!aStack.empty()|pointer)if(pointer)/访问当前结点访问当前结点 Visit(pointer-value();/当前结点地址入栈当前结点地址入栈 aStack.push(pointer);北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归前序周游二叉树非递归前序周游二叉树/当前链接结构指向左孩子当前链接结构指向左孩子pointer=pointer-leftchild();else/左子树访问完毕，转向访问右子树左子树访问完毕，转向访问右子树 pointer=aStack.top();aStack.pop();/栈顶元素退栈栈顶元素退栈 /当前链接结构指向右孩子当前链接结构指向右孩子 pointer=pointer-rightchild();/end while北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归中序周游二叉树非递归中序周游二叉树n思想：思想：n遇到一个结点，就把它推入栈中，并去周游它的左子树遇到一个结点，就把它推入栈中，并去周游它的左子树n周游完左子树后，从栈顶托出这个结点并访问之，然后按周游完左子树后，从栈顶托出这个结点并访问之，然后按照它的右链接指示的地址再去周游该结点的右子树。照它的右链接指示的地址再去周游该结点的右子树。ntemplate void BinaryTree:InOrderWithoutRecusion(BinaryTreeNode*root)/非递归中序遍历二叉树或其子树非递归中序遍历二叉树或其子树北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归中序周游二叉树非递归中序周游二叉树using std:stack;/使用使用STL中的中的stackstackBinaryTreeNode*aStack;BinaryTreeNode*pointer=root;while(!aStack.empty()|pointer)if(pointer)/当前结点地址入栈当前结点地址入栈 aStack.push(pointer);/当前链接结构指向左孩子当前链接结构指向左孩子 pointer=pointer-leftchild();北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归中序周游二叉树非递归中序周游二叉树 /end if else/左子树访问完毕，转向访问右子树左子树访问完毕，转向访问右子树 pointer=aStack.top();Visit(pointer-value();/访问当前结点访问当前结点 /当前链接结构指向右孩子当前链接结构指向右孩子 pointer=pointer-rightchild();aStack.pop();/栈顶元素退栈栈顶元素退栈 /end else /end while 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归后序周游二叉树非递归后序周游二叉树n思想思想:n遇到一个结点，把它推入栈中，周游它的左子树遇到一个结点，把它推入栈中，周游它的左子树n周游结束后，还不能马上访问处于栈顶的该结点，周游结束后，还不能马上访问处于栈顶的该结点，而是要再按照它的右链接结构指示的地址去周游该而是要再按照它的右链接结构指示的地址去周游该结点的右子树结点的右子树n周游遍右子树后才能从栈顶托出该结点并访问之周游遍右子树后才能从栈顶托出该结点并访问之北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归后序周游二叉树非递归后序周游二叉树n解决方案：解决方案：n需要给栈中的每个元素加上一个需要给栈中的每个元素加上一个特征位特征位，以便当从栈顶托出，以便当从栈顶托出一个结点时区别是从栈顶元素左边回来的一个结点时区别是从栈顶元素左边回来的(则要继续周游右则要继续周游右子树子树)，还是从右边回来的，还是从右边回来的(该结点的左、右子树均已周游该结点的左、右子树均已周游)n特征为特征为Left表示已进入该结点的左子树，将从左边回来；特表示已进入该结点的左子树，将从左边回来；特征为征为Right表示已进入该结点的右子树，将从右边回来表示已进入该结点的右子树，将从右边回来北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归后序周游二叉树非递归后序周游二叉树n栈中的元素类型定义栈中的元素类型定义StackElement enum TagsLeft,Right;/特征标识定义特征标识定义template class StackElement/栈元素的定义栈元素的定义public:/指向二叉树结点的链接指向二叉树结点的链接BinaryTreeNode*pointer;/特征标识申明特征标识申明Tags tag;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归后序周游二叉树非递归后序周游二叉树templatevoid BinaryTree:PostOrderWithoutRecusion(BinaryTreeNode*root)/非递归后序遍历二叉树或其子树非递归后序遍历二叉树或其子树using std:stack;/使用使用STL栈部分栈部分StackElement element;stackStackElement aStack;/栈申明栈申明BinaryTreeNode*pointer;if(root=NULL)return;/空树即返回空树即返回北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归后序周游二叉树非递归后序周游二叉树/else pointer=root;while(true)/进入左子树进入左子树 while(pointer!=NULL)element.pointer=pointer;element.tag=Left;aStack.push(element);/沿左子树方向向下周游沿左子树方向向下周游pointer=pointer-leftchild();/托出栈顶元素托出栈顶元素 element=aStack.top();北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归后序周游二叉树非递归后序周游二叉树aStack.pop();pointer=element.pointer;/从右子树回来从右子树回来while(element.tag=Right)Visit(pointer-value();/访问当前结点访问当前结点 if(aStack.empty()return;/else element=aStack.top();北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归后序周游二叉树非递归后序周游二叉树 aStack.pop();/弹栈弹栈 pointer=element.pointer;/end else/end while/从左子树回来从左子树回来element.tag=Right;aStack.push(element);/转向访问右子树转向访问右子树pointer=pointer-rightchild();/end while北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 问题讨论问题讨论n前序周游算法是否还可以简洁一些？前序周游算法是否还可以简洁一些？n前序、中序、后序框架的算法通用性？前序、中序、后序框架的算法通用性？n例如后序框架是否支持前序、中序访问？例如后序框架是否支持前序、中序访问？若支持，怎么改动？若支持，怎么改动？n非递归周游的意义？非递归周游的意义？n栈中存放了什么？栈中存放了什么？北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 思考题思考题n 习题习题4.8:给定结点类型为给定结点类型为BinaryTreeNode的三个指针的三个指针p、q、rt，假设假设rt为根结点，求距离结点为根结点，求距离结点p和结点和结点q最近的这两个结点的共同祖先结点。最近的这两个结点的共同祖先结点。n上机题上机题4.2：表达式二叉树。把计算机内部：表达式二叉树。把计算机内部的一棵表达式二叉树，输出为相应的中缀的一棵表达式二叉树，输出为相应的中缀表达式（可以带括号，但不允许冗余括号）表达式（可以带括号，但不允许冗余括号）北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归前序周游二叉树非递归前序周游二叉树简洁简洁 n思想：思想：n遇到一个结点，就访问该结点，并把此结点的非空右结点遇到一个结点，就访问该结点，并把此结点的非空右结点推入栈中，然后下降去周游它的左子树；推入栈中，然后下降去周游它的左子树；n周游完左子树后，从栈顶托出一个结点，并按照它的右链周游完左子树后，从栈顶托出一个结点，并按照它的右链接指示的地址再去周游该结点的右子树结构。接指示的地址再去周游该结点的右子树结构。template void BinaryTree:PreOrderWithoutRecusion(BinaryTreeNode*root)/非递归前序遍历二叉树或其子树非递归前序遍历二叉树或其子树北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 非递归前序周游二叉树非递归前序周游二叉树 using std:stack;/使用使用STL中的中的stack stackBinaryTreeNode*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 广度优先周游二叉树广度优先周游二叉树 n从二叉树的第一层（根结点）开始，从二叉树的第一层（根结点）开始，自上自上至下至下逐层遍历；在同一层中，按照逐层遍历；在同一层中，按照从左到从左到右右的顺序对结点逐一访问。的顺序对结点逐一访问。n例如：例如：ABCDEFGHIABCDEFGHI北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 广度优先周游二叉树广度优先周游二叉树 templateVoid BinaryTree:LevelOrder(BinaryTreeNode*root)using std:queue;/使用使用STL的队列的队列queueBinaryTreeNode*aQueue;BinaryTreeNode*pointer=root;if(pointer)aQueue.push(pointer);while(!aQueue.empty()北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 广度优先周游二叉树广度优先周游二叉树/取队列首结点取队列首结点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 4.5 二叉树的实现二叉树的实现 n4.5.1 用指针实现二叉树用指针实现二叉树 n4.5.2 空间开销分析空间开销分析n4.5.3 用数组实现完全二叉树用数组实现完全二叉树n4.5.4 穿线二叉树穿线二叉树北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 用指针实现二叉树用指针实现二叉树 n二叉树是非线性的树形结构，在存储器里表示树形结构的二叉树是非线性的树形结构，在存储器里表示树形结构的最自然的方法是最自然的方法是链接链接的方法的方法 n在每个结点中除存储结点本身的数据外再设置在每个结点中除存储结点本身的数据外再设置两个指针字两个指针字段段llink和和rlink，分别指向结点的左子女和右子女，分别指向结点的左子女和右子女n当结点的某个子女为空时，则相应的指针为空指针当结点的某个子女为空时，则相应的指针为空指针n结点的形式为结点的形式为北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 用指针实现二叉树用指针实现二叉树 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 用指针实现二叉树用指针实现二叉树 n二叉树还可以有其他的链接表示法二叉树还可以有其他的链接表示法n例如，在树的每个结点中除用例如，在树的每个结点中除用llink和和rlink分别分别指向子女和兄弟外，再增加一个指向子女和兄弟外，再增加一个指向父母的指指向父母的指针针parent，形成三重链接的二叉树，称为，形成三重链接的二叉树，称为“三三叉链表叉链表”n有了指向父母的指针就给了我们有了指向父母的指针就给了我们“向上向上”访问访问的能力，这在一些复杂的应用中是需要的的能力，这在一些复杂的应用中是需要的 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 用指针实现二叉树用指针实现二叉树 n扩展二叉树结点抽象数据类型扩展二叉树结点抽象数据类型BinaryTreeNode,为每为每个元素结点添加个元素结点添加left和和right左右子结点结构左右子结点结构 private:/二叉树结点指向左子树的指针二叉树结点指向左子树的指针BinaryTreeNode*left;/二叉树结点指向左子树的指针二叉树结点指向左子树的指针BinaryTreeNode*right;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 用指针实现二叉树用指针实现二叉树 n二叉链表表示的二叉树成员函数实现二叉链表表示的二叉树成员函数实现 templatebool BinaryTree:isEmpty()const/判定二叉树是否为空树判定二叉树是否为空树return(root)?false:true);templateBinaryTreeNode*