四章节二叉树.ppt
《四章节二叉树.ppt》由会员分享,可在线阅读,更多相关《四章节二叉树.ppt(162页珍藏版)》请在三一文库上搜索。
1、第四章 二叉树,任课教员:张 铭 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
2、 4,二叉树的定义,二叉树由结点的有限集合构成: 或者为空集 或者由一个根结点及两棵不相交的分别称作这个根的左子树和右子树的二叉树(它们也是结点的集合)组成 这是个递归的定义。二叉树可以是空集合,因此根可以有空的左子树或右子树,或者左右子树皆为空,北京大学信息学院 版权所有,转载或翻印必究 Page 5,二叉树的五种基本形态,(a)空 (b)独根 (c)空右 (d)空左 (e)左右都不空,北京大学信息学院 版权所有,转载或翻印必究 Page 6,满二叉树,如果一棵二叉树的任何结点,或者是树叶,或者恰有两棵非空子树,则此二叉树称作 满二叉树,北京大学信息学院 版权所有,转载或翻印必究 Page
3、7,完全二叉树,若一颗二叉树 最多只有最下面的两层结点度数可以小于2 最下面一层的结点都集中在该层最左边的若干位置上, 则称此二叉树为完全二叉树 在许多算法和算法分析中都明显地或隐含地用到完全二叉树的概念,北京大学信息学院 版权所有,转载或翻印必究 Page 8,完全二叉树,北京大学信息学院 版权所有,转载或翻印必究 Page 9,扩充二叉树,当二叉树里出现空的子树时,就增加新的、特殊的结点空树叶 对于原来二叉树里度数为1的分支结点,在它下面增加一个空树叶 对于原来二叉树的树叶,在它下面增加两个空树叶 扩充的二叉树是满二叉树,新增加的空树叶(外部结点)的个数等于原来二叉树的结点(内部结点)个数
4、加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) 每个分支,恰有两个子结
5、点(满),故有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的一个空子树。
6、 因此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 +
7、 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 二叉树的深度定义为二叉树中层数最大的叶结点的层数,北京大学信息学院 版权所有,转
8、载或翻印必究 Page 17,4.3 二叉树的抽象数据类型,定义了二叉树的逻辑结构之后,我们需要考虑在二叉树逻辑结构之上的各种可能运算,这些运算应该适合二叉树的各种应用 : 二叉树的某些运算是针对整棵树的 初始化二叉树 合并两棵二叉树 二叉树的大部分运算都是围绕结点进行的 访问某个结点的左子结点、右子结点、父结点 访问结点存储的数据。,北京大学信息学院 版权所有,转载或翻印必究 Page 18,4.3 二叉树的抽象数据类型,二叉树结点抽象数据类型BinaryTreeNode是带有参数 T 的模板,T是存储在结点中的数据类型 每个元素结点都有leftchild()和rightchild()左右子
9、结点结构 另外每个结点还包含一个数据域value()。 为了强调抽象数据类型与存储无关,我们并没有具体规定该抽象数据类型的存储方式,北京大学信息学院 版权所有,转载或翻印必究 Page 19,4.3 二叉树的抽象数据类型,template class BinaryTreeNode /申明二叉树为结点类的友元类,便于访问私有 /数据成员 friend class BinaryTree; private: /二叉树结点数据域 T element; / 实现时,可以补充private的左子结点 /右子结点定义,北京大学信息学院 版权所有,转载或翻印必究 Page 20,4.3 二叉树的抽象数据类型,
10、public: BinaryTreeNode(); /缺省构造函数 BinaryTreeNode(const T,北京大学信息学院 版权所有,转载或翻印必究 Page 21,4.3 二叉树的抽象数据类型,/设置当前结点的左子树 void setLeftchild(BinaryTreeNode*) ; /设置当前结点的右子树 void setRightchild(BinaryTreeNode*) ; /设置当前结点的数据域 void setValue(const T,北京大学信息学院 版权所有,转载或翻印必究 Page 22,4.3 二叉树的抽象数据类型,二叉树的抽象数据类型的C+定义Binar
11、yTree,没有具体规 定该抽象数据类型的存储方式 template class BinaryTree private: /二叉树根结点指针 BinaryTreeNode* root; /从二叉树的root结点开始 /查找current结点的父结点 BinaryTreeNode* GetParent(BinaryTreeNode* root, BinaryTreeNode* current);,北京大学信息学院 版权所有,转载或翻印必究 Page 23,4.3 二叉树的抽象数据类型,public: BinaryTree(root=NULL); /构造函数 BinaryTree() Delete
12、BinaryTree(root);/析构函数 bool isEmpty() const; /判定二叉树是否为空树 /返回二叉树根结点 BinaryTreeNode* Root()return root; /返回current结点的父结点 BinaryTreeNode* Parent(BinaryTreeNode* current); /返回current结点的左兄弟 BinaryTreeNode* LeftSibling( BinaryTreeNode* current);,北京大学信息学院 版权所有,转载或翻印必究 Page 24,4.3 二叉树的抽象数据类型,/返回current结点的右兄
13、弟 BinaryTreeNode* RightSibling( BinaryTreeNode* current); / 以elem作为根结点,leftTree作为树的左子树, /rightTree作为树的右子树,构造一棵新的二叉树 void CreateTree(const T /前序周游二叉树或其子树 void PreOrder(BinaryTreeNode* root); /中序周游二叉树或其子树 void InOrder(BinaryTreeNode* root);,北京大学信息学院 版权所有,转载或翻印必究 Page 25,4.3 二叉树的抽象数据类型,/后序周游二叉树或其子树 voi
14、d PostOrder(BinaryTreeNode* root); /按层次周游二叉树或其子树 void LevelOrder(BinaryTreeNode* root); /删除二叉树或其子树 void DeleteBinaryTree(BinaryTreeNode* root); ;,北京大学信息学院 版权所有,转载或翻印必究 Page 26,4.4 周游二叉树,周游 系统地访问数据结构中的结点。每个结点都正好被访问到一次。 周游一棵二叉树的过程实际上就是把二叉树的结点放入一个线性序列的过程,或者说把二叉树进行线性化,北京大学信息学院 版权所有,转载或翻印必究 Page 27,4.4 周
15、游二叉树,二叉树周游 4.4.1 深度优先周游二叉树 4.4.2 非递归深度优先周游二叉树 4.4.3 广度优先周游二叉树,北京大学信息学院 版权所有,转载或翻印必究 Page 28,深度优先周游二叉树,我们变换一下根结点的周游顺序,可以得到以下三种方案: 前序周游(tLR次序):访问根结点;前 序周游左子树;前序周游右子树。 中序周游(LtR次序):中序周游左子 树;访问根结点;中序周游右子树。 后序周游(LRt次序):后序周游左子 树;后序周游右子树;访问根结点。,北京大学信息学院 版权所有,转载或翻印必究 Page 29,深度优先周游二叉树,深度周游如下二叉树,北京大学信息学院 版权所有
16、,转载或翻印必究 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()
17、;/访问右子树 Visit(root); /后序 ,北京大学信息学院 版权所有,转载或翻印必究 Page 32,非递归深度优先周游二叉树,栈是实现递归的最常用的结构 深度优先二叉树周游是递归定义的 利用一个栈来记下尚待周游的结点或子树,以备以后访问。,北京大学信息学院 版权所有,转载或翻印必究 Page 33,非递归前序周游二叉树,思想: 遇到一个结点,就访问该结点,并把此结点推入栈中,然后下降去周游它的左子树; 周游完它的左子树后,从栈顶托出这个结点,并按照它的右链接指示的地址再去周游该结点的右子树结构。 template void BinaryTree:PreOrderWithoutRec
18、usion (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,非
19、递归前序周游二叉树,/当前链接结构指向左孩子 pointer=pointer-leftchild(); else /左子树访问完毕,转向访问右子树 pointer=aStack.top(); aStack.pop(); /栈顶元素退栈 /当前链接结构指向右孩子 pointer=pointer-rightchild(); /end while ,北京大学信息学院 版权所有,转载或翻印必究 Page 36,非递归中序周游二叉树,思想: 遇到一个结点,就把它推入栈中,并去周游它的左子树 周游完左子树后,从栈顶托出这个结点并访问之,然后按照它的右链接指示的地址再去周游该结点的右子树。 template
20、 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-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 章节 二叉
链接地址:https://www.31doc.com/p-3195532.html