首页 > 代码库 > 【数据结构】中序遍历线索二叉树

【数据结构】中序遍历线索二叉树

2024-07-04 22:30:24   225人阅读

昨天写了个二叉树遍历，自以为对二叉树很了解了。自大的认为线索二叉树不过是加了点线索而已，不足挂齿。可是当真的自己编程序写的时候才发现完全不是那么容易。在有线索的情况下，如何判别Link类型的下一节点，如何不用栈跳过已访问节点搞得脑子晕晕的。 折腾一个晚上，才根据书上把线索二叉树的建立、中序遍历给写出来。要回去继续好好的理清关系。

#include <stdio.h>
#include <stdlib.h>

typedef enum PointerTag{Link, Thread};

typedef struct BiThrNode
{
    int data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
}BiThrNode, *BiThrTree;

int createBinaryTree(BiThrTree &T)  //线索二叉树建立
{
    int ch;
    scanf("%d", &ch);

    if(ch != 0)
    {
        T = (BiThrTree)malloc(sizeof(BiThrNode));
        T->data =http://www.mamicode.com/ ch;
        createBinaryTree(T->lchild);
        createBinaryTree(T->rchild);
    }
    else
    {
        T = NULL;
    }
    return 0;
}

int InTreading(BiThrTree T, BiThrTree &pre) //中序线索建立 内
{
    if(T != NULL)
    {
        InTreading(T->lchild, pre);
        if(T->lchild == NULL){ T->LTag = Thread; T->lchild = pre;}
        else{ T->LTag = Link;}
        if(pre->rchild == NULL){ pre->RTag = Thread; pre->rchild = T;}
        else{ T->RTag = Link;}
        pre = T;
        InTreading(T->rchild, pre);
    }
    return 0;
}
int InOrderThreading(BiThrTree & Thrt, BiThrTree T) //中序线索建立 外
{
    BiThrTree pre;
    Thrt= (BiThrTree)malloc(sizeof(BiThrNode));
    Thrt->LTag = Link; Thrt->RTag = Thread;
    Thrt->rchild = Thrt;
    if(T == NULL) Thrt->lchild = Thrt;
    else
    {
        Thrt->lchild = T; pre = Thrt;
        InTreading(T, pre);
        pre->rchild = Thrt; pre->RTag = Thread;
        Thrt->rchild = pre;

    }
    return 0;
}

int visit(int data)
{
    printf("%d ", data);
    return 0;
}

int InOrderTraverse_Thr(BiThrTree T) //中序非递归线索二叉树遍历
{
    BiThrTree p = T->lchild;
    while(p != T)
    {
        while(p->LTag == Link) p = p->lchild;
        visit(p->data);
        while(p->RTag == Thread && p->rchild != T)
        {
            p = p->rchild; visit(p->data);
        }
        p = p->rchild;
    }
    return 0;
}

int main()
{
    BiThrNode TT;
    BiThrTree T, Thrt;
    
    createBinaryTree(T);
    InOrderThreading(Thrt, T);
    InOrderTraverse_Thr(Thrt); //注意遍历的时候要带上头结点
    return 0;
}

 


联系
我们