《数据结构——树的概念和二叉树》由会员分享，可在线阅读，更多相关《数据结构——树的概念和二叉树（88页珍藏版）》请在金锄头文库上搜索。
1、第四章 树的概念和二叉树吉林大学计算机学院 谷方明 4.1 树的基本概念p树是一种非常重要的非线性数据结构，可用来 描述客观世界中中广泛存在的具有分支或层次关 系的对象。1. 树的定义(递归版)定义4.1： 一棵树（或树形）是一个有限非空的结点 集合T，其中：有一个被称为根的结点，记为root(T) ；其余结点被分成m 0 个不相交的集合T1，T2， ，Tm，且T1，T2，Tm又都是树。树T1，T2，Tm称作root(T)的子树，每一棵子 树的根都和root(T)有一条边连接。AECDBIHGF定义4.2 （非递归版）树是包含n ( n 1 )个结点有限集合，满足如下条件：存在一个唯一的结点v
2、0，没有前驱结点，称为树的根（或根结点）；任一非根结点都有且仅有一个前驱结点，称为该结点的 父结点；（任何结点都可能有零或多个后继结点，称之为 该结点的子结点）任一非根结点vk都有且仅有一条从v0到该结点的路径： v0 v1 vk，其中vi是vi1（1 i k）的子结点。2. 树的相关术语度一个结点的子结点的数目，称为该结点的度 。一棵树的度为maxi=1, n D (i)，其中n为树中结 点总数，i指树中的第i个结点，D(i)表结点i的度 。叶结点、分支结点度为0的结点被称为叶结点；度大于0的结点 被称为分支结点。结点的层数 root(T)层数为零； 其余结点的层数为其前驱结点的层数加 1；
3、树的高度树的高度是指树中结点的最大层数，即 maxi=1, n NL (i)，其中n为树中结点总数，i指树 中第i个结点，NL(i)之值为结点i的层数。 路径若树T中存在结点序列v1 v2 vk，满足(vi , vi+1 )是树的边，则称此结点序列为v1到vk的路径。路径所经历的边数被称为路径长度。子孙结点、祖先结点、兄弟结点一棵树中若存在结点vm到vn的路径，则称vn为vm的 子孙结点，vm为vn的祖先结点。同一个父亲的诸子结点称为兄弟结点。树作为无向图的性质p有n-1条边；p连通p无环树的等价定义p连通无环图（自由树或无根树，没有确定根， 选定一顶点作根，则成为一棵通常的树）pn-1 条边
4、的连通图（归纳、必有度为1的点）pn-1 条边的无环图（归纳、每个连通分支）3、树在计算机领域有广泛的应用p操作系统中，文件及文件夹的存储，软件的菜 单等都是树；p在分析算法时，可用树来描述其执行过程，如 递归调用、搜索等；p4.2 二叉树p定义4.3：二叉树是结点的有限集合，它或者 是空集，或者由一个根及左、右两个不相交的的 二叉树构成。这两棵子树分别称为左、右子树。树与二叉树的主要区别二叉树每个结点最多有 2 个子结点，树则无此限 制； 二叉树中结点的子树分成左子树和右子树，即使 某结点只有一棵子树，也要指明该子树是左子树， 还是右子树，即二叉树是有序的； 树决不能为空（换言之树不能为空集
5、），它至少 有一个结点，而一棵二叉树可以是空的（或者说二 叉树可以为空集）。A(a) (b) (c) (d) (e)ACBACBCBACBACB含有3个结点的不同二叉树引理4.1 二叉树中层数为i的结点至多有2i个，i 0。引理4.2 高度为k的二叉树中至多有2k+1-1 (k 0)个结点。引理4.3 p设T是由n个结点构成的二叉树，其中叶子结 点个数为n0，度为2的结点个数为n2，则有：n0 n21证明：设度为1的结点有n1个，总结点个数为n，总边数 为e，则：n=n0+n1+n2 (1) e=n-1 (2)e=2n2+n1 (3)因此，有n0+n1+n2-1=2n2+n1n0=n2+1证毕
6、。满二叉树p定义4.4 一棵非空高度为k( k 0)的满二叉树， 是有2k+11个结点的二叉树。156437298101311121415满二叉树的特点p 叶结点都在第k层上；p 每个分支结点都有两个子结点；p 叶结点的个数等于非叶结点个数加1完全二叉树p定义4.5 一棵包含n个结点高为k的二叉树T， 当按层次顺序编号T的所有结点，对应于一棵高 为k的满二叉树中编号由1至n的那些结点时，T 被称为完全二叉树。56437298101完全二叉树的特点p树中叶结点只能在层数最大的两层上出现；树 中最下一层的结点都集中在该层最左边的若干位 置上；p仅仅编号最大的分支结点可以没有右孩子，其 余分支结点都
7、有两个孩子；引理4.4 p若将一颗具有n个结点的完全二叉树按层次次序从1开 始编号，则对编号为i (1i n)的结点有： 若i1，则编号为i的结点的父结点的编号为 i/2 。若2in，则编号为i的结点的左孩子的编号为 2i ，否则 i 无左孩子。若2i+1n，则i结点的右孩子结点编号为2i+1， 否则 i 无右孩子。引理4.5 p具有n个结点的完全二叉树的高度是 log2n2 二叉树的顺序存储p将二叉树中所有结点按层次顺序存放在一块地 址连续的存储空间中，同时反映出二叉树中结点 间的逻辑关系。完全二叉树的顺序存储31 23 12 66 94 17 5 70 62 49 171252362704
8、9316694p 一般二叉树也可仿照完全二叉树那样存储。 但可能会浪费很多存储空间。CB A 25731a1a2 a3a4a5 A B a6 a7C二叉树的链接存储p二叉树诸结点被随机存放在内存空间中，结点 之间的关系用指针说明。p 二叉树的结点结构二叉树结点包含三个域：数据域data、指针 域left和指针域right，其中左、右指针分别指向该结点的左、右孩子结点.leftright dataADCBEFGACBEFDGrootp在二叉树的链接存储中，有一个指向根结点的 指针，称为根指针。若二叉树为空，根指针为 NULL.p空指针域个数：2n - (n-1)三叉链p另一种常用的结点结构包括三
9、个指针域， parent域中指针指向其父结点leftdataparentright二叉树的遍历p二叉树树的遍历历：按照一定次序访问树访问树 中所有 结结点，且使每个结结点恰好被访问访问 一次。p先根(中根、后根)序列：以先根(中根、后根) 次序遍历二叉树 T, 得到 T 之结点的一个序列遍历方式先根遍历： DLR中根遍历： LDR后根遍历： LRDDRL先根遍历 (前/先序遍历)p若二叉树为空，则返回空；p否则访问根结点；先根遍历左子树；先根遍历右子树。遍历结果 ABCDEFABDFCE先根遍历算法算法PreOrder(t) /* 先根遍历 t 指向的树*/ P1 递归遍历if (t != N
10、ULL) coutData Left);PreOrder(t-Right); 中根遍历(中序遍历)p若二叉树为空，则空操作；p否则中根遍历左子树；访问根结点；中根遍历右子树。遍历结果 BDCAFEABDFCE中根遍历算法算法InOrder(t) /* 中根遍历 t 指向的树*/ I1 递归遍历if (t != NULL) InOrder(t-Left);coutData Right); 后根遍历 (后序遍历)p若二叉树为空，则空操作；p否则后根遍历左子树；后根遍历右子树；访问根结点。遍历结果 DCBFEAABDFCE后根遍历算法算法PostOrder(t) /* 后根遍历 t 指向的树*/ I
11、1 递归遍历if (t != NULL) PostOrder(t-Left);PostOrder(t-Right);cout Data Left ; NIO3. 栈为空? if ( S.empty() return; else p = S.pop ( ) ; NIO4. 访问p，更新pcoutData ; p = p- Right ; NIO5. 返回goto NIO2 ;p定理4.1：正确性证明p非递归的先根遍历算法，与非递归的中根遍历 算法类似；（区别在于输出语句的位置不同）非递归的后根遍历算法p先根和中根遍历的非递归算法，一个结点仅进 栈出栈一次，我们能够判断其输出语句的位置， 分别为结
12、点进栈前及出栈后。p而后根遍历输出结点的位置应为处理完右子树 之后，如果每个结点还是进栈、出栈一次，则无 法确定何时输出结点，即其左右子树是否已处理 完。pp设置一个工作栈：设置一个工作栈：结点所处状态结点所处状态i = 0, 1i = 0, 1或或2 2：0 0：结点及左右子树均未被访问；：结点及左右子树均未被访问；1 1：遍历左子树；：遍历左子树；2 2：遍历右子树。：遍历右子树。pp树中任一结点树中任一结点q q都需进栈三次，出栈三次。第一次出都需进栈三次，出栈三次。第一次出 栈是为遍历结点栈是为遍历结点q q的左子树，第二次出栈是为遍历结点的左子树，第二次出栈是为遍历结点q q 的右子
13、树，第三次出栈是为访问结点的右子树，第三次出栈是为访问结点q . q . 结点 结点状态 i算法思想1) 将(根结点,0)压入堆栈。 2) 弹栈，对出栈元素(p, i )中标号i进行判断， 若 i0，则将(p,1)压入堆栈；若结点p的左指针 不为空，则将(Left(p), 0) 压入堆栈，准备遍历其 左子树.若 i1，此时已遍历完结点p的左子树，则将 (p,2)压入堆栈；若右指针不为空，则将(Right(p), 0)压入堆栈，准备遍历其右子树.若 i2，此时已遍历完结点p的右子树，访问结 点p.算法NPostOrder(t)NPO1建立堆栈CREATStack S; S (t,0); NPO3
14、利用栈实现递归while( ! s.empty() (P,i) S;if ( i=0 ) S (P,1);if ( p-Left != NULL ) S (p-Left,0) ; if ( i=1 ) S (P,2);if ( p-Right != NULL ) S (p-Right,0) ; if ( i=2 ) coutData ; 二叉树的层次遍历p按层数由小到大，同层由左向右的次序访问结 点。遍历结果:A B E C F DABDFCEp二叉树层次遍历算法需要一个辅助队列p根结点入队.p重复本步骤直至队为空:若队非空，取队头结点并访问；若其左指针不空，将其左孩子入队；若其右指针不空，将
15、其右孩子入队.ABDFCE算法LevelOrder ( t )LevelOrder1. 初始化CREATEQuene Q ; p =t ; if ( p!=NULL ) Q p ;LevelOrder 2. 层次遍历while (!Q.empty() ) p Q .cout Data Left != NULL ) Q p - Left ; if ( p- Right != NULL ) Q p - Right ; 创建二叉树p先根序列不能唯一确定二叉树之结构，两棵不 同的二叉树却可能有相同的先根序列。p先根序列和中根序列可以唯一确定一棵二叉树 。 例 先根序列 A B C K D E H F中根序列 B K C A H E D FAB C KD E H FABEDCKFHABDC KE HFp后根序列和中根序列可以唯一确定一棵二叉树 。 例 后根序列 C E F D B H G A 中根序列 C B E D F A G HAC B E D FG HABCD
