第6章树和二叉树 从对线性结构的研究过渡到对树形 结构的研究,是数据结构课程学习的 次跃变
从对线性结构的研究过渡到对树形 结构的研究，是数据结构课程学习的一 次跃变
6树的定义和基本术语 1树的定义 树是由n(n≥0个结点组成的有限集合。 如果n=0,称为空树 如果n>0,则 有一个特定的称之为根(roo的结点,它只有 后继,但没有前驱; 除根以外的其它结点划分为m(m≥0)个互不 相交的有限集合T,T,…,Tm1,每个集合本身又 是一棵树,并且称之为根的子树( subTree每棵 子树的根结点有且仅有一个直接前驱,但可以有 0个或多个后继
6.1 树的定义和基本术语 1. 树的定义 树是由n (n 0)个结点组成的有限集合。 如果n = 0，称为空树； 如果n > 0，则: ▪ 有一个特定的称之为根(root)的结点，它只有 后继，但没有前驱； ▪ 除根以外的其它结点划分为m (m 0)个互不 相交的有限集合T0 , T1 , …, Tm-1，每个集合本身又 是一棵树，并且称之为根的子树(subTree)。每棵 子树的根结点有且仅有一个直接前驱，但可以有 0个或多个后继
root Level 1 mlevel 2 level 3 eve
E BF Q/(@c J K D H A(B(E, FO, K)G)C, D(H D) (b) (a)嵌套集合表示法(b)括号表示法()凹入表示法
(a)嵌套集合表示法 (b)括号表示法 (c)凹入表示法
2树的基本术语 1)度(次数、级) (1)结点的度:一个结点所拥有的子数的个数 (2)树的度:树内各结点的度的最大值 2)描述上下及左右的关系 孩子和双亲结点:某个结点的子树的根称为该结点的 孩子,相应的,该结点称为其孩子的双亲。 兄弟结点:同一个双亲的孩子之间互称兄弟 祖先:结点的祖先是从根到该结点所经分支上的 所有结点。 子孙:以某结点为根的子树中的任一结点都称为该结 点的子孙
1）度（次数、级） （1）结点的度：一个结点所拥有的子数的个数 （2）树的度：树内各结点的度的最大值 2）描述上下及左右的关系 孩子和双亲结点：某个结点的子树的根称为该结点的 孩子，相应的，该结点称为其孩子的双亲。 兄弟结点：同一个双亲的孩子之间互称兄弟 祖先：结点的祖先是从根到该结点所经分支上的 所有结点。 子孙：以某结点为根的子树中的任一结点都称为该结 点的子孙。 2. 树的基本术语
3)层次 (1)结点的层次:规定根所在的层次为第1层,根 的孩子在第二层,依次类推。 (2)树的深度(高度):树中结点最大的层数。 4)有序树:是指树中结点的各子树从左至右是有次序 的,否则称为无序树。 森林:是指n(n≥0)棵互不相交的树的集合。 树的抽象数据类型:树的基本操作:p19 树的建立和遍历—重点
树的基本操作：p119 树的建立和遍历——重点 树的抽象数据类型： 3）层次 （1）结点的层次：规定根所在的层次为第1层，根 的孩子在第二层，依次类推。 （2）树的深度（高度）：树中结点最大的层数。 4）有序树：是指树中结点的各子树从左至右是有次序 的，否则称为无序树。 森林：是指n（n≥0）棵互不相交的树的集合
62二叉树( Binary Tree) 二叉树的定义 一棵二叉树是结点的一个有限集合,该 集合或者为空,或者是由一个根结点加上两 棵分别称为左子树和右子树的、互不相交的 二叉树组成。 特点:1)每个结点的度<2:2)是有序树 (a)(b) R (c)(d) 二叉树的五种不同形庵
6.2 二叉树 (Binary Tree) 二叉树的定义 二叉树的五种不同形态 一棵二叉树是结点的一个有限集合，该 集合或者为空，或者是由一个根结点加上两 棵分别称为左子树和右子树的、互不相交的 二叉树组成。 特点：1）每个结点的度≤2；2）是有序树
二叉树基本操作:p121 (1)createbitree(t)(2)destroybitree(t) root(t) (4)leftchild(t) (5)rightchild(t)(6)locate(t,x) ()parent(t,x)(8)isempty(t) (9)depth(t) (10)numofnode(t (11)addchild(t, x, t1, b)(12)deletechild(t, x, b) (13)setnull(t)(14)isequal(t1, t2) (15) preorder(t) (16)inorder(t) (17)postorder(t)(18)transform(t1, t2)
二叉树基本操作：p121 (1)createbitree(t) (2)destroybitree(t) (3)root(t) (4)leftchild(t) (5)rightchild(t) (6)locate(t,x) (7)parent(t,x) (8)isempty(t) (9)depth(t) (10)numofnode(t) (11)addchild(t,x,t1,b) (12)deletechild(t,x,b) (13)setnull(t) (14)isequal(t1,t2) (15)preorder(t) (16)inorder(t) (17)postorder(t) (18)transform(t1,t2)
二叉树的抽象教据类型 二叉树是一种重要的树型结构,但二叉树不是 树的特例。 二叉树的5种形态分别为:空二叉树,只有根 结点的二叉树,根结点和左子树,根结点和右子 树,根结点和左右子树。 二叉树与树的区别:二叉树中每个结点的孩子 至多不超过两个,而树对结点的孩子数无限制 另外,二叉树中结点的子树有左右之分,而树的 子树没有次序
二叉树的抽象数据类型 二叉树是一种重要的树型结构，但二叉树不是 树的特例。 二叉树的5 种形态分别为：空二叉树，只有根 结点的二叉树，根结点和左子树，根结点和右子 树，根结点和左右子树。 二叉树与树的区别：二叉树中每个结点的孩子 至多不超过两个，而树对结点的孩子数无限制； 另外，二叉树中结点的子树有左右之分，而树的 子树没有次序
二叉树的性质(P123) 性质1若二叉树的层次从1开始,则在二叉树的 第i层最多有2个结点。(i≥1) i证明用数学归纳法 性质2深度为k的二叉树最多有2k-1个结点。 (k≥1) 证明用求等比级数前k项和的公式 性质3对任何一棵二叉树,如果其叶结点个数为 np度为2的非叶结点个数为m2,则有 noEn+1
性质1 若二叉树的层次从1开始, 则在二叉树的 第 i 层最多有 2 i-1个结点。(i 1) [证明用数学归纳法] 性质2 深度为k的二叉树最多有 2 k -1个结点。 (k 1) [证明用求等比级数前k项和的公式] 性质3 对任何一棵二叉树, 如果其叶结点个数为 n0 , 度为2的非叶结点个数为n2 , 则有 n0＝n2＋1 二叉树的性质（P123）