树和森林的概念 二叉树 二叉树遍历 二叉树的计数 线索化二叉.ppt

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

1、树和森林的概念二叉树二叉树遍历二叉树的计数线索化二叉树堆树与森林Huffman树第六章树与森林树和森林的概念树的定义树是由n(n≥0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其他结点划分为m(m≥0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树。树的特点每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。0层1层3层2层height=3ACGBDEFKLHMIJ0层

2、1层3层2层height=3ACGBDEFKLHMIJ结点结点的度分支结点叶结点子女双亲兄弟祖先子孙结点层次树的度树高度森林templateclassTree{//对象:树是由n(≥0)个结点组成的有限集//合。在类界面中的position是树中结点的//地址。在数组存储方式下是下标型,在链//表存储方式下是指针型。Type是树结点中存放数据的类型。public:Tree();~Tree();树的抽象数据类型positionRoot();BuildRoot(constType&value);po

3、sitionFirstChild(positionp);positionNextSibling(positionp);positionParent(positionp);TypeGetData(positionp);intInsertChild(constpositionp,constType&value);intDeleteChild(positionp,inti);}二叉树(BinaryTree)二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子

4、树和右子树的、互不相交的二叉树组成。LLRR性质1若二叉树的层次从0开始,则在二叉树的第i层最多有2i个结点。(i≥0)[证明用数学归纳法]性质2高度为h的二叉树最多有2h+1-1个结点。(h≥-1)[证明用求等比级数前k项和的公式]20+21+22+…+2h=2h+1-1二叉树的性质性质3对任何一棵二叉树,如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0＝n2＋1证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=

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

6、h=log2(n+1)-1上面h层结点数包括第h层的最大结点数23-124-1性质5如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0,1,2,…,n-1，则有以下关系：若i=0,则i无双亲若i>0,则i的双亲为(i-1)/2若2*i+1classBi

7、naryTree{public:BinaryTree();//构造函数BinaryTree(BinTreeNode*lch,BinTreeNode*rch,Typeitem);//构造以item为根，lch和rch为左、右//子树的二叉树intIsEmpty();//判二叉树空否？BinTreeNode*Parent();//双亲BinTreeNode*LeftChild();//取左子女结点地址BinTreeNode*RightChild();//取右子女

8、结点地址intInsert(constType&item);//插入intFind(constType&item)const;//搜索TypeGetData()const;//取得结点数据BinTreeNode*GetRoot()const;//取根结点地址}正则二叉树理想平衡二叉树满的完全二叉树一般二叉树的顺序表示的顺序表示二叉树