树

5.1 树的结构定义和基本操作

树(Tree)是n(n>=0)个结点的有限集。在一棵非空树中：
(1) 有且仅有一个特定的称为根的结点;
(2) 当n>1时其余结点可分为m(m>0)个互不相交的有限集T1,T2...Tm,其中,每一个集合
   本身 又是一棵树, 并且称为根的子树(subtree)例如,在图6.1中,(a)是只有一个根
   结点的树;(b)是有 13个结点的树,其中A是根,其余结点分成三个互不相交的子树：

树是一种数据结构 : Tree=(D,R) 其中：D是具有相同特性的数据元素的集合；若D只含一个数据元素,则R为空集,否则R是D上 个二元关系的集合，即R={H}。H为如下描述二元关系：

• (1) 在D中存在发唯一的称为根的数据元素,它在关系H下无前驱;

• (2) 若D-{root}≠φ，则存在D-{root}的一个划分D1,D2,...Dm(m>0),对任意一对j≠k     (l<=j,k<=m)有Dj∩Dk=φ，且对任意的i(l<=i<=m)，唯一存在数据元素Xi∈Di，有 ∈H;

• (3) 对应于D-{root}的划分，H-{ ,..., }有唯一的一个划分H1,H2,...，Hm(m>0),对任意一对j≠k(l<=j,K<=m)有，Hj∩Hk=φ，且对任意的i(l<=i<=m)Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。
  

树结构中的一些基本术语：

• 结点的度：结点拥有的子树数。

• 叶子（终端结点）：度为零的结点。

• 非终端结点（分支结点）：度不为零的结点。

• 树的度：树内各结点的度的最大值。

树的基本操作：

(1) INITIATE(T) 初始化操作，置T为空树。

(2) ROOT(T)\ROOT(X) 求根函数。求数T的根或求结点x所在的树的根结点。若T是空树或X不在任何一棵树上，则函数值为“空”。

(3) RARENT(T,x) 求双亲函数。求树T中结点x的双亲结点。若结点x是树T的根结点或结点x不在T中，则函数值为“空”。

(4) CHILD(T,x,i) 求孩子结点函数。求数T中结点x的第i个孩子结点。若结点x是树T的叶子或无第i个孩子或结点x不在树T中，则函数值为“空”。

(5) RIGHT_SINLING(T,x)求右兄弟函数。求树T中结点x右边的兄弟。若结点x是其双亲的最右边的孩子结点或结点x不在树T中，则函树值为“空”。

(6) CRT_TREE(x,F) 建树操作。生成一棵以X结点为根，以森F为子树森林的树。

(7) INS_CHILD(y,i,x) 插入子树操作。置以结点x为根的树为结点y的第i棵子树。若原树中无结点y或结点y的子树个数&gti-1，则空操作。

(8) DEL_CHILD(x,i) 删除子树操作。删除结点x的第i棵子树。若无结点x或结点x的子树个数&gti，则空操作。

(9) TRAVERSE(T) 遍历操作。按某个次序依此访问树中各个结点，并使每个结点只被访问一次。

(10) CLEAR(T) 清除结构操作。将树T置为空树。

5.2.1 二叉树定义与基本操作

   二叉树(binary tree)是另一种树型结构，它的特点是每个结点至多只有二棵子
树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒. 二叉树是一种数据结构 :

                       Binary_tree=(D,R)

其中：D是具有相同特性的数据元素的集合;若D等于空,则R等于空称为空的二叉树;若
D等于空则R是D上某个二元关系H的集合，即R={H}，且

(1)  D中存在唯一的称为根的元素r，它的关系H下无前驱;

(2)  若D-{r}不等于空，则D-{r}={Dl,Dr}，且Dl交Dr等于空;

(3)  若Dl不等于空,则在Dl中存在唯一的元素xl,〈r,xl〉属于H，且存在Dl上的关
        系Hl属于H；

        若Dr不等于空,则在Dr中存在唯一的元素xr,〈r,xr〉>属于H, 且存Dr上的关
        系Hr属于H；H={r,xl,＜r,xr＞,Hl, Hr};

(4)  (Dl, Hl)是一棵合本定义的二叉树，称为根r的左子树,(Dr,Hr)是一棵符合定
        义的二叉树，称为根的右子树。

   其中，图6.2 是各种形态的二叉树.

(1)为空二叉树  (2)只有一个根结点的二叉树  (3)右子树为空的二叉树  (4)左子树为空的二叉树  (5)完全二叉树

二叉树的基本操作：

(1)INITIATE(BT）  初始化操作。置BT为空树。

(2)ROOT(BT)\ROOT(x)  求根函数。求二叉树BT的根结点或求结点x所在二叉树的根结
   点。若BT是空树或x不在任何二叉树上，则函数值为“空”。

(3)PARENT(BT,x)  求双亲函数。求二叉树BT中结点x的双亲结点。若结点x是二叉树
   BT的根结点或二叉树BT中无x结点，则函数值为“空”。

(4)LCHILD(BT,x)和RCHILD(BT,x)  求孩子结点函数。分别求二叉树BT中结点x的左孩
   子和右孩子结点。若结点x为叶子结点或不在二叉树BT中，则函数值为“空”。

(5)LSIBLING(BT,x)和RSIBING(BT,x)  求兄弟函数。分别求二叉树BT中结点x的左兄弟
   和右兄弟结点。若结点x是根结点或不在BT中或是其双亲的左/右子树根,则函树值
   为“空”。

(6)CRT_BT(x,LBT,RBT)  建树操作。生成一棵以结点x为根，二叉树LBT和RBT分别为左，
   右子树的二叉树。

(7)INS_LCHILD(BT,y,x)和INS_RCHILD(BT,x)  插入子树操作。将以结点x为根且右子
   树为空的二叉树分别置为二叉树BT中结点y的左子树和右子树。若结点y有左子树/右
   子树，则插入后是结点x的右子树。

(8)DEL_LCHILD(BT,x)和DEL-RCHILD(BT,x)  删除子树操作。分别删除二叉树BT中以结
   点x为根的左子树或右子树。若x无左子树或右子树，则空操作。

(9)TRAVERSE(BT)  遍历操作。按某个次序依此访问二叉树中各个结点，并使每个结点
   只被访问一次。

(10)CLEAR(BT)  清除结构操作。将二叉树BT置为空树。

5.2.2  二叉树的存储结构

一 顺序存储结构
        连续的存储单元存储二叉树的数据元素。例如图6.4(b)的完全二叉树, 可以向量(一维数组 ) bt(1:6)作它的存储结构，将二叉树中编号为i的结点的数据元素存放在分量bt[i]中,如图6.6(a) 所示。但这种顺序存储结构仅适合于完全二叉树,而一般二叉树也按这种形式来存储,这将造成存 贮浪费。如和图6.4(c)的二叉树相应的存储结构图6.6(b)所示，图中以“0”表示不存在此结点.

二 链式存储结构
    由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构成,则表 示二叉树的链表中的结点至少包含三个域:数据域和左右指针域,如图(b)所示。有时,为了便于找 到结点的双亲,则还可在结点结构中增加一个指向其双亲受的指针域，如图6.7(c)所示。

5.3  遍历二叉树        

        遍历二叉树(traversing binary tree)的问题， 即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 其中常见的有三种情况：分别称之为先(根)序遍历，中(根)序遍历和后(根)序遍历。

5.3.1 前序遍历

    前序遍历运算：即先访问根结点，再前序遍历左子树，最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。例如：

    按前序遍历此二叉树的结果为：Hello!How are you?

proc preorder(bt:bitreprtr)

  if (bt<>null)[

    print(bt^);

    preorder(bt^.lchild);

    preorder(bt^.rchild);]

end;

5.3.2 中序遍历

    中序遍历运算：即先中前序遍历左子树，然后再访问根结点，最后再中序遍历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。例如：

    按中序遍历此二叉树的结果为：a*b-c

proc inorder(bt:bitreprtr)

  if (bt<>null)[

    inorder(bt^.lchild);

    print(bt^);

    niorder(bt^.rchild);]

end;

5.3.3 后序遍历

    后序遍历运算：即先后序遍历左子树，然后再后序遍历右子树，最后访问根结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。例如：

    按后序遍历此二叉树的结果为：Welecome to use it!

proc postorder(bt:bitreprtr)

  if (bt<>null)[

    postorder(bt^.lchild);

    postorder(bt^.rchild);]

    print(bt^);

end;