第六章树与森林 树和森林的概念 二叉树(Binary Tree) 二叉树的表示 二叉树遍历(Binary Tree Traversal) 线索化二叉树(Threaded Binary Tree 堆(Heap) 树与森林(Tree& Forest) 二叉树的计数 霍夫曼树(Huffman Tree)
树和森林的概念 二叉树 (Binary Tree) 二叉树的表示 二叉树遍历 (Binary Tree Traversal) 线索化二叉树 (Threaded Binary Tree) 堆 ( Heap ) 树与森林 (Tree & Forest) 二叉树的计数 霍夫曼树 (Huffman Tree)
树和森林的概念 树的完义 树是由n(n≥0个结点组成的有限集合。如果n 0,称为空树;如果n>0,则 有一个特定的称之为根root的结点,它只有 直接后继,但没有直接前驱; 除根以外的其它结点划分为m(m≥0个互不 相交的有限集合T,T1,…,Tm,每个集合又是一 棵树,并且称之为根的子树( subTree)每棵子树 的根结点有且仅有一个直接前驱,但可以有0个 或多个直接后继
树和森林的概念 树的定义 树是由n (n 0)个结点组成的有限集合。如果n = 0，称为空树；如果n > 0，则 ▪ 有一个特定的称之为根(root)的结点，它只有 直接后继，但没有直接前驱； ▪ 除根以外的其它结点划分为m (m 0)个互不 相交的有限集合T0 , T1 , …, Tm-1，每个集合又是一 棵树，并且称之为根的子树(subTree)。每棵子树 的根结点有且仅有一个直接前驱，但可以有0个 或多个直接后继
root root A Level o (a) eve depth=3 E)(F)(G)(H level 2 level 3 0结点(mode) 0兄弟( ( Sibling)结点有序树 结点的度( degree)祖先 ancestor)结点无序树 分支( branch)结点子孙 descendant)结点·森林 叶(ea结点 0结点所处层次eve) 0子女( child)结点树的高度( depth) 0双亲( parent)结点。树的度( degree)
结点(node) 结点的度(degree) 分支(branch)结点 叶(leaf)结点 子女(child)结点 双亲(parent)结点 兄弟(sibling)结点 祖先(ancestor)结点 子孙(descendant)结点 结点所处层次(level) 树的高度(depth) 树的度(degree) ◼ 有序树 ◼ 无序树 ◼ 森林
树的抽象数据类型 template class Tree i public ee e(); position root o; Buildroot( const Type& value ) position First Child( position position Nextsibling( position p, position v ) position Parent( position ) Type Retrieve( position p ) position Insertchild( const position p, const Type &value
template class Tree { public: Tree ( ); ~Tree ( ); position Root ( ); BuildRoot ( const Type& value ); position FirstChild ( position p ); position NextSibling ( position p, position v ); position Parent ( position p ); Type Retrieve ( position p ); position InsertChild ( const position p, const Type &value ); 树的抽象数据类型
position Delete child(position p, int i) void Delete Tree(position int IsEmpty (;
position DeleteChild ( position p, int i ); void DeleteSubTree ( position t ); int IsEmpty ( ); }
二叉树( Binary Tree 二叉树的完义 一棵二叉树是结点的一个有限集合,该 集合或者为空,或者是由一个根结点加上两 棵分别称为左子树和右子树的、互不相交的 二叉树组成。 (a)(b) R (e) 二叉树的五种不同形
二叉树 (Binary Tree) 二叉树的定义 二叉树的五种不同形态 一棵二叉树是结点的一个有限集合，该 集合或者为空，或者是由一个根结点加上两 棵分别称为左子树和右子树的、互不相交的 二叉树组成
二叉树的性质 性质1若二叉树的层次从0开始,则在二叉树的 第i层最多有2个结点。(i≥0) i证明用数学归纳法 性质2高度为k的二叉树最多有24+1-1个结点。 (k≥-1) 证明用求等比级数前k项和的公式 性质3对任何一棵二叉树,如果其叶结点个数为 np度为2的非叶结点个数为m2,则有 noEn+1
性质1 若二叉树的层次从0开始, 则在二叉树的 第 i 层最多有 2 i 个结点。(i 0) [证明用数学归纳法] 性质2 高度为k的二叉树最多有 2 k+1 -1个结点。 (k -1) [证明用求等比级数前k项和的公式] 性质3 对任何一棵二叉树, 如果其叶结点个数为 n0 , 度为2的非叶结点个数为n2 , 则有 n0＝n2＋1 二叉树的性质
证明:若设度为1的结点有n1个,总结点个 数为n,总边数为e,则根据二叉树的定义, n=n0+n1+n2e=2m2+n1=n- 因此,有2m2+n1=n+n1+n2-1 2 0 0-2 +1 当当当当当当当当当当当当当当当当当当当当当当当巨当当当当巨当 定义1满二叉树( Full Binary tree 定义2完全二叉树( omplete Binary Tree) 若设二叉树的高度为h,则共有h+1层。除第h 层外,其它各层(0~h-1)的结点数都达到最大个数 第h层从右向左连续缺若干结点,这就是完全二 叉树
证明：若设度为1的结点有n1个，总结点个 数为n，总边数为e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1 定义1 满二叉树(Full Binary Tree) 定义2 完全二叉树(Complete Binary Tree) 若设二叉树的高度为h，则共有h+1层。除第h 层外，其它各层(0h-1)的结点数都达到最大个数， 第h层从右向左连续缺若干结点，这就是完全二 叉树
(8)(9 0203 (a)满二叉树 (b)完全二叉树 性质4具有n个结点的完全二叉树的高度为 log(n+1)|-1 证明:设完全二叉树的高度为则有 2h-1<n≤2h+1-12h<n+1≤2h+1 取对数h<log2(n+1)≤h+1
性质4 具有n个结点的完全二叉树的高度为 log2 (n+1) -1 证明：设完全二叉树的高度为h，则有 2 h - 1 < n 2 h+1 - 1 2 h < n+1 2 h+1 取对数 h < log2 (n+1) h+1
性质5如果将一棵有n个结点的完全二叉树自顶 向下,同一层自左向右连续给结点编号0,1,2, n-1,然后按此结点编号将树中各结点顺序地存 放于一个一维数组中,并简称编号为结点为结 点i(0≤i≤n-1。则有以下关系 若i==0,则i无双亲 若i>0,则i的双亲为(-1)2」 若2*计1<n,则i的左子女为2*计1 若2*计2<n,则i的右子女为2*计2 若i为偶数,且i!=0,则其左兄弟为i1 若i为奇数,且i!=n-1,则其右兄弟为i1 i所在层次为Log2(计+1)
性质5 如果将一棵有n个结点的完全二叉树自顶 向下，同一层自左向右连续给结点编号0, 1, 2, …, n-1，然后按此结点编号将树中各结点顺序地存 放于一个一维数组中, 并简称编号为i的结点为结 点i (0 i n-1。则有以下关系： ◼ 若i == 0, 则 i 无双亲 若i > 0, 则 i 的双亲为(i -1)/2 ◼ 若2*i+1 < n, 则 i 的左子女为2*i+1 若2*i+2 < n, 则 i 的右子女为2*i+2 ◼ 若 i 为偶数, 且i != 0, 则其左兄弟为i-1 若 i 为奇数, 且i != n-1, 则其右兄弟为i+1 ◼ i 所在层次为 log2 (i+1)