树的定义与基本概念 二叉树 二叉树遍历 二叉树的计数 线索化.ppt

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

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

2、IJ1层2层4层3层depth=4ACGBDEFKLHMIJ结点结点的度分支结点叶结点子女双亲兄弟祖先子孙结点层次树的度树深度森林二叉树(BinaryTree)二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。LLRR性质1若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i0)[证明用数学归纳法]性质2深度为h的二叉树最多有2h-1个结点。(h0)[证明用求等比级数前k项和的公式]21+22+23+

3、…+2h-1=2h-1二叉树的性质性质3对任何一棵二叉树,如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0＝n2＋1证明：若设度为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层。除第h层外，其它各层(1h-1)的结点数都达到最大个数，第h层从右向左连

4、续缺若干结点，这就是完全二叉树。性质4具有n(n0)个结点的完全二叉树的深度为log2(n+1)证明：设完全二叉树的深度为h，则有2h-1-11,则i的双亲为i/2若2*i

5、，若2*i+1

6、tdatalchildrchild三叉链表二叉树链表表示的示例AAABBBCCCDDDFFFEEErootrootroot二叉树二叉链表三叉链表三叉链表的静态结构ABCDFErootdataparentlchildrchild012345A-11-1B023C1-1-1D145E3-1-1F3-1-1typedefcharTElemType;//树结点数据类型typedefstructnode{//树结点定义TElemTypedata;//结点数据域structnode*lchild,*rch

7、ild;//子女指针域}BinTreeNode;typedefBinTreeNode*BinTree;//树定义，代表树的根指针二叉树的定义二叉树遍历树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作V遍历根的左子树记作L遍历根的右子树记作R则可能的遍历次序有前序VLR镜像VRL中序LVR镜像RVL后序LRV镜像RLV中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果a+b*c-d-e/f中序遍历(Inorde

8、rTraversal)--/+*abcdefvoidInOrder(BinTreeNode*T){if(T!=NULL){InOrder(T->lchild);visit(T->data);InOrder(T->rchild);}}二叉树递归的中序遍历算法前序遍历二叉树算法的框架是：若二叉树为空，则空操