《数据结构与程序设计(24)二叉树》由会员分享，可在线阅读，更多相关《数据结构与程序设计(24)二叉树（38页珍藏版）》请在金锄头文库上搜索。
1、8/2/2024数据结构与程序设计 1Treen树tree的定义n (1) 无结点的树 空树 n (2) 非空树n 仅有一个根结点n 其余结点分为若干n 互不相交的子树n在树形结构中每个结点最多只有一个前驱，但可有多个后继的结构。它表示了一种具有层次的分支关系。 8/2/2024数据结构与程序设计 2subtreeTreenRoot（根）（根）: node without parent (A)nSiblings（兄弟）（兄弟）: nodes share the same parentnInternal node: node with at least one child (A, B, C, F
2、)nExternal node (leaf ): node without children (E, I, J, K, G, H, D)nAncestors of a node: parent, grandparent, grand-grandparent, etc.nDescendant of a node: child, grandchild, grand-grandchild, etc.nDepth of a node: number of ancestorsnHeight of a tree: maximum depth of any node (3)nDegree of a node
3、: the number of its childrennDegree of a tree: the maximum number of its node.ABDCGHEFIJKnSubtree: tree consisting of a node and its descendants8/2/2024数据结构与程序设计 3Tree PropertiesABCDGEFIHPropertyValueNumber of nodes 9Height 4 Root Node ALeaves Interior nodesAncestors of H （G，E，B，A）Descendants of BSi
4、blings of ERight subtree of ADegree of this tree8/2/2024数据结构与程序设计 4Chapter 10 Binary Tree nDEFINITION A binary tree is either empty, or it consists of a node called the root （根）together with two binary trees called the left subtree (左子树) and the right subtree （右子树）of the root.8/2/2024数据结构与程序设计 5二叉树二
5、叉树 (Binary Tree)二叉树的定义二叉树的定义二叉树的五种不同形态二叉树的五种不同形态 一棵二叉树是结点的一个有限集合，该集合一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。为左子树和右子树的、互不相交的二叉树组成。8/2/2024数据结构与程序设计 6深度(Height)为k，结点至多2k+1-1个，深度为最大层数第i层结点至多2i个 在本书，层数从0开始计算。设有n2个2度点则有n2+1个叶片ABCDEFGH I J8/2/2024数据结构与程序设计 7Binary
6、 Treen满二叉树：满二叉树：如果一棵二叉树的如果一棵二叉树的深度为深度为k,结点数结点数2k+1-1,每层结点数都最大每层结点数都最大，则此二叉树称作满，则此二叉树称作满二叉树。二叉树。n完全二叉树：完全二叉树：如果一棵二叉树至多只有最下面如果一棵二叉树至多只有最下面的两层结点度数可以小于的两层结点度数可以小于2，其余各层结点度，其余各层结点度数都必须为数都必须为2，并且最下面一层的结点都集中，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为在该层最左边的若干位置上，则此二叉树称为完全二叉树。即为，完全二叉树。即为，满二叉树去掉最下层最右满二叉树去掉最下层最右边若干结点边
7、若干结点8/2/2024数据结构与程序设计 8Binary Tree8/2/2024数据结构与程序设计 9ABCDEFGH I J完全二叉树完全二叉树K LMn个结点个结点,深度深度 k=log2(n) 下取整下取整n个结点,深度为k:2k-1n2k+1-12k n 2k+1k log2n k+1k=log2(n) 下取整下取整1个结点深度为个结点深度为02-3个结点深度为个结点深度为14-7个结点深度为个结点深度为2 8-15个结点深度为个结点深度为3 8/2/2024数据结构与程序设计 10 0123456 7 89完全二叉树完全二叉树101112结点结点i的左子结点是的左子结点是2i+1
8、 右子结点是右子结点是2i+2结点结点i的父结点是的父结点是(i-1)/2堆排序利用了这种特点。堆排序利用了这种特点。8/2/2024数据结构与程序设计 1110.1.2 Traversal of Binary TreesnWith preorder traversal （前序）we first visit a node, then traverse its left subtree, and then traverse its right subtree.nWith inorder traversal （中序）we first traverse the left subtree, then
9、visit the node, and then traverse its right subtree.nWith postorder traversal（后序） we first traverse the left subtree, then traverse the right subtree, and finally visit the node.8/2/2024数据结构与程序设计 12写出这棵树的前序，后序，中序访问的结果8/2/2024数据结构与程序设计 13前序遍历 (Preorder Traversal)前序遍历二叉树算法的框架是前序遍历二叉树算法的框架是n n若二叉树为空，则空
10、操作；若二叉树为空，则空操作；n n否则否则n n访问根结点访问根结点访问根结点访问根结点 (V)(V)；n n前序遍历左子树前序遍历左子树前序遍历左子树前序遍历左子树 (L)(L)；n n前序遍历右子树前序遍历右子树前序遍历右子树前序遍历右子树 (R)(R)。遍历结果遍历结果遍历结果遍历结果- - + a * b - - c d / e f8/2/2024数据结构与程序设计 14中序遍历二叉树算法的框架是：中序遍历二叉树算法的框架是：n n若二叉树为空，则空操作；若二叉树为空，则空操作；n n否则否则n n中序遍历左子树中序遍历左子树中序遍历左子树中序遍历左子树 (L)(L)；n n访问根结
11、点访问根结点访问根结点访问根结点 (V)(V)；n n中序遍历右子树中序遍历右子树中序遍历右子树中序遍历右子树 (R)(R)。遍历结果遍历结果遍历结果遍历结果 a + b * c - - d - - e / f中序遍历 (Inorder Traversal)表达式语法树表达式语法树8/2/2024数据结构与程序设计 15后序遍历 (Postorder Traversal)后序遍历二叉树算法的框架是后序遍历二叉树算法的框架是n n若二叉树为空，则空操作；若二叉树为空，则空操作；n n否则否则n n后序遍历左子树后序遍历左子树后序遍历左子树后序遍历左子树 (L)(L)；n n后序遍历右子树后序遍历
12、右子树后序遍历右子树后序遍历右子树 (R)(R)；n n访问根结点访问根结点访问根结点访问根结点 (V)(V)。遍历结果遍历结果遍历结果遍历结果a b c d - - * + e f / - -8/2/2024数据结构与程序设计 16完全二叉树的数组表示完全二叉树的数组表示 一般二叉树的数组表示一般二叉树的数组表示二叉树的表示二叉树的表示 1.数组表示数组表示8/2/2024数据结构与程序设计 17二叉树的表示二叉树的表示2. 链表表示链表表示8/2/2024数据结构与程序设计 1810.1.3 二叉树的链式实现二叉树的链式实现8/2/2024数据结构与程序设计 19Implement of
13、Binary Tree链式实现方式链式实现方式-节点的数据结构节点的数据结构ntemplate nstruct Binary_node n/ data members:nEntry data;nBinary_node *left; /指向左孩子的指针指向左孩子的指针nBinary_node *right; /指向右孩子的指针指向右孩子的指针n/ constructors:nBinary_node( ); /默认的不带参数的构造函数默认的不带参数的构造函数nBinary_node(const Entry &x); /带有一个参数的构造函数带有一个参数的构造函数n;8/2/2024数据结构与程序设
14、计 20Implement of Binary Tree链式实现方式链式实现方式-节点的实现节点的实现n#include Binary_node.hntemplate nBinary_node : Binary_node()nleft = NULL;nright = NULL;nntemplate nBinary_node : Binary_node(const Entry &x)ndata = x;nleft = NULL;nright = NULL;n8/2/2024数据结构与程序设计 21二叉树的基本方法n1. 遍历nvoid preorder(void (*visit)(Entry &
15、);nvoid inorder(void (*visit)(Entry &);nvoid postorder(void (*visit)(Entry &);n2. 访问方法访问方法nbool empty( ) const;nint size( ) const;nint height( ) const; /求高度求高度8/2/2024数据结构与程序设计 22二叉树的基本方法n3. 更新操作nvoid insert(Entry &);n/插入一个新的节点n4. 构造二叉树nBinary_tree( );n/构造函数。8/2/2024数据结构与程序设计 23Implement of Binary T
16、ree链式实现的头文件链式实现的头文件n#include Binary_node.cppntemplate nclass Binary_tree npublic:nBinary_tree( );nbool empty( ) const;nvoid preorder(void (*visit)(Entry &);nvoid inorder(void (*visit)(Entry &);nvoid postorder(void (*visit)(Entry &);nint size( ) const;nint height( ) const;nvoid insert(Entry &);8/2/20
17、24数据结构与程序设计 24Implement of Binary Tree二叉树定义的头文件二叉树定义的头文件nprotected:n/ Add auxiliary function prototypes here.nvoid recursive_preorder(Binary_node *sub_root, void (*visit)(Entry &);nvoid recursive_inorder(Binary_node *sub_root, void (*visit)(Entry &);nvoid recursive_postorder(Binary_node *sub_root, v
18、oid (*visit)(Entry &);nBinary_node *root; /二叉树的根节点二叉树的根节点nint count;n;8/2/2024数据结构与程序设计 25Implement of Binary Tree构造函数的实现构造函数的实现ntemplate nBinary_tree : Binary_tree( )n/* Post: An empty binary tree has been created. */nnroot = NULL;ncount = 0;nntemplate nbool Binary_tree : empty( ) constn/* Post: A
19、result oftrue is returned if the binary tree is empty. Otherwise,false isnreturned. */nnreturn root = NULL;n8/2/2024数据结构与程序设计 26Implement of Binary Tree二叉树的前序遍历二叉树的前序遍历ntemplate nvoid Binary_tree : preorder(void (*visit)(Entry &)nnrecursive_preorder(root, visit);nntemplate nvoid Binary_tree : recurs
20、ive_preorder(Binary_node *sub_root, void (*visit)(Entry &)nnif (sub_root != NULL) n(*visit)(sub_root-data);nrecursive_preorder(sub_root-left, visit);nrecursive_preorder(sub_root-right, visit);n n8/2/2024数据结构与程序设计 27Implement of Binary Tree二叉树的中序遍历二叉树的中序遍历ntemplate nvoid Binary_tree : inorder(void (*
21、visit)(Entry &)nnrecursive_inorder(root, visit);nntemplate nvoid Binary_tree : recursive_inorder(Binary_node *sub_root, void (*visit)(Entry &)nnif (sub_root != NULL) nrecursive_inorder(sub_root-left, visit);n(*visit)(sub_root-data);nrecursive_inorder(sub_root-right, visit);n n8/2/2024数据结构与程序设计 28Imp
22、lement of Binary Tree二叉树的后序遍历二叉树的后序遍历ntemplate nvoid Binary_tree : postorder(void (*visit)(Entry &)nnrecursive_postorder(root, visit);nntemplate nvoid Binary_tree : recursive_postorder(Binary_node *sub_root, void (*visit)(Entry &)nnif (sub_root != NULL) nrecursive_postorder(sub_root-left, visit);nre
23、cursive_postorder(sub_root-right, visit);n(*visit)(sub_root-data);n n8/2/2024数据结构与程序设计 29Implement of Binary Tree求二叉树的高度求二叉树的高度n假设当前二叉树为一棵完全二叉树，则如何求其高度？假设当前二叉树为一棵完全二叉树，则如何求其高度？n启发，根据前面的讨论，设二叉树的节点数为启发，根据前面的讨论，设二叉树的节点数为n,，完，完全二叉树的高度为：全二叉树的高度为：log2n的值下取整。的值下取整。n则有则有2K=n; k为满足条件的最大整数为满足条件的最大整数n实现方法：实现方法
24、：nK=0；tmp=20n当当tmp = n时，时， K= K+1，tmp= tmp*2；/ 2Kn退出循环时退出循环时K的值，即为完全二叉树的高度。的值，即为完全二叉树的高度。8/2/2024数据结构与程序设计 30Implement of Binary Tree求二叉树的高度求二叉树的高度ntemplate nint Binary_tree : size( ) constnnreturn count;nntemplate /该方法适用于完全二叉树，当前的对象必须为完全二叉树。该方法适用于完全二叉树，当前的对象必须为完全二叉树。nint Binary_tree : height( ) con
25、st nnint count=size();nif(count=0)return 0;nint tmp=1;nfor(int k=0; tmp=count; k+) tmp*=2;nreturn k;n8/2/2024数据结构与程序设计 31插入：新插入的节点在最后一个叶子结插入：新插入的节点在最后一个叶子结点之后点之后012345678结点结点i的左子结点是的左子结点是2i+1 右子结点是右子结点是2i+2结点结点i的父结点是的父结点是(i-1)/28/2/2024数据结构与程序设计 32插入：新插入的节点在最后一插入：新插入的节点在最后一个叶子结点之后个叶子结点之后n如何在完全二叉树的末尾
26、插入一个新的节点：如何在完全二叉树的末尾插入一个新的节点：只需要只需要知道插入位置的父节点的信息即可，即父节点的指针。知道插入位置的父节点的信息即可，即父节点的指针。n如何获取父节点的信息：如何获取父节点的信息：必须从根节点一层一层访问，必须从根节点一层一层访问，获取父节点的信息。获取父节点的信息。n实现实现:(1)当前插入点的编号当前插入点的编号tmpcount = size();n(2) 计算计算tmpcount是左孩子还是右孩子。将信息入栈保存是左孩子还是右孩子。将信息入栈保存;n(3) 计算计算tmpcount的父节点，的父节点， tmpcount= (tmpcount -1)/2;n
27、(4) 当当tmpcount不是根节点，继续步骤不是根节点，继续步骤(2);n经过上述计算之后，栈内保存了从根到插入点的路径。经过上述计算之后，栈内保存了从根到插入点的路径。n(5) 依次将信息出栈，逐一访问路径上的节点，获取父节点的依次将信息出栈，逐一访问路径上的节点，获取父节点的指针。指针。n(6) 将当前信息插入到树中。将当前信息插入到树中。 8/2/2024数据结构与程序设计 33插入：新插入的节点在最后一插入：新插入的节点在最后一个叶子结点之后个叶子结点之后ntemplate nvoid Binary_tree : insert(Entry &x)n/新插入的节点在最后一个叶子节点之
28、后，因此用该方新插入的节点在最后一个叶子节点之后，因此用该方/法构造的树为完全二叉树。法构造的树为完全二叉树。nif(empty() /为空的情况为空的情况nroot=new Binary_node(x);ncount+;nreturn;n8/2/2024数据结构与程序设计 34Implement of Binary Treen MyStack numbers;n int item=0;n int tmpcount=size();n while(tmpcount0)n if(tmpcount%2=0)/the node is right childn numbers.push(2);/2 st
29、and for right childn n else/the node is left childn numbers.push(1);/1 stand for left childn n tmpcount=(tmpcount-1)/2;/get to the parentn8/2/2024数据结构与程序设计 35Implement of Binary TreenBinary_node *current=root;nwhile (numbers.size()1) /出栈，直到栈内剩余一个节点出栈，直到栈内剩余一个节点nnumbers.top(item); n if(item=1)current
30、=current-left;nif(item=2)current=current-right;n numbers.pop();n nnumbers.top(item); /链接新节点链接新节点nif(item=1)current-left=new Binary_node(x);nif(item=2)current-right=new Binary_node(x);ncount+;n8/2/2024数据结构与程序设计 36Implement of Binary Treentemplate nvoid print(Entry &x)ncoutx;nnvoid main()nBinary_tree
31、mytree;nfor(int i=0; i10; i+)mytree.insert(Record(i);ncoutTree size is: mytree.size()endl;ncoutTree height is: mytree.height()endl;ncoutPreorder:endl;nmytree.preorder(print);ncoutendl;ncoutinorder:endl;nmytree.inorder(print);ncoutendl;ncoutPostorder:endl;nmytree.postorder(print);ncoutendl;ncin.get();n8/2/2024数据结构与程序设计 37Implement of Binary Treen目录目录Binary_Tree下例程下例程nTree size is: 10nTree height is: 4nPreorder:n0 1 3 7 8 4 9 2 5 6ninorder:n7 3 8 1 9 4 0 5 2 6nPostorder:n7 8 3 9 4 1 5 6 2 001234567898/2/2024数据结构与程序设计 38课后作业 P441n（1）E5 用递归的方法计算二叉树的叶子节点数。n（2）E6 用递归的方法计算二叉树的高度。
