5-数据结构与算法-北京大学2008-张铭-二叉树

数据结构与算法第5章二叉树本章由王腾蛟主写://张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。5.1二叉树的概念5.2二叉树的抽象数据类型5.3二叉树的存储结构5.4二叉搜索树5.5堆与优先队列5.6Huffman树及其应用5.7二叉树知识点总结主要内容“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。5.1.1二叉树的定义及基本术语5.1.2满二叉树、完全二叉树、扩充二叉树5.1.3二叉树的主要性质5.1二叉树的概念“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二叉树的定义二叉树(binarytree)由结点的有限集合构成，这个有限集合或者为空集(empty)，或者为由一个根结点(root)及两棵互不相交、分别称作这个根的左子树(leftsubtree)和右子树(rightsubtree)的二叉树组成的集合。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二叉树的五种基本形态(a)空二叉树(b)仅有根的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左右子树均非空的二叉树图5.1二叉树的五种基本形态“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。满二叉树如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则这棵二叉树称作满二叉树(fullbinarytree)。如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的连续位置上，则此二叉树称作完全二叉树(completebinarytree)。图5.2满二叉树和完全二叉树示例ABCDEFGABDEJKHICFGL(A)满二叉树(b)完全二叉树“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。完全二叉树完全二叉树的特点是：其叶结点只可能在层次最大的两层出现完全二叉树中由根结点到各个结点的路径长度总和在具有同样结点个数的二叉树中达到了最小，即任意一棵二叉树中根结点到各结点的最长路径一定不短于结点数目相同的完全二叉树中的路径长度“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。扩充二叉树在二叉树里出现空子树的位置增加空树叶，所形成的二叉树称为扩充二叉树(extendedbinarytree)构造一棵扩充二叉树只需要在原二叉树里度数为1的分支结点下增加一个空树叶，在原二叉树的树叶下面增加两个新的空树叶。扩充二叉树是满二叉树，新增空树叶(以下称为外部结点)的个数等于原二叉树的结点(以下称为内部结点)个数加1“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。扩充二叉树图5.3扩充二叉树63124971058“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。扩充二叉树从扩充的二叉树的根到每个外部结点的路径长度之和称为外部路径长度(E)。扩充的二叉树里从根到每个内部结点的路径长度之和称为内部路径长度(I)。外部路径长度E和内部路径长度I满足：E=I+2n，其中n是内部结点个数。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二叉树的主要性质性质1.在二叉树中，第i层上最多有2i个结点（i≥0）证明：利用数学归纳法当i=0时，20=1，只有一个根结点，正确。现在假设对所有的j，1≤j＜i，命题成立，即第j层上之多有2j个结点。下面证明当就j=i时结论也成立。由归纳假设，第i-1层上最多有2i-1个结点。由于二叉树每个结点的度数最大为2，所以第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2i个。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二叉树的主要性质性质2.深度为k的二叉树至多有2k+1-1个结点（k≥0）。其中深度(depth)定义为二叉树中层数最大的叶结点的层数。证明：由性质1可知，第i层的最大结点数为2i，所以kiki0221+1＝＝“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二叉树的主要性质性质3.任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设n1为二叉树中度为1的结点数。该二叉树的结点总数n为度分别为0，1，2的结点数之和，即n=n0+n1+n2（公式5.1）除根结点外，其余结点都有一条边进入，设边数为e，有n=e+1。由于这些边是由度为1或2的的结点射出的，所以又有e=n1+2n2，于是得n=e+1=n1+2n2+1（公式5.2）由公式5.1和5.2得n0+n1+n2=n1+2n2+1，即n0=n2+1“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二叉树的主要性质性质4.满二叉树定理：非空满二叉树树叶数目等于其分支结点数加1。证明：满二叉树定理由性质3可直接推出。性质5.满二叉树定理推论：一个非空二叉树的空子树数目等于其结点数加1。证明：设二叉树为T，将其所有空子树换为树叶，记新的扩充满二叉树为T’。所有原来T的结点现在是T’的分支结点。根据满二叉树定理，新添加的树叶数目等于T结点个数加1。而每个新添加的树叶对于T的一个空子树。因此T中空子树的数目等于T中的结点个数加1。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二叉树的主要性质性质6.有n个结点（n0）的完全二叉树的高度为[log2(n+1)]（深度为[log2(n+1)]-1）。其中二叉树的高度(height)定义为二叉树中层数最大的叶结点的层数加1。证明：假设高度为h，则根据性质2和完全二叉树的定义，有或不等式中各项取对数，于是得到。因为h为整数，所以h＝[log2(n+1)]。h-1h21n21h-1h2n+12n12h1logh＋“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二叉树的主要性质性质7.对于具有n个结点的完全二叉树，结点按层次由左到右编号，则对任一结点i（0≤i≤n-1）有（1）如果i=0，则结点i是二叉树的根结点；若i＞0，则其父结点编号是[(i-1)/2]。（2）当2i+1≤n-1时，结点i的左子结点是2i+1，否则结点i没有左子结点。当2i+2≤n-1时，结点i的右子结点是2i+2，否则结点i没有右子结点。（3）当i为偶数且0in时，结点i的左兄弟是结点i-1，否则结点i没有左兄弟。当i为奇数且i+1n时，结点i的右兄弟是结点i+1，否则结点i没有右兄弟。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二叉树的主要性质证明：这里证明(2)，(1)和(3)即可由结论(2)推得。对于i=0，由完全二叉树的定义，其左孩子的编号是1，如果1n-1，即不存在编号为1的结点，此时结点i没有左孩子。其右孩子的编号只能是2，如果2n-1，此时结点i没有右孩子。对于i0分两种情况讨论：(1)设第j层的第一个结点编号为i(此时有i=2j-1)，则其左孩子必为第j+1层的第一个结点，其编号为2j+1-1=2i+1，如果2i+1n-1，那么i没有左孩子；其右孩子必为第j+1层第二个结点，其编号为2i+2。(2)假设第j层的某个结点编号为i，若它有左孩子，那么它的左孩子必然是第j+1层中的第2[i-(2j-1)]个，那么其左孩子的编号就是[2j+1-1]+2[i-(2j-1)]=2i+1；如果结点i有右孩子，那么其右孩子的编号必是2i+2。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。5.2二叉树的抽象数据类型5.2.1抽象数据类型5.2.2深度优先周游二叉树5.2.3广度优先周游二叉树“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。5.2.1抽象数据类型一般情况下需要二叉树的各个结点存储所需要的信息，对二叉树的操作和运算也主要集中在访问二叉树的结点信息上。例如访问某个结点的左子结点、右子结点、父结点，或者访问结点存储的数据。从二叉树的应用角度来看，有时还需要遍历二叉树的每个结点。“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。5.2.1抽象数据类型在二叉树的抽象数据类型中，定义了二叉树基本操作的集合，在具体应用中可以以此为基础进行扩充为了强调抽象数据类型与存储无关，在此并没有具体规定该抽象数据类型的存储方式“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。5.2.1抽象数据类型【代码5.1】二叉树结点的抽象数据类型(ADT)templateclassTclassBinaryTreeNode{friendclassBinaryTreeT;//声明二叉树类为结点类的友元类，以便访问私有数据成员private:Tinfo;//二叉树结点数据域public:BinaryTreeNode();//缺省构造函数BinaryTreeNode(constT&ele);//给定数据的构造函数BinaryTreeNode(constT&ele,BinaryTreeNodeT*l,BinaryTreeNodeT*r);//子树构造结点“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。5.2.1抽象数据类型Tvalue()const;//返回当前结点的数据BinaryTreeNodeT*leftchild()const;//返回当前结点左子树BinaryTreeNodeT*rightchild()const;//返回当前结点右子树voidsetLeftchild(BinaryTreeNodeT*);//设置当前结点的左子树voidsetRightchild(BinaryTreeNodeT*);//设置当前结点的右子树voidsetValue(constT&val);//设置当前结点的数据域boolisLeaf()const;//判断当前结点是否为叶结点BinaryTreeNodeT&operator=(constBinaryTreeNodeT&Node);//重载赋值操作符};“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。5.2.1抽象数据类型【代码5.2】二叉树的抽象数据类型templateclassTclassBinaryTree{private:BinaryTreeNodeT*root;//二叉树根结点public:BinaryTree(){root=NULL;};//构造函数~BinaryTree(){DeleteBinaryTree(root);};//析构函数boolisEmpty()const;//判定二叉树是否为空树BinaryTreeNodeT*Root(){returnroot;};//返回二叉树根结点};“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。5.2.1抽象数据类型BinaryTreeNodeT*Parent(BinaryTreeNodeT*current)