计算机程序设计艺术一二叉树

概念：

        一个有限的节点集合，它或者为空，或者由一个根连同两个二叉树组成。

二叉树的自然方法：

        在每个节点内，有两个链接，LLINK和RLINK以及作为“指向树的指针”的链接变量T(T是NULL或者指向根节点)。如果这棵树为空，T = NULL；否则T是树的根节点的地址，而LLINK(T)和RLINK(T)分别是指向根的左子树和右子树的指针。

自然方法的实现示意图：

对树的操作：

        遍历或者“走遍”一棵树的概念。（系统地考虑树的节点，使得3每个节点恰被访问一次的方法。）         常用的遍历二叉树的方法：先根序、中根须、后根序（皆为递归）。

遍历过程：

1.当二叉树为空时，什么都不做；否则进入2

2. 先根序中根序后根序访问根遍历左子树遍历左子树遍历左子树访问根遍历右子树遍历右子树遍历右子树访问根

遍历算法：

1.中根序遍历二叉树：

        使用了辅助栈A。         T1.【初始化】置栈A为空，并置链接变量P = T；         T2.【P = NULL ？】如果p = NULL,转到步骤T4；         T3.【将P中值放入栈A】（现在P指向要加以遍历的一个非空二叉树）将P放入A;然后置P = LLINK(P)并返回到        T2。         T4.【将A中缓存的值放入P】如果栈A为空，则算法终止：否则置P = A         T5.【访问P】访问NODE(P)，然后置P = RLINK(P),并返回到步骤T2。                  以下为流程图：

代码实现算法：

//代码实现二叉树中序根遍历 /* *节点 */ typedef struct node { int values; struct node *llink; struct node *rlink; }node, *node_p; node_p T; //指针 node_p A;//上一个节点 void inorder_traversal() { node_p p; A = NULL; p = T; while(true) { while(p != NULL) { A = p; p = p->llink; } if(A = NULL) { return; } else { p = A; } printf(" %d \n", p->values);//NODE(p) p = p->rlink; } } //end

2.先根序遍历二叉树：

        书上说是，用几乎一样的算法可以设计先根序遍历的算法。

        我猜一下：

        利用一个辅助栈A,存储上一个节点的地址,访问NODE(p)的意思就是访问当前p指向的节点。它的位置决定了算法是先序还是中序.         R1.【初始化】置栈A为空，并置链接变量p = T;         R2.【p = NULL?】如果A为空，转到步骤R4;         R3.【访问p】置A =p,访问NODE(p),然后置p = LLINK(p);并放回步骤R2;         R4.【将栈中的值置入p】如果栈A为空，则算法终止；否则置将栈中的值置入p;         R5.【转向右子树】 p = RLINK(p).转到R2.

代码实现

//代码实现 void preorder_travering() { node_p p; A = NULL; p = T; while(true) { while(p != NULL) { A = p; printf(" %d \n", p->values);//NODE(p) p = p->llink; } if(A = NULL) { return; } else { p = A; } p = p->rlink; }

}

为了描述方便引入的标号：

        p* = 先根序下NODE(p)的后继的 地址；         p$ = 在中根序下的NODE(p)的后继的地址；         p# = 在后根序下NODE(p)的后继的地址;         *p = 在先根序下的NODE(p)的前驱的地址；         $p = 在中根序下的NODE(p)的前驱的地址         #p = 在后根序下的NODE(p)的前驱的地址.         令INFO(p)是树中的NODE(p)的值部分。

        如果NODE(p)没有这样的后继或前驱，一般使用LOC(T)的 值，其中T是指向根节点的指针 。

引入标号之后产生的公式：

*(p*) = (*p)* = p，$(sp$) = ($p)$ = p,#(p#) = (#p)# = p。

标号和二叉树举例：

其中，穿线二叉树是，带有链接前驱后继的虚线的二叉树。 算法S：(在穿线二叉树中的对称序(中根序)后继) 如果P指向穿线二叉树的一个节点，这个算法置Q = P$。 S1.【RLINK(p)是一个穿线吗?】置Q = RLINK(p)。如果RTAG(p) = 2终止算法. S2.【向左搜索】如果LTAG(Q) = 0，置Q = LLINK(Q)，并重复这一步骤。否则终止算法。

穿线二叉树计算机表示举例：

        程序表示穿线二叉树时，节点设计为双字：

LTAGLLINKINFO1RTAGRLINKINFO2

        在无穿线树中，LTAG和RTAG将总是“+”表示，而终端链接将通过零表示。在穿线树中，将使用“+”来代表0，用“-”代表1。

算法：（插入到穿线二叉树中）如果树为空（即如果RTAG(p) = 1）,这个算法就把节点NODE(Q)作为NODE(p)的右子树附加上来；否则就把NODE(Q)插到NODE(p)和NODE(RLINK(p))之间，使得后一节成为NODE(Q)的右子节点。假定发生插入的二叉树是上边图中那样。         I1.【调整标志和链接】RLINK(Q) = RLINK(p)，RTAG(Q) = RTAG(p)，RLINK(p) = Q,RTAG(p) = 0, LLINK(Q) = p, LTAG(Q) = 1;         I2.【RLINK(p)是穿线吗?】如果RTAG(Q) = 0,置LLINK(Q$) = Q。（这里Q$由算法S确定，即使LLINK(Q$)现在指向NODE(p)而不是NODE(Q)，它仍将正确地工作。仅当插入到穿线的中间而不仅仅是插入新叶的这个步骤必要。）

森林和二叉树的自然对应：

通过某种变换过程，任何二叉树对应于着一个森林。

森林转二叉树的转换描述：

        令F = (T1, T2, T3, ... ，Tn)是树的森林。对应于F的二叉树B(F)可严格地定义如下：         a)如果n = 0，则B(F)为空。         b)如果n > 0，则B(F)的根是root(T1)；B(F)的左子树是B(T11, T12,...,T1m),其中T11,T12,...,T1m是root(T1)的子树；且B(F)的右子树是B(T2,..., Tn)。

复制一个二叉树的算法：

设HEAD是一个二叉树T的表头地址。于是，T是通过LLINK(HEAD)抵达的HEAD的左子树。令NODE(U)是带有空左子树的一个节点。这个算法给出T的一个副本而且这个副本变成NODE(U)的左子树。如果NODE(U)是一个空的二叉树的表头，则这个算法把空树变成为T的一个副本。 C1.【初始化】置P = HEAD，Q = U。转到C4。 C2.【右边有任何东西？】如果NODE(P)有一个非空的右子树，置R = AVAIL，并把NODE(R)附加到NODE(Q)的右边。(在步骤C2开始时，NODE(Q)的右子树为空) C3.【复制INFO】置INFO(Q) = INFO(P)。(注：INFO和以前的意思有点不一样，这里表示节点中除链接之外的所有部分) C4.【左边有任何东西?】如果NODE(P)有一个非空的左子树，置R = AVAIL,并把NODE(R)附加到NODE(Q)的左边。(注：在步骤4开始前，NODE(Q)的左子树为空) C5.【前推】置P = P*, Q = Q*。 C6.【检查完成否】如果P = HEAD（或等价地如果Q = RLINK(U),假定NODE(U)有一个非空的右子树），算法结束；否则转到步骤C2。