资源描述：
《数据结构 树和二叉树new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Ch6树和二叉树°有关树的概念树的定义树(tree)是n(n≥0)个结点的有限集T，对任一非空树：•有且仅有一个特定的结点，称为树的根(root);•当n>1时，其余结点可分为m(m>0)个互不相交的有限集T,T,⋅⋅⋅,T，其中每一个集合本身又是一棵树，称为12m根的子树(subtree).A只有根结点的树A根(root)树本质上是子树T1T2T3一个递归的概念BCDEFGHIJKLM有子树的树°有关树的概念树的常用术语•结点(node)表示树中的元素，包括数据项及若干指向其子树的分支•结点的度
2、(degree)结点拥有的非空子树数树的度一棵树中所有结点的度的最大值•叶子(leaf)度为0的结点•结点的孩子(child)一个结点的子树的根称为该结点的孩子孩子的双亲(parents)该结点本身•兄弟(sibling)同一双亲的孩子间的互称结点的子孙(descendant)以某结点为根的子树中的任一结点•结点的层次(level)从根结点算起，根为第一层，其孩子为第二层⋅⋅⋅若某结点处在第L层，则其子树的根为第L+1层•深度/高度(depth/height)树中结点的最大层次数•森林(fores
3、t)m(m≥0)棵互不相交的树的集合°有关树的概念树的常用术语例示说明结点A的度：3叶子：K,L,F,G,M,I,J结点B的度：2结点M的度：0树的度：3结点B,C,D为兄弟A结点K,L为兄弟结点A的孩子：B,C,D结点B的孩子：E,F结点D的子孙：H,I,J,MBCD结点C的双亲：A结点E的双亲：BEFGHIJ树的深度：4KLM结点A的层次：1结点F,G为堂兄弟结点M的层次：4结点A是结点F,G的祖先°二叉树(binarytree)的定义及性质二叉树的定义是n(n≥0)个结点的有限集，它或为空树
4、(n=0)，对非空树有:•有一个称之为根的结点•除根结点外的其余结点分为两棵互不相交的分别称为左子树(left)和右子树(right)的二叉树构成Note•每个结点至多有二棵子树(即不存在度大于2的结点)•二叉树的子树有左、右之分，且其次序不能任意颠倒•有5种基本形状:Φ空二叉树只有根结点的二叉树右子树为空左子树为空左、右子树均非空二叉树的性质•二叉树的第i(i≥1)层上至多有2i-1个结点[用归纳法证明]性质3证明:设二叉树的总结点数为(第i-1层上至多有2i-2,则第n,则i层n=n2×2+n
5、i-2=2+ni-1)1012•深度为又因为含k(kn≥1)个结点的二叉树中除根结点外的二叉树至多有2k−1个结点,其余n-1个结点均各有一条分支指向它,k即含n个结点的二叉树有(=20+21+22+⋅⋅⋅+2k-1=Σ(第i层上的最大结点数)n-1条分支:n-1=n×0+n×1+n×22k01i=12由=12Σ2得i-1:n=2k=n−1)+102i=1•在任意二叉树中，若叶结点(即度为0)数为n，度为1结点数0为n，度为2结点数为n，则有n=n+11202°二叉树(binarytree)的定义
6、及性质两种特殊形态的二叉树---FullBinaryTree、CompleteBinaryTree满二叉树的含义及特点定义深度为k且含有2k−1个结点的二叉树特点每一层上的结点数都是最大结点数2i-1,满二叉树中没有度=1的结点完全二叉树的含义及特点定义深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应(n≤2k−1).特点1.满二叉树是完全二叉树,但完全二叉树不一定是满二叉树2.叶结点只可能在层次最大的两层上出现,即至多只有最下面两层上结点的度可以
7、小于2,且最下层上的结点均集中在该层最左边的若干位置上3.对任一结点，若其右分支下子孙的最大层次为L,则其左分支下子孙的最大层次必为L或L+111112323232345674545645VVUU°二叉树(binarytree)的定义及性质当logn为非整数时,2二叉树的性质•含有n个结点的完全二叉树的深度是⎣log2n⎦+1(=⎡log2n⎤)(设该完全二叉树的深度为k,则根据完全二叉树的定义可知,其前k−1层是深度为k−1的满二叉树,共有2k-1−1个结点;又由性质2有n≤2k−1,综合得:2
8、k-1−11，则其双亲是⎣i/2⎦;2)如果2i>n，则结点i无左孩子；如果2i≤n，则其左孩子是2i;3)如果2i+1>n，则结点i无右孩子；如果2i+1≤n，则其右
