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

        遍历或者“走遍”一棵树的概念。（系统地考虑树的节点，使得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)，并重复这一步骤。否则终止算法。

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

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

LTAG	LLINK	INFO1
RTAG	RLINK	INFO2

        在无穿线树中，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。