[信息与通信]数据结构chapter 6 树和二叉树.ppt
《[信息与通信]数据结构chapter 6 树和二叉树.ppt》由会员分享,可在线阅读,更多相关《[信息与通信]数据结构chapter 6 树和二叉树.ppt(117页珍藏版)》请在三一文库上搜索。
1、30-Jan-19,1,第六章 树和二叉树,树是一类重要的非线性数据结构,是以分支关系定义的层次结构 典型例子: 企业的管理机构 计算机文件系统,30-Jan-19,2,第一节 树的定义,树(Tree)的定义 树是由n (n 0)个节点组成的有限集合。 如果n = 0,称为空树; 如果n 0,则:有且仅有一个特定的称之为根(root)的节点,它只有直接后继,但没有直接前驱; 如果n1,则:除根以外的其它节点可以划分为m (m0)个互不相交的有限集合T0, T1, , Tm-1,每个集合又是一棵树,并且称为根的子树(subTree)。每棵子树的根节点有且仅有一个直接前驱,但可以有0个或多个直接后
2、继。 特点: 非空的树至少有一个根节点 树中各子树是互不相交的集合,30-Jan-19,3,树的示例,子树,根,30-Jan-19,4,树的基本术语,节点(node):树中的元素。包含一个数据元素及若干指向其子树的分支 节点的度(degree):节点拥有的指向其子树的分支数目 分支(branch) 节点:度不为0的节点 叶(leaf)(终端)节点:度为0的节点 树的度:树中所有节点度的最大值 孩子(child)与双亲(parent) 节点:节点的子树的根称为该节点的孩子,该节点称为孩子的双亲,30-Jan-19,5,树的基本术语(续),兄弟 ( sibling):同一个双亲的孩子之间互称兄弟。
3、 祖先(ancestor) :从根节点到某个节点所经分支上的所有节点。 子孙(descendant) :以某个节点为根节点的子树中的所有节点均是该节点的子孙。 堂兄弟:双亲在同一个层次上的节点互为堂兄弟。 节点所处层次(level) :根为第一层,根的孩子为第二层,依此类推。 树的深度(depth)(高度) :树中所有节点层次的最大值。,30-Jan-19,6,树的基本术语(续),有序树与无序树:树的各个子树从左至右的顺序不可以调换则称为有序树,否则为无序树。 森林(Forest):m(m0)棵互不相交的树的集合称为森林。 对树中每个节点而言,其子树的集合就构成森林。,30-Jan-19,7,
4、树的基本术语举例,节点A的度:3 节点B的度:2 节点M的度:0,叶子:K,L,F,G,M,I,J,节点I的双亲:D 节点L的双亲:E,树的度:3,树的深度:4,节点B,C,D为兄弟 节点K,L为兄弟,节点E,G,H为堂兄弟,节点A,D,H是M的祖先,30-Jan-19,8,树的抽象数据类型,数据对象D: D是具有相同特性的数据元素的集合。 数据关系R: 如果D为空集,则称为空树; 如果D中只有一个元素,则R为空集; 否则R=H,H是满足以下条件的二元关系: (1) 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2) 若D-root , 则存在D-root上 的一个划分D1
5、,D2,Dm m0,对任意jk(1j,km)有DjDk= ,且对任意的 i(1im),唯一存在数据元素xi(xiDi),,有H (3) 对应于D-root的划分,H , , , 有唯一的一个划分H1,H2,Hm m0,对任意jk(1j,km)有HjHk= ,且对任意的i(1im),Hi 是Di 上的二元关系,(Di,Hi) 是一棵符合本定义的树,称为根root的子树。,30-Jan-19,9,树的操作, 初始化 InitTree( 销毁树 DestroyTree(&T) 创建树 CreateTree(&T) 清空树 ClearTree(&T) 判断树是否为空 TreeEmtpy(T) 求树的深
6、度 TreeDepth(T) 求树的根 Root(T) 求树上某个节点的值 Value(T, cur_e) 给树上某个节点赋值 Assign(T, Cur_e, value) 返回某个节点的双亲 Parent(T, Cur_e) 11 求某个节点的左孩子 LeftChild(T, Cur_e) 12 求某个节点的右孩子 RightChild(T, Cur_e) 13 求某个节点的右兄弟 RightSibling(T, Cur_e) 14 在树中插入元素 InsertChild(&T, &p, i, c) 15 删除树中的元素 DeleteChild(&T, &p, i) 16 遍历树中所有元素
7、 TranverseTree(T, Visit(),30-Jan-19,10,第二节 二叉树(Binary Tree),二叉树的定义 一棵二叉树是n(n0)个节点的有限集合,该集合或者为空,或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 二叉树的特点 每个节点至多有二棵子树(即不存在度大于2的节点) 二叉树的子树有左、右之分,且其次序不能任意颠倒 二叉树是一种度为2的有序树,30-Jan-19,11,二叉树的五种不同形态,(a)空二叉树 (b)仅有根节点的二叉树 (c)右子树为空 (d)左子树为空 (e)左右子树均非空,30-Jan-19,12,二叉树的抽象数据类型
8、,数据对象D: D是具有相同特性的数据元素的集合。 数据关系R:如果D= ,则R= 称为空二叉树; 如果D ,则 R=H,H是满足以下条件的二元关系: (1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2)若D-root, 则存在D-root=Dl,Dr,且有DlDr= (3)如果 Dl ,则Dl中存在唯一元素xl,H,且存在Dl上的关系HlH;如果 Dr ,则Dr中存在唯一元素xr,H,且存在Dr上的关系HrH,并且有H=, ,Hl ,Hr (4)(Dl,Hl)是一棵符合本定义的二叉树,称为根root的左子树。(Dr,Hr)是一棵符合本定义的二叉树,称为根root的右子
9、树,30-Jan-19,13,二叉树的操作,二叉树的操作同普通树的操作类似 二叉树的遍历操作是最重要的操作 二叉树的遍历包括 先序遍历 中序遍历 后序遍历,30-Jan-19,14,2 二叉树的重要特性,性质1 在二叉树的第 i 层上至多有 2i-1 (i1) 个节点 证明:第1层只有1个节点1=21-1=20 假定第i层的节点个数为2i-1 那么由于二叉树每个节点最多有两个分支,因此第i+1层最多会有:2 2i-1= 2i-1+1 = 2(i+1)-1个节点 性质2 深度为 k 的二叉树至多有 2k-1 (k1) 个节点 证明:,30-Jan-19,15,二叉树的性质(续),性质3 对任何一
10、棵二叉树T,如果其终端节点数为 n0 ,度为2的节点数为 n2,则有: n0=n2+1 证明:若设度为1的节点有n1个,总节点个数为n,总分支数为B,则根据二叉树的定义, n = n0 + n1 + n2 (1) B = 2n2 + n1 = n 1 (2) 于是有: 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 1 n0 = n2 + 1,30-Jan-19,16,几种特殊形式的二叉树,满二叉树(Full Binary Tree) 定义:一棵深度为k,且有 2k-1 个节点的二叉树被称为满二叉树。 特点 每一层的节点数目均达到了最大值 可以对其按照从上到下,从左到右
11、的原则进行连续编号。,30-Jan-19,17,完全二叉树,完全二叉树(Complete Binary Tree) 定义:深度为 k,有 n 个节点的二叉树,当且仅当其每一个节点都与深度为 k 的满二叉树中编号从 1 至 n 的节点一一对应时,称之为完全二叉树。 完全二叉树的特点: 叶子节点只可能在层次最大的两层上出现; 对任一节点,若其右分支下的子孙的最大层次为 L ,那么其左分支下的子孙的最大层次必为 L 或 L+1 。,30-Jan-19,18,满二叉树与完全二叉树图示,30-Jan-19,19,进一步解释完全二叉树,完全二叉树:若共有h层,除第h层外,其它各层(1h-1)的节点数都达到
12、最大个数,第h层从右向左连续缺若干节点,这就是完全二叉树。,30-Jan-19,20,完全二叉树的两个重要性质,性质4 具有n个节点的完全二叉树的深度为 log2n+1 符号x表示不大于 x 的最大整数。,证明:根据完全二叉树的定义,若深度为k,则有:,30-Jan-19,21,完全二叉树的两个重要性质,性质5 对于一棵有 n 个节点的完全二叉树(深度为 log2n +1)的节点按照层序编号(从上到下,从左到右),则对于任意一个节点i (1in) 有: 1)如果i=1,则节点是根节点,无双亲;如果i1 ,则其双亲是节点是i/2 。 2)如果 2in ,则节点 i 无左孩子,否则其左孩子为 2i
13、 3)如果 2i+1n ,则节点 i无右孩子,否则其右孩子为 2i+1 性质5说明:在完全二叉树中,如果知道节点的编号就可以用简单的数学运算求出其双亲和孩子的位置。 性质5的证明;可以先证明2和3,然后利用2和3的结论来证明1。,30-Jan-19,22,性质5的证明,假定第i个节点位于第k层,根据二叉树的性质,那么前面k-1层总的节点个数为:2k-1-1个节点 第k层第一个节点的编号为2k-1-1+1= 2k-1,由此可以知道在第K层的第i个节点前面节点数目为:i- 2k-1 如果节点i有左孩子,根据完全二叉树的定义,那么第k层中在它前面的节点必然有左右孩子,这些孩子的总数目为:2( i-
14、2k-1 )且位于第k+1层 由于第K+1层第一个节点的编号为2k,那么第i个节点的左孩子的编号必然为: 2k+ 2( i- 2k-1 )=2i,它的右孩子的编号则为2i+1.,2k-1,K+1层,2i,i-2k-1,2k,2i+1,30-Jan-19,23,第三节 二叉树的存储结构,一 顺序存储结构 用一组连续的存储单元依次自上而下、自左至右存储完全二叉树中的所有元素。 特点: 节点间关系蕴含在其存储位置中 只适用于完全二叉树,对于普通的树,可能会造成严重的空间浪费。,30-Jan-19,24,顺序存储示例,30-Jan-19,25,顺序存储缺点,由于完全二叉树的节点数目与树的深度是指数关系
15、,因此如果树的深度较大,所需要的空间是惊人的。,单支树示例 例:一个深度为k (k=10) 的二叉树,如果用顺序存储结构来表示,需要2k-1(1023)个单元,而实际上树中的元素可能只有10个(单支树)。,30-Jan-19,26,顺序存储结构的C语言描述,#define MAX_TREE_SIZE 100 TElenType SqBiTree MAX_TREE_SIZE,完全二叉树,普通二叉树,30-Jan-19,27,二 二叉树的链式存储结构,根据不同的需要,可以设计不同的节点结构,从而得到不同的链式存储结构。 常用的链式存储结构有两种: 二叉链表,节点中有两个指针域,分别指向左右孩子 三
16、叉链表,节点中有三个指针域,分别指向左右孩子和父亲,30-Jan-19,28,二叉链表与三叉链表示例,30-Jan-19,29,二叉链表存储C描述,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode , *BiTree;,30-Jan-19,30,第四节 遍历二叉树,在实际应用中通常要在二叉树中查找具有某些特性的节点,或是对二叉树中的所有节点作某种处理,这就需要涉及二叉树的遍历问题。 所谓树的遍历,就是按某种次序访问树中的节点,要求每个节点访问一次且仅访问一次。 树遍历的典型例子:计算机
17、上删除目录 必须找到一种规律,将二叉树转换为一种线性结构,然后进行遍历。,30-Jan-19,31,二叉树的遍历方法,由于二叉树是由根节点、左子树、右子树三部分组成的,假定访问根节点记作 D,遍历根的左子树记作 L,遍历根的右子树记作 R 那么二叉树可能的遍历次序有6种: DLR,DRL,LDR,LRD,RDL,RLD 若限定先访问左子树后访问右子树,则可能有三种遍历方法: 先(根)序遍历DLR,先访问根,然后是左子树和右子树 中(根)序遍历LDR,先访问左子树,然后是根和右子树 后(根)序遍历LRD ,先访问左子树和右子树,然后是根,30-Jan-19,32,先序遍历算法,表达式语法树,若二
18、叉树为空,则空操作; 否则 访问根节点 (D); 先序遍历左子树 (L); 先序遍历右子树 (R)。 举例: 先序遍历结果:- + a * b - c d / e f,30-Jan-19,33,中序遍历算法,若二叉树为空,则空操作; 否则 中序遍历左子树 (L); 访问根节点 (D); 中序遍历右子树 (R) 举例: 遍历结果 a + b * c - d - e / f,30-Jan-19,34,后序遍历算法,若二叉树为空,则空操作; 否则 后序遍历左子树 (L); 后序遍历右子树 (R); 访问根节点 (D) 举例: 遍历结果 a b c d - * + e f / -,30-Jan-19,
19、35,三种遍历算法示例,先序遍历得到的序列为:ABDEHIJKCFG 中序遍历得到的序列为:DBHEJIKAFCG 后序遍历得到的序列为:DHJKIEBFGCA,30-Jan-19,36,先序遍历算法的C语言描述,Status preordertranverse(BiTree T, statsus (* visit) (TelemType) if (T) visit(T-data); preorderTranverse(T-lchild, visit); preorderTranverse(T-rchild, visit); return OK; ,30-Jan-19,37,C语言函数的递归调
20、用,如果函数体中的某语句调用函数本身,那么这个函数是递归的。 例:定义阶乘 n! 的递归函数factr(int n) 与非递归fact(int n),factr(int n) int answer; if(n=1) return 1; answer=factr(n-1)*n; return anwser; fact(int n) int t, answer; answer=1; for(t=1;t=n;t+) answer=answer *t; return anwser; ,30-Jan-19,38,递归程序,递归程序的主要优点是能够使某些算法更清晰简洁。 编写递归函数时必须在恰当的位置放置
21、if条件语句,让递归函数不需要继续递归而是立即返回。 函数调用自己时在栈上为局部变量和参量分配存储空间,从头执行函数代码,并不复制函数代码。,30-Jan-19,39,递归示例1:统计叶子节点数目,int CountLeafNum(BiTree T) if (T = NULL) return 0; if (T-lchild = NULL ,30-Jan-19,40,递归示例2:计算树的高度,int ComputeTreeHeight(BiTree T) int lh; int rh; if (T = NULL) return 0; if (T-lchild = NULL ,30-Jan-19,
22、41,中序遍历非递归算法(1),status InOrderTraverse (BiTree T, Status (*Visit) (TElement e) InitStack(S);push(S, T); while (! StackEmpty (S) while (GetTop(S,p) ,30-Jan-19,42,非递归算法(1)示意图,a,Stack,b,c,null,Output:,c,e,30-Jan-19,43,中序遍历非递归算法(2),status InOrderTranverse(BiTree T, Status (*Visit) (TElement e) InitStack
23、(S); p = T; while (p | !EmptyStack(S) if (p) push(S,p); p=p-lchild; else pop(S, p); visit(p-data); p=p-rchild; return OK; ,30-Jan-19,44,非递归算法(2)示意图,a,Stack,b,c,Output:,c,e,两种方法的区别是(2)的处理要简洁些,空指针不需要入栈,而方法(1)有多次的空指针入栈、出栈操作。,30-Jan-19,45,先序遍历非递归算法,status PreOrderTranverse(BiTree T, Status (*Visit) (TEl
24、ement e) InitStack(S); p = T; while (p | !EmptyStack(S) if (p) visit(p-data); push(S,p); p=p-lchild; else pop(S, p); p=p-rchild; return OK; ,30-Jan-19,46,二叉树形态与遍历结果的关系,当二叉树的形态确定后,那么它的先序、中序和后序遍历的结果就已经确定。 但是单纯根据二叉树的先序、中序或后序遍历的序列不可能完全确定二叉树的形态。 如果要完全确定二叉树的形态需要知道先序和中序的结果,或是中序和后序遍历的结果,30-Jan-19,47,创建二叉树,单
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息与通信 信息与通信数据结构chapter 树和二叉树 信息 通信 数据结构 chapter 二叉
链接地址:https://www.31doc.com/p-2000868.html