程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 線索二叉樹

線索二叉樹

編輯：C++入門知識

線索二叉樹的定義 n個結點的二叉鏈表中含有n+1個空指針域。利用二叉鏈表中的空指針域，存放指向結點在某種遍歷次序下的前趨和後繼結點的指針（這種附加的指針稱為"線索"）。
為了區分這個指針是指向前驅（或後繼）還是指向孩子節點的，我們需要加上標志 lTag，rTag 來區分
這種加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹(ThreadedBinaryTree)。
根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和後序線索二叉樹三種。

因為線索二叉樹保存了每個節點的前去後繼信心，對於需要頻繁查詢樹中節點的前驅，後繼的情況，線索二叉樹是個不錯的選擇

Code
[cpp]
#include<stdio.h>
#include<malloc.h>

typedef struct ThreadBiTreeNode
{
    char data;
    struct ThreadBiTreeNode *lChild;
    struct ThreadBiTreeNode *rChild;
    int lTag,rTag;
}BiTNode,*BiTree;

void CreateBTree(BiTree &biTree){
    char data;
    data = getchar();
    if(data=='0'){
        biTree = NULL;
    }
    else {
        biTree = (BiTree)malloc(sizeof(BiTNode));
        biTree->data = data;
        CreateBTree(biTree->lChild);
        CreateBTree(biTree->rChild);
    }
}

void InOrder(BiTree biTree){
    if(biTree != NULL){
        InOrder(biTree->lChild);
        printf("%c ",biTree->data);
        InOrder(biTree->rChild);
    }return ;
}

void InThreading(BiTree & p,BiTree & pre)
{
    if(p){
        InThreading(p->lChild,pre);

        if(!p->lChild){ //左孩子空，左孩子指針指向前驅
            p->lTag=1;
            p->lChild=pre;
        }
        else p->lTag=0;

        if(pre && !pre->rChild){ //前驅的右孩子空，前驅的右孩子指針指向後繼
            pre->rTag=1;
            pre->rChild=p;
        }

        pre = p;
        pre->rTag = 0;

        InThreading(p->rChild,pre);
    }
}

BiTree InOrderThreading(BiTree biTree)
{
    BiTree threadTree = new BiTNode;
    //新加的節點（頭節點），樹中沒有這個點
    //中序線索化出的鏈表的第一個節點的前驅（左孩子指針）指向這個頭節點，
    //同時鏈表最後一個節點的後繼（右孩子指針）也指向這個頭結點，
    //而這個頭結點的左孩子指針指向二叉樹的根節點，右孩子指針指向中序線索化鏈表的最後一個節點
    //類似雙向鏈表

    threadTree->lTag = 0;    //沒有左孩子
    threadTree->rTag = 1;    //有右孩子
    threadTree->rChild = threadTree; //右指針回指

    if(!biTree){//空樹左指針回指
        threadTree->lChild = threadTree;
    }
    else {
        threadTree->lChild = biTree;
        BiTree pre = threadTree;
        InThreading(biTree,pre);//中序線索化

        pre->rChild = threadTree;
        pre->rTag = 1;
        threadTree->rChild = pre;
    }
    return threadTree;
}

void InOrderTraverse_Thr(BiTree biTree)//中序遍歷線索二杈樹的非遞歸算法, biTree 指向頭結點
{
    BiTree p = biTree->lChild; //p指向根結點
    while (p != biTree) //空樹或遍歷結束時，p == biTree
    {
        //從根開始尋找第一個結點，中根序列第一個節點是沒有左孩子的，也就是lTag = 0
        //這點是區分中序線索化的標志，同樣的，其它的線索化也都根據相應的特點來做
        while (p->lTag == 0)
        {
            p = p->lChild;
        }
        printf("%c ",p->data);

        while (p->rTag == 1 && p->rChild != biTree)//訪問後繼結點
        {
            p = p->rChild;
            printf("%c ",p->data);
        }
        p = p->rChild;
    }
}

BiTree NewBTree(char x)//構造一個數據域為x的新結點
{
    BiTree s = new BiTNode;
    s->data = x;
    s->lChild = s->rChild = NULL;
    s->lTag = s->rTag = 0;
    return s;
}

void Insert(BiTree & b, BiTree s)//在二杈排序樹中插入新結點s
{
    if (b == NULL)
        b = s;
    //else if(b->data == s->data)//不做任何插入操作
    // return;
    else if(b->data > s->data)//把s所指結點插入到左子樹中
        Insert(b->lChild, s);
    else                    //把s所指結點插入到右子樹中
        Insert(b->rChild, s);
}

int main()
{
    BiTree biTree=NULL;
    //puts("Input:12300400500");
    puts("Input:ABD000CE00F00");
    /*********************
            A

        /       \

        B       C

    /       /       \

    D       E       F
    *********************/
    CreateBTree(biTree);

    puts("中根遍歷二叉樹（遞歸）：");
    InOrder(biTree);puts("");
    puts("");

    BiTree BT = InOrderThreading(biTree);

    puts("中根遍歷線索二叉樹（非遞歸）：");
    InOrderTraverse_Thr(BT);puts("");

    return 0;
}