2.树的逻辑结构描述 棵树的逻辑结构可以用二元组描述为 tree=(k,R) k={k;|1sinn≥0.k;∈ elemtype R={r} 其中,n为树中结点个数,若n=0,则为一棵空树,n> 0时称为一棵非空树,而关系r应满足下列条件 (1)有且仅有一个结点没有前驱称该结点为树根 (2除根结点以外其余每个结点有且仅有一个直接前 驱: 3)树中每个结点可以有多个直接后继(孩子结点)
2．树的逻辑结构描述 一棵树的逻辑结构可以用二元组描述为： tree =(k,R) k={ki∣1≤i≤n;n≥0,kielemtype} R={r} 其中，n为树中结点个数，若 n=0，则为一棵空树， n> 0时称为一棵非空树，而关系 r 应满足下列条件： （1）有且仅有一个结点没有前驱,称该结点为树根; （2）除根结点以外,其余每个结点有且仅有一个直接前 驱; （3）树中每个结点可以有多个直接后继(孩子结点)
:例如,对图6-1(c)的树结构可以二元组表示为 K-A,B, C, D,E, F, G, H, I,J,K, L, Mi R={r} r={(A,B),(A,C),(A,D),(B,E),(B,F),(CG), (D,H),(D,I),(E,J),(E,K),(E,L),(HM) 3.树的基本运算 树的基本运算可以定义如下几种: (intree(&T) 初始化树T (2)root(T) 求树T的根结点
例如，对图6-1(c )的树结构,可以二元组表示为： K={A，B，C，D，E，F，G，H，I，J，K，L，M} R={r} r={(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)， (D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,M)} 3．树的基本运算 树的基本运算可以定义如下几种： (1) inittree(&T) 初始化树T。 (2) root(T) 求树T的根结点
3)parent(T,X) 求树T中,值为x的结点的双亲。 ((4)child(T, x, i) 求树T中,值为x的结点的第i个孩子。 (5)addchild(y,i, x) 把值为x的结点作为值为y的结点的第个孩子插入到树 (6)delchild(x, i) 删除值为x的结点的第i个孩子 traverse(T) 遍历或访问树T
(3) parent(T,x) 求树T中，值为x的结点的双亲。 (4) child(T,x,i) 求树T中，值为x的结点的第i个孩子。 (5) addchild(y,i,x) 把值为x的结点作为值为y的结点的第i个孩子插入到树 中。 (6) delchild(x,i) 删除值为x的结点的第i个孩子。 (7) traverse(T) 遍历或访问树T
612基本术语 1结点 指树中的一个数据元素,一般用一个字母表示。 2度 个结点包含子树的数目,称为该结点的度。 3树叶(叶子) 度为0的结点,称为叶子结点或树叶,也叫终端结 4孩子结点 若结点X有子树,则子树的根结点为X的孩子结点,也 称为孩子,儿子,子女等。如图6-1(c)中A的孩子为 B,C,D
6.1.2 基本术语 1.结点 指树中的一个数据元素，一般用一个字母表示。 2.度 一个结点包含子树的数目，称为该结点的度。 3.树叶（叶子） 度为0的结点，称为叶子结点或树叶，也叫终端结 点。 4.孩子结点 若结点X有子树，则子树的根结点为X的孩子结点，也 称为孩子，儿子，子女等。如图6-1（c）中A的孩子为 B，C，D
5双亲结点 若结点X有子女Y,则X为Y的双亲结点 6祖先结点 从根结点到该结点所经过分枝上的所有结点为该结点的 祖先,如图6-1(c)中M的祖先有A,D,H 入7子孙结点 某一结点的子女及子女的子女都为该结点子孙 8兄弟结点 具有同一个双亲的结点,称为兄弟结点
5.双亲结点 若结点X有子女Y，则X为Y的双亲结点。 6.祖先结点 从根结点到该结点所经过分枝上的所有结点为该结点的 祖先，如图6-1（c）中M的祖先有A，D ，H 。 7.子孙结点 某一结点的子女及子女的子女都为该结点子孙。 8.兄弟结点 具有同一个双亲的结点，称为兄弟结点