北大数据结构与算法课件04二叉树

数据结构与算法第四章二叉树信息科学与技术学院“数据结构与算法”教学小组北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2主要内容„4.1二叉树的概念„4.2二叉树的主要性质„4.3二叉树的抽象数据类型„4.4周游二叉树„4.5二叉树的实现„4.6二叉搜索树„4.7堆与优先队列„4.8Huffman编码树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page34.1二叉树的概念„4.1.1二叉树的定义及相关概念„4.1.2满二叉树完全二叉树扩充二叉树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4二叉树的定义„树的特例„递归的定义：二叉树由结点的有限集合构成:„或者为空集„或者由一个根结点及两棵不相交的分别称作这个根的左子树和右子树的二叉树(它们也是结点的集合)组成北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5二叉树的五种基本形态(a)空(b)独根(c)空右(d)空左(e)左右都不空„二叉树可以是空集合，因此根可以有空的左子树或右子树，或者左右子树皆为空北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6二叉树的相关术语„结点„根结点、子结点、父结点、左子结点、右子结点„分支结点、叶结点„边„路径、路径长度„祖先、后代„深度、高度、层数、宽度„二叉树的高度定义为二叉树中层数昀大的叶结点的层数加1„二叉树的深度定义为二叉树中层数昀大的叶结点的层数HGEABCDFI北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7满二叉树„如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树ABCDEFGHI树叶两棵非空子树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8完全二叉树ABGCABCFGEDIJLDEHKF„昀多只有昀下面的两层结点度数可以小于2„昀下一层的结点都集中昀左边北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9扩充二叉树„所有空子树，都增加空树叶wimwenyumxulwulxalwanzolwilzomyoxemziyon北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10扩充二叉树„扩充二叉树是满二叉树„新增加的空树叶(外部结点)的个数等于原来二叉树的结点(内部结点)个数加1„路径长度„外部路径长度E从扩充的二叉树的根到每个外部结点的路径长度之和„内部路径长度I扩充的二叉树里从根到每个内部结点的路径长度之和„E和I两个量之间的关系为E=I+2n北京大学信息学院张铭编写©版权所有，转载或翻印必究Page114.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北京大学信息学院张铭编写©版权所有，转载或翻印必究Page124.2二叉树的性质2.满二叉树定理推论：一个非空二叉树的空子树(指针)数目等于其结点数加1。证明：设二叉树T，将其所有空子树换为树叶，记新的扩充满二叉树为T’。所有原来T的结点现在是T’的分支结点。根据满二叉树定理，新添加的树叶数目等于T结点个数加1。而每个新添加的树叶对应T的一个空子树。因此T中空子树数目等于T中结点数加1。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page134.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北京大学信息学院张铭编写©版权所有，转载或翻印必究Page144.2二叉树的性质„4.二叉树的第i层（根为第0层，i≥1）昀多有2i个结点„5.高度为k(深度为k-1。只有一个根结点的二叉树的高度为1，深度为0)的二叉树至多有2k-1个结点„6.有n个结点（n0）的完全二叉树的高度为⎡log2(n+1)⎤(深度为⎡log2(n+1)⎤-1)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page154.3二叉树的抽象数据类型„逻辑结构+运算：„针对整棵树„初始化二叉树„合并两棵二叉树„围绕结点„访问某个结点的左子结点、右子结点、父结点„访问结点存储的数据北京大学信息学院张铭编写©版权所有，转载或翻印必究Page164.3二叉树的抽象数据类型templateclassTclassBinaryTreeNode{//申明二叉树为结点类的友元类，便于访问私有//数据成员friendclassBinaryTree;private:Telement;//二叉树结点数据域//实现时，可以补充private的左右//子结点定义北京大学信息学院张铭编写©版权所有，转载或翻印必究Page174.3二叉树的抽象数据类型public:BinaryTreeNode();//缺省构造函数BinaryTreeNode(constT&ele);//拷贝构造函数//给定了结点值和左右子树的构造函数BinaryTreeNode(constT&ele,BinaryTreeNode*l,BinaryTreeNode*r);Tvalue()const;//返回当前结点的数据//返回当前结点指向左子树BinaryTreeNodeT*leftchild()const;//返回当前结点指向右子树BinaryTreeNodeT*rightchild()const;北京大学信息学院张铭编写©版权所有，转载或翻印必究Page184.3二叉树的抽象数据类型//设置当前结点的左子树voidsetLeftchild(BinaryTreeNode*);//设置当前结点的右子树voidsetRightchild(BinaryTreeNode*);//设置当前结点的数据域voidsetValue(constT&val);//判定当前结点是否为叶结点,若是返回trueboolisLeaf()const;//重载赋值操作符BinaryTreeNodeT&operator=(constBinaryTreeNodeT&Node)};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page194.3二叉树的抽象数据类型„二叉树的抽象数据类型的C++定义BinaryTree，没有具体规定该抽象数据类型的存储方式templateclassTclassBinaryTree{private://二叉树根结点指针BinaryTreeNodeT*root;北京大学信息学院张铭编写©版权所有，转载或翻印必究Page204.3二叉树的抽象数据类型public:BinaryTree();//构造函数~BinaryTree();//析构函数boolisEmpty()const;//判定二叉树是否为空树//返回二叉树根结点BinaryTreeNodeT*Root();//返回current结点的父结点BinaryTreeNodeT*Parent(BinaryTreeNodeT*current);//返回current结点的左兄弟BinaryTreeNodeT*LeftSibling(BinaryTreeNodeT*current);北京大学信息学院张铭编写©版权所有，转载或翻印必究Page214.3二叉树的抽象数据类型//返回current结点的右兄弟BinaryTreeNodeT*RightSibling(BinaryTreeNodeT*current);//以elem作为根结点，leftTree作为树的左子树,//rightTree作为树的右子树，构造一棵新的二叉树voidCreateTree(constT&elem,BinaryTreeT&leftTree,BinaryTreeT&rightTree);//前序周游二叉树或其子树voidPreOrder(BinaryTreeNodeT*root)；//中序周游二叉树或其子树voidInOrder(BinaryTreeNodeT*root)；北京大学信息学院张铭编写©版权所有，转载或翻印必究Page224.3二叉树的抽象数据类型//后序周游二叉树或其子树voidPostOrder(BinaryTreeNodeT*root)；//按层次周游二叉树或其子树voidLevelOrder(BinaryTreeNodeT*root)；//删除二叉树或其子树voidDeleteBinaryTree(BinaryTreeNodeT*root);};北京大学信息学院张铭编写©版权所有，转载或翻印必究Page234.4周游二叉树„周游„系统地访问数据结构中的结点„每个结点都正好被访问到一次„二叉树的结点的线性化北京大学信息学院张铭编写©版权所有，转载或翻印必究Page244.4周游二叉树„二叉树周游„4.4.1深度优先周游二叉树„4.4.2非递归深度优先周游二叉树„4.4.3广度优先周游二叉树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page25深度优先周游二叉树变换根结点的周游顺序，得到三种方案：①前序周游(tLR次序)：访问根结点；前序周游左子树；前序周游右子树。②中序周游(LtR次序)：中序周游左子树；访问根结点；中序周游右子树。③后序周游(LRt次序)：后序周游左子树；后序周游右子树；访问根结点。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page26„①前序周游：ABDCEGFHI„②中序周游：DBAEGCHFI„③后序周游：DBGEHIFCAHGEABCDFI北京大学信息学院张铭编写©版权所有，转载或翻印必究Page27深度优先周游二叉树（递归）templateclassTvoidBinaryTreeT::DepthOrder(BinaryTreeNodeT*root)｛if(root!=NULL){DepthOrder(root-leftchild());//访问左子树DepthOrder(root-rightchild());//访问右子树}｝Visit(root);//前序Visit(root);//中序Visit(root);//后序北京大学信息学院张铭编写©版权所有，转载或翻印必究Page284.4周游二叉树„二叉树周游„4.4.1深度优先周游二叉树„4.4.2非递归深度优先周游二叉树„4.4.3广度优先周游二叉树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page29非递归深度优先周游二叉树„深度优先二叉树周游是递归定义的„栈是实现递归的昀常用的结构„记下尚待周游的结点或子树„以备以后访问北京大学信息学院张铭编写©版权所有，转载或翻印必究Page30非递归前序周游二叉树——简洁„思想：„遇到一个结点，就访问该结点，并把此结点的非空右结点推入栈中，然后下降去周游它的左子树；„周游完左子树后，从栈顶托出一个结点，并按照它的右链接指示的地址再去周游该结点的右子树结构。templateclassTvoidBinaryTreeT::PreOrderWithoutRecusion(BinaryTreeNodeT*root)//非递归前序遍历二叉树或其子树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page31非递归前序周游二叉树{usingstd::stack;//使用STL中的stackstackBina