二叉树的存储结构遍历二叉树 （Binary Tree Traversal）线.ppt

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

1、树的定义和基本术语二叉树(BinaryTree)二叉树的存储结构遍历二叉树(BinaryTreeTraversal)线索化二叉树(ThreadedBinaryTree)树与森林(Tree&Forest)赫夫曼树(HuffmanTree)二叉树的计数第6章树和二叉树6.1树的定义和基本术语1.树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则:有一个特定的称之为根(root)的结点，它只有后继，但没有前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合本身又是一棵树，并且称之为根的子树(subTree)。每棵

2、子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。结点(node)结点的度(degree)分支(branch)结点叶(leaf)结点孩子(child)结点双亲(parent)结点兄弟(sibling)结点祖先(ancestor)结点子孙(descendant)结点结点所处层次(level)树的深度(depth)树的度(degree)有序树无序树森林1）度（次数、级）（1）结点的度：一个结点所拥有的子数的个数（2）树的度：树内各结点的度的最大值2）描述上下及左右的关系孩子结点：一个结点的子树的根双亲结点：P120兄弟结点：同一个双亲的孩子之间互称兄弟祖先：结点的祖先是从根到该结点所

3、经分支上的所有结点子孙：P120结点的后代3）层次（1）结点的层次（2）树的深度（高度）2.树的基本术语树的基本操作：p119树的建立和遍历——重点树的抽象数据类型6.2二叉树(BinaryTree)二叉树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。特点：1）每个结点的度≤2；2）是有序树基本操作：p121~p123二叉树的建立和遍历二叉树的抽象数据类型性质1若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i1)[证明用数学归纳法]性质2深度为k的二叉树最多有2k-

4、1个结点。(k1)[证明用求等比级数前k项和的公式]性质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同理：三次树：n0=1+n2+2n3四次树：n0=1+n2+2n3+3n4…K次树：n0=1+n2+2n3+…+(k-1)nk定义1满二叉树(FullBinaryTree)定义2完全二叉树(CompleteBinaryTree)若设二叉树的

5、深度为h，则共有h层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。性质4具有n个结点的完全二叉树的深度为log2n+1证明：设完全二叉树的深度为k，则有2k-1-1

6、根，无双亲若i>1,则i的双亲为i/2若2*i≤n,则i的左孩子为2*i，否则无左孩子若2*i+1≤n,则i的右孩子为2*i+1，否则无右孩子若i为偶数,且i!=n,则其右兄弟为i+1若i为奇数,且i!=1,则其左兄弟为i-1i所在层次为log2i+1完全二叉树的数组表示一般二叉树的数组表示二叉树的存储结构1.顺序存储结构（数组表示）#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。单支树2.链

7、式存储结构typedefstructBiTNode{//二叉链表的定义TElemTypedata;StructBiTNode*lchild,*rchild;}BiTNode,*BiTree;二叉树链表表示的示例3.静态二叉链表和静态三叉链表预先开辟空间，用数组表示leftChild,rightChild——数组元素的下标6.3遍历二叉树(TraversingBinaryTree)p128所谓树的遍历，就是按某种次序访问树中的结点，要