755-第6章 树和二叉树.ppt
《755-第6章 树和二叉树.ppt》由会员分享,可在线阅读,更多相关《755-第6章 树和二叉树.ppt(49页珍藏版)》请在三一文库上搜索。
1、,第6章 树和二叉树 树是一类重要的非线性数据结构,是以分支关系定义的层次结构 6.1 树的定义 定义:树(tree)是n(n0)个结点的有限集T 其中:有且仅有一个特定的结点,称为树的根(root) 当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每一个集合本身又是一棵树,称为根的子树(subtree) 特点: 树中至少有一个结点称为根 树中各子树是互不相交的集合,A,只有一个根结点的树,A为根结点,其余分为三个互不相交的子集 T1=B,E,F,K,L T2=C,G T3=D,H,I,J,M T1,T2,T3都是根结点A的子树,且本身又是一棵树。,根,基本术语 结点
2、(node):包括一个数据元素及若干指向其子树的分支 结点的度(degree):结点拥有的子树个数 叶子(leaf):度为0的结点(或称终端结点) 分支结点(非终端结点):度不为0的结点 树的度:树内各结点的度的最大值 孩子(child):结点的子树的根称为该结点的孩子 双亲(parents): (相对孩子)结点的上层结点 兄弟(sibling):同一双亲的孩子之间互称兄弟 结点的祖先:从根到该结点所经分支上的所有结点 子孙:某结点为根的子树中的任意结点 结点的层次(level):从根结点算起,根为第一层,它的孩子为第二层 深度(depth):树中结点的最大层次数 森林(forest):m(m
3、0)棵互不相交的树的集合,ADT Tree 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R:若D为空集,则称为空树; 若D仅含一个数据元素,则R为空集,否则RH, H是如下二元关系: (1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2)若Droot,则存在Droot的一个划分 D1,D2,Dm(m0),对任意j k(1j, km) 有Dj Dk = ,且对任意的i(1im),唯一存在数据元素Xi Di,有root, Xi H; (3) 对应于D-root的划分,H-有唯一的一个划分H1,H2,Hm(m0),对任意jk(1j, km) 有Hj Hk = ,且对
4、任意i(1im),Hi是 Di上的二元关系,(Di,Hi)是一棵符合本定义的树,称为根root的子树。,基本操作P: InitTree ( ADT Tree,6.2 二叉树 一、定义 二叉树是n(n0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分,且其次序不能任意颠倒 基本形态,A,ADT BinaryTree 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R: 若D,则R,称BinaryTree为空二叉树; 若D,则RH,H是如下二元关系; (
5、1) 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2) 若D-root,则存在D-rootDl,Dr,且DlDr ; (3) 若Dl ,则Dl中存在唯一的元素Xl,H,且存在Dl上的关系HlH;若Dr,则Dr中存在唯一的元素Xr,H , 且存在Dr上的关系HrH; H,, Hl, Hr ; (4) (Dl, Hl)是一棵符合本定义的二叉树,称为根的左子树 (Dr,Hr)是一棵符合本定义的二叉树,称为根的右子树,基本操作P: InitBiTree ( ADT BinaryTree,二、二叉树的性质,性质1:在二叉树的第i层上至多有2i-1个结点(i1),证明:用归纳法证明
6、i=1时,只有一个根结点, 2i-1= 20=1 是对的 假设对所有j(1ji)命题成立,即第j层上至多有 2j-1 个结点 那么,第i-1层至多有2i-2 个结点 又二叉树每个结点的度至多为2 第i层上最大结点数是第i-1层的2倍,即2x2i-2= 2i-1 故命题得证,性质2:深度为k的二叉树至多有2k -1个结点(k1),证明:由性质1知深度为k 的二叉树最大结点数为 k k (第i层上的最大结点数)= 2i-1= 2k 1 i=1 i=1,性质3:对任何一棵二叉树T,如果其终端结点数为n0,度 为2的结点数为n2,则 n0=n2+1,证明:设n1为二叉树T中度为1的结点数 因为:二叉树
7、中所有结点的度均小于或等于2 所以:其结点总数n=n0+n1+n2 又二叉树中,除根结点外,其余结点都只有一个 分支进入 设B为分支总数,则n=B+1 又:分支由度为1和度为2的结点射出,B=n1+2n2 于是,n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1,两种特殊形式的二叉树,满二叉树,定义:一棵深度为k且有2k-1个结点的二叉树称为满二叉树,特点:每一层上的结点数都是最大结点数,两种特殊形式的二叉树,完全二叉树,定义:深度为k,有n个结点的二叉树当且仅当其每一个结 点都与深度为k的满二叉树中编号从1至n的结点一一 对应时,称为完全二叉树,特点:叶子结点只可能在层次最大的两
8、层上出现 对任一结点,若其右分支下子孙的最大层次为l,则其左分支下子孙的最大层次必为l 或l+1,性质4:具有n个结点的完全二叉树的深度为log2n +1,证明:设深度为k,根据性质2和完全二叉树的定义有 2k-1 -1 n 2k-1,或 2k-1 n 2k,于是 k-1 log2n k,因为 k是整数 所以 k= log2n +1,性质5:如果对一棵有n个结点的完全二叉树的结点按层序 编号,则对任一结点i(1in),有: (1) 如果i=1,则结点i是二叉树的根,无双亲;如果i1, 则其双亲是i/2 (2) 如果2in,则结点i无左孩子;如果2in,则其左孩子是2i (3) 如果2i+1n,
9、则结点i无右孩子;如果2i+1n,则其右孩子是2i+1,三、二叉树的存储结构,1、顺序存储结构 二叉树的顺序存储表示 #define MAX_TREE_SIZE 100 typedef TElemType SqBiTree MAX_TREE_SIZE ; SqBiTree bt ;,顺序存储结构的特点: 结点间关系蕴含在其存储位置中 浪费空间,适于存满二叉树和完全二叉树,2、链式存储结构,二叉树的二叉链表存储表示 typedef struct BiTNode TElemType data; struct BiTNode * lchild , * rchild ; BiTNode , * BiT
10、ree ;,特点: 指针直接表示关系,操作简单 增加指针域,浪费空间,特别是存在多个空指针域,6.3 遍历二叉树和线索二叉树 一、遍历二叉树 遍历二叉树(Traversing Binary Tree):按某条搜索路径巡访树的每个结点,且使每个顶点仅被访问一次,从而得到树中所有结点的一个线性排列。,由二叉树的递归定义可知: 二叉树是由三个基本单元组成: 根结点、左子树、右子树,则可得到六种遍历方案: DLR、LDR、LRD、DRL、RDL、RLD,先序遍历(DLR):先访问根结点,然后分别先序遍历左子树、 右子树 中序遍历(LDR):先中序遍历左子树,然后访问根结点,最 后中序遍历右子树 后序遍
11、历(LRD):先后序遍历左、右子树,然后访问根结点,先序遍历二叉树的操作定义为: 若二叉树为空,则空操作;否则 (1)访问根结点 (2)先序遍历左子树 (3)先序遍历右子树,中序遍历二叉树的操作定义为: 若二叉树为空,则空操作;否则 (1)中序遍历左子树 (2)访问根结点 (3)中序遍历右子树,后序遍历二叉树的操作定义为: 若二叉树为空,则空操作;否则 (1)后序遍历左子树 (2)后序遍历右子树 (3)访问根结点,例:,先序序列:,A,B,D,F,E,G,C,中序序列:,D,B,F,G,E,A,C,后序序列:,D,F,G,B,E,C,A,先序遍历二叉树的递归算法 Status PreOrder
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 755-第6章 树和二叉树 755 二叉
链接地址:https://www.31doc.com/p-3023873.html