position root o; BuildRoot( const Type& value )3 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 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个 结点。(≥-1) i证明用求等比级数前项和的公式] 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对任何一棵二叉树,如果其叶结点 有n0个,度为2的非叶结点有m2个,则有 =n2+1 证明:若设度为1的结点有n1个,总结点 个数为n,总边数为e,则根据二叉树的 定义, n=n0+n1+n2e=2n2+n1=n-1 因此,有2n2+n1=+m1+n2-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完全二叉树( omplete 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 层从右向左连续缺 若干结点，这就是完全二叉树