算法學習 - 線索二叉樹

線索二叉樹

線索二叉樹就是在通用的二叉樹裡多了點東西，多了什麼呢？ 前驅和後繼，把二叉樹變成一個鏈式的結構。解釋下：通常我們的二叉樹裡，葉子節點是沒有孩子，所以指向空也就是NULL，在線索二叉樹裡，葉子節點的左右孩子分別指向它自己的前驅和後繼，而前驅和後繼是哪個節點呢？ 就是樹遍歷過程的前一個節點和後一個節點。所以第一個遍歷的節點是沒有前驅的，最後一個節點是沒有後繼的。這裡一般都是中序線索二叉樹，當然也有先序線索二叉樹和後序線索二叉樹。

            []a[]
            /   \
         []b[] []c[]
         /   \   
      []d[] []e[]

上面是一個二叉樹，我在每個節點兩邊都添加了一個標簽[]這個標簽裡面我暫時還沒添內容，裡面只有兩種值，一個是0一個是1，當節點有孩子節點的時候，為0，沒有孩子的時候為1。
所以節點的結構體為：

typedef struct TreeNode* node;

struct TreeNode{
    node lchild;
    int ltag;
    int rtag;
    node rchild;
    int data;
};

當為0的時候，指向孩子節點，為1的時候指向前驅或者後繼。
下面附上代碼。

代碼實現

代碼如下：

node Pre = NULL;

void InOrderTree(node n){
    if (n == NULL) {
    }else{
        //        Pre = n;
        if (n->lchild != NULL) {
            n->ltag = 0;
            InOrderTree(n->lchild);
        }else{
            n->ltag = 1;
            n->lchild = Pre;
        }
        if (Pre!=NULL && Pre->rchild == NULL) {
            Pre->rtag = 1;
            Pre->rchild = n;
        }
        Pre = n;
        if (n->rchild != NULL) {
            n->rtag = 0;
            InOrderTree(n->rchild);
        }else{
            n->rtag = 1;
        }
    }
}

int main(int argc, const char * argv[]) {
    node head = (node)malloc(sizeof(struct TreeNode));
    head->data = 1;
    node node1 = (node)malloc(sizeof(struct TreeNode));
    node node2 = (node)malloc(sizeof(struct TreeNode));
    node node3 = (node)malloc(sizeof(struct TreeNode));
    node node4 = (node)malloc(sizeof(struct TreeNode));
    node1->data = 2;
    node2->data = 3;
    node3->data = 4;
    node4->data = 5;
    head->lchild = node1;
    head->rchild = node2;
    node1->lchild = node3;
    node1->rchild = node4;
    node2->lchild = NULL;
    node2->rchild = NULL;
    node3->lchild = NULL;
    node3->rchild = NULL;
    node4->lchild = NULL;
    node4->rchild = NULL;
    InOrderTree(head);
    return 0;
}