首页 > 代码库 > 算法学习 - 线索二叉树

算法学习 - 线索二叉树

线索二叉树

线索二叉树就是在通用的二叉树里多了点东西,多了什么呢? 前驱和后继,把二叉树变成一个链式的结构。解释下:通常我们的二叉树里,叶子节点是没有孩子,所以指向空也就是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;
        }
    }
}

测试代码(main):

int main(int argc, const char * argv[]) {
    node head = (node)malloc(sizeof(struct TreeNode));
    head->data = http://www.mamicode.com/1;>

算法学习 - 线索二叉树