d树和森林的概念

《d树和森林的概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树和森林的概念二叉树二叉树的表示二叉树遍历及其应用线索化二叉树树与森林堆Huffman树第5章树树和森林的概念两种树：自由树与有根树。自由树：一棵自由树Tf可定义为一个二元组Tf=(V,E)其中V={v1,...,vn}是由n(n＞0)个元素组成的有限非空集合，称为顶点集合。E={(vi,vj)

2、vi,vjV,1≤i,j≤n}是n-1个序对的集合，称为边集合，E中的元素(vi,vj）称为边或分支。自由树r是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为m(m0)个互不相交的有限集合T1,T2,…,Tm，每个集合又是一棵树，并且称之为根的子树。每棵

3、子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。有根树：一棵有根树T，简称为树，它是n(n≥0)个结点的有限集合。当n=0时，T称为空树；否则，T是非空树，记作树的示意图（P.187）树的特点每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。0层1层3层2层height=3ACGBDEFKLHMIJ0层1层3层2层height=3ACGBDEFKLHMIJ结点结点的度分支结点叶结点子女双亲兄弟祖先子孙结点层次树的度树高度森林术语templateclassTree{public:Tree();~Tree();positionRoot();Bui

4、ldRoot(constType&value);positionFirstChild(positionp);positionNextSibling(positionp);positionParent(positionp);TypeGetData(positionp);intInsertChild(constpositionp,constType&value);intDeleteChild(positionp,inti);}树的抽象数据类型一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。5.2二叉树(BinaryTree)

5、二叉树的定义二叉树的五种不同形态LLRR性质1若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i≥1)性质2深度为k的二叉树最多有2k-1个结点。k≥0二叉树的性质性质3对任何一棵二叉树,如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0＝n2＋1证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2e=n-1=2n2+n1=因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+1定义1满二叉树(FullBinaryTree)如果二叉树中所有分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉

6、树。定义2完全二叉树(CompleteBinaryTree)如果一棵具有n个结点的高度为k的二叉树，它的每一个结点都与高度为k的满二叉树中编号为1-n结点一一对应，则称这棵二叉树为完全二叉树。（从上到下从左到右编号）满二叉树完全二叉树层次h，叶结点仅在两层出现对任一结点，若其右子树的高度为k，则其左子树的高度是h和h-1kork+1性质4具有n(n0)个结点的完全二叉树的高度为log2(n+1)23-124-1性质5如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,…,n，则有以下关系：(1)若i==1,则i为根，无双亲若i>1,则i的双亲为i/2(2)若n

7、>=2*i,则结点i的左子女为2*i;(3)若n>=2*i+1,则结点i的右子女为2*i+112348567910（4）若结点编号i为奇数，且i!=1,则它的左兄弟为结点i-1。（5）若结点编号i为偶数，且i!=n,则它的右兄弟为结点i+1。（6）结点i所在层次为log2i+112348567910templateclassBinaryTree{public:BinaryTree();//构造函数BinaryTree(BinTreeNode*lch,BinTreeNode*rch,Typeitem);//构造以item为根，lch和rch为左、

8、右//子树的二叉树intIsEmpty();//判二叉树空否？BinTreeNode*Parent();//双亲二叉树的抽象数据类型BinTreeNode*LeftChild();//取左子女结点地址BinTreeNode*RightChild();//取右子女结点地址intInsert(constType&item);//插入intFind(constType