文档介绍：:树:T是n个结点构成的有限集合(n>0),其中有一个结点叫根,其余结点可划分为m个互不相交的子集T1,T2,……,Tm(m≥0),并且这m个子集本身又构成树,称为T的子树。注意:这里没给出空树的概念。从树的定义可以看出,树的逻辑结构:(1)树的根结点没有前驱结点,除根结点之外的所有结点有且只有一个前驱结点。(2)树中所有结点可以有零个或多个后继结点。:图形表示法ABDEFGIHC嵌套集合表示法HIEDFBGCA凹入表表示法ABCDEFGHI广义表表示法(A(B(D,E(H,I),F),C(G))):1、孩子结点、双亲结点(父结点):某结点的子树的根为该结点的孩子结点,而该结点为其孩子结点的双亲结点。兄弟结点:同一结点的孩子为兄弟结点。可延伸到祖先结点和后代结点。2、一个结点的度:该结点的直接后继结点(孩子)的个数。树的度:树中最大的结点度。3、叶子结点(终结点):结点度为0。分支结点:结点度不为0。根结点:无直接前驱结点。:5、森林:多棵树。4、一个结点的层次:根为1,其余为父结点的层次数加1。树的深度:最大的结点层次数。6、有序树:树中各兄弟结点之间的排列次序是有关的。无序树:树中各兄弟结点之间的排列次序是无关的。:1、初始化树initial_tree(T):建立树的初始结构。2、插入子树insert_tree(T,S):将以S为根的子树作为T的第一个子树插入到树中。3、插入兄弟结点insert_sigling(T,S):将以S为根的树作为T的兄弟子树插入到树中。4、查询根结点rootof(T):查询结点T所在树的根结点。5、查询父结点fatherof(T):查询结点T的父结点。6、查询孩子结点childof(T):查询结点T的所有或某个孩子结点。7、查询兄弟结点siblingof(T):查询结点T的所有或某个兄弟结点。,其中n≥0,当n=0时,为空树,否则,其中有一个结点为根结点,其余结点划分为两个互不相交的子集TL、TR,并且TL、TR分别构成叫作左、右子树的二叉树。(即树中结点的最大度为2,每个结点的孩子有左、右之分)。:空树Ø单结点树右子树为空左子树为空左、:满二叉树:每层都有最大数目结点的二叉树。满二叉树:每层都有最大数目结点的二叉树。完全二叉树:在满二叉树的最下层从右向左连续地删除若干个结点所得到的二叉树。(满二叉树是完全二叉树的一个特例):在二叉树的第i层上的结点个数≤2i-1(i>0)。性质2:深度为k的二叉树的结点个数≤2k-1(k>0)。性质3:对任一棵非空的二叉树T,如果其叶子数为n0,度为2的结点数为n2,则有:n0=n2+1。性质4:有n个结点的完全二叉树(n>0)的深度为log2n+1。性质5:在编号的完全二叉树(根结点编号为1,顺序按从上到下、从左到右进行编号)中,各结点编号之间的关系为:i结点若有左孩子则其编号为2i,若有右孩子则其编号为2i+1,若有父结点则其编号为i/2。证明镁湃冶绿从睹炉膛负峻杭搐绵骇破铅戴封觉毗史薪棋嘿菌诵缆尾感詹耘凿树的基础知识树的基础知识