第六章树与森林 树和森林的概念 二叉树 树遍历 叉树的计数 线索化二叉树 堆 与森休 霍夫曼树
◼ 树和森林的概念 ◼ 二叉树 ◼ 二叉树遍历 ◼ 二叉树的计数 ◼ 线索化二叉树 ◼ 堆 ◼ 树与森林 ◼ 霍夫曼树
树和森林的概念 树的定义 树是由n(≥0)个结点组成的有限集合。 如果n=0,称为空树;如果n>0,则 有一个特定的称之为根(root)的结点, 它只有直接后继,但没有直接前驱 除根以外的其它结点划分为m(m≥0) 个互不相交的有限集合TT,…,Tm1,每 个集合又是一棵树,并且称之为根的子树
树和森林的概念 树的定义 树是由 n (n 0) 个结点组成的有限集合。 如果 n = 0，称为空树；如果 n > 0，则 ▪ 有一个特定的称之为根(root)的结点， 它只有直接后继，但没有直接前驱； ▪ 除根以外的其它结点划分为m (m 0) 个 互不相交的有限集合T0 , T1 , …, Tm-1，每 个集合又是一棵树，并且称之为根的子树
树的特点 每棵子树的根结点有且仅有一个直接前 驱,但可以有0个或多个直接后继。 A 0层 B D l层 height O-2层3 K(L 3层
树的特点 ◼ 每棵子树的根结点有且仅有一个直接前 驱，但可以有0个或多个直接后继。 0层 1层 3层 2层 height = 3 A C G B D E F K L H M I J
结点子女祖先来树的度 结点的度米双亲癥子孙树高度 ※分支结点*兄弟*结点层次*森林 叶结点 A 0层 B D l层 height O-2层3 K(L 3层
0层 1层 3层 2层 height = 3 A C G B D E F K L H M I J 结点 结点的度 分支结点 叶结点 子女 双亲 兄弟 祖先 子孙 结点层次 树的度 树高度 森林
树的抽象数据类型 template class Tree t /对象:树是由n(0)个结点组成的有限集 /合。在类界面中的 position是树中结点的 /地址。在顺序存储方式下是下标型,在链 /表存储方式下是指针型。Type是树结点中 存放数据的类型。 public Tree (; caree()
template class Tree { //对象: 树是由n(≥0)个结点组成的有限集 //合。在类界面中的position是树中结点的 //地址。在顺序存储方式下是下标型, 在链 //表存储方式下是指针型。Type是树结点中 存放数据的类型。 public: Tree ( ); ~Tree ( ); 树的抽象数据类型
position root o; BuildRoot( const Type& value )3 position Firstchild( position p ) position Nextsibling( position p, position v ) position Parent( position p )i Type GetData( position p ) int InsertChild( const position p, const Type &value int Delete Child( position p, int 1 );
position Root ( ); BuildRoot ( const Type& value ); position FirstChild ( position p ); position NextSibling ( position p, position v ); position Parent ( position p ); Type GetData ( position p ); int InsertChild ( const position p, const Type &value ); int DeleteChild ( position p, int i ); }
二叉树( Binary Tree 二叉树的定义 一棵二叉树是结点的一个有限集合, 该集合或者为空,或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不 相交的二叉树组成。 R LR 二叉树的五种不同形
二叉树 (Binary Tree) 二叉树的定义 二叉树的五种不同形态 一棵二叉树是结点的一个有限集合， 该集合或者为空，或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不 相交的二叉树组成。 L R L R
二叉树的性质 性质1若二叉树的层次从0开始,则在二叉 树的第i层最多有2个结点。(≥0) i证明用数学归纳法] 性质2高度为h的二叉树最多有2+1-1个 结点。(h≥-1) 证明用求等比级数前k项和的公式 20+21+22+…+2h=2h+1-1
性质1 若二叉树的层次从0开始, 则在二叉 树的第 i 层最多有 2 i 个结点。(i 0) [证明用数学归纳法] 性质2 高度为 h 的二叉树最多有 2 h+1-1个 结点。(h -1) [证明用求等比级数前k项和的公式] 2 0 + 21 + 22 + … + 2h = 2h+1-1 二叉树的性质
性质3对任何一棵二叉树,如果其叶结点 有m0个,度为2的非叶结点有n2个,则有 =n2+1 证明:若设度为1的结点有m1个,总结点 个数为n,总边数为e,则根据二叉树的 定义, n=n0+n1+n2e=2n2+n1=n-1 因此,有2n2+m1=m0+n1+m2-1 0 n=n+1 0
性质3 对任何一棵二叉树, 如果其叶结点 有 n0 个, 度为2的非叶结点有 n2 个, 则有 n0＝n2＋1 证明：若设度为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层外,其它各层(0~h-1)的结点数 都达到最大个数,第h层从右向左连续缺 若千结点,这就是完全二又树
定义1 满二叉树 (Full Binary Tree) 定义2 完全二叉树 (Complete Binary Tree) 若设二叉树的高度为h，则共有h+1层。 除第 h 层外，其它各层 (0 h-1) 的结点数 都达到最大个数，第 h 层从右向左连续缺 若干结点，这就是完全二叉树