树和森林的概念 二叉树 （Binary Tree） 二叉树遍历 （Binary.ppt

《树和森林的概念 二叉树 （Binary Tree） 二叉树遍历 （Binary.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、树和森林的概念二叉树(BinaryTree)二叉树遍历(BinaryTreeTraversal)线索化二叉树(ThreadedBinaryTree)堆(Heap)树与森林(Tree&Forest)二叉树的计数霍夫曼树(HuffmanTree)小结第六章树与森林树和森林的概念树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是

2、一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。结点(node)结点的度(degree)分支(branch)结点叶(leaf)结点子女(child)结点双亲(parent)结点兄弟(sibling)结点祖先(ancestor)结点子孙(descendant)结点结点所处层次(level)树的高度(depth)树的度(degree)有序树无序树森林templateclassTree{public:Tree();~Tree();positio

3、nRoot();BuildRoot(constType&value);positionFirstChild(positionp);positionNextSibling(positionp,positionv);positionParent(positionp);TypeRetrieve(positionp);树的抽象数据类型intInsertChild(constpositionp,constType&value);intDeleteChild(positionp,inti);voidDeleteSubTree(posi

4、tiont);intIsEmpty();}二叉树(BinaryTree)二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。性质1若二叉树的层次从0开始,则在二叉树的第i层最多有2i个结点。(i0)[证明用数学归纳法]性质2高度为k的二叉树最多有2k+1-1个结点。(k-1)[证明用求等比级数前k项和的公式]性质3对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1二叉树的性质证明：

5、若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+1定义1满二叉树(FullBinaryTree)定义2完全二叉树(CompleteBinaryTree)若设二叉树的高度为h，则共有h+1层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。性质4具有n个结点的完全二叉树的高度为log2(n+1)-1证明：设完全二叉树的高度为h，

6、则有2h-10,则i的双亲为(i-1)/2若2*i+1

7、弟为i+1i所在层次为log2(i+1)二叉树的抽象数据类型templateclassBinaryTree{public:BinaryTree();BinaryTree(BinTreeNode*lch,BinTreeNode*rch,Typeitem);intIsEmpty();BinTreeNode*Parent();BinTreeNode*LeftChild();BinTreeNode*RightChild();intInsert(c

8、onstType&item);intFind(constType&item)const;TypeGetData()const;constBinTreeNode*GetRoot()const;}完全二叉树的数组表示一般二叉树的数组表示二叉树的表示数组表示单支树链表表示由于一般二叉树必须仿照完全