二叉树前中后遍历递归与非递归版本(数据结构课程必写代码,纯手写)

欢迎访问我的主页!http://godweiyang.com edited 3 年,5 月前

/*******************二叉树各种操作*********************/

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

typedef struct BiTreeNode
{
    char data;
    struct BiTreeNode* lchild, * rchild;
}BiTreeNode;

/**创建二叉树结点**/

BiTreeNode* CreatBiTreeNode(char x)
{
    BiTreeNode* node = (BiTreeNode* )malloc(sizeof(BiTreeNode));
    node->data = x;
    node->lchild = node->rchild = NULL;
    return node;
}

/**创建二叉树(先序输入)**/

BiTreeNode* CreatBiTree()
{
    char x;
    BiTreeNode* root;
    scanf("%c", &x);
    getchar();
    if (x == '0')
        root = NULL;
    else
    {
        root = (BiTreeNode* )malloc(sizeof(BiTreeNode));
        root->data = x;
        root->lchild = CreatBiTree();
        root->rchild = CreatBiTree();
    }
    return root;
}

/**在指定结点左孩子处插入新结点**/

void Insert_lBt(BiTreeNode* parent, char x)
{
    BiTreeNode* ptr = CreatBiTreeNode(x);
    if (ptr->lchild)
    {
        ptr->lchild = parent->lchild;
        parent->lchild = ptr;
    }
    else
        parent->lchild = ptr;
}

/**在指定结点右孩子处插入新结点**/

void Insert_rBt(BiTreeNode* parent, char x)
{
    BiTreeNode* ptr = CreatBiTreeNode(x);
    if (ptr->rchild)
    {
        ptr->rchild = parent->rchild;
        parent->rchild = ptr;
    }
    else
        parent->rchild = ptr;
}

/**先序遍历非递归**/

void Pre_Bt(BiTreeNode* Bt)
{
    int Ss_top = 0;
    BiTreeNode* ptr = Bt;
    BiTreeNode* Ss[1000];
    while (Ss_top >= 0)
    {
        while (ptr)
        {
            printf("%c ", ptr->data);
            if (ptr->rchild)
                Ss[Ss_top++] = ptr->rchild;
            ptr = ptr->lchild;
        }
        if (Ss_top-- > 0)
            ptr = Ss[Ss_top];
    }
    printf("\n");
}

/**先序遍历递归**/

void Pre_BtRec(BiTreeNode* Bt)
{
    if(Bt)
    {
        printf("%c",Bt->data);
        Pre_BtRec(Bt->lchild);
        Pre_BtRec(Bt->rchild);
    }
}

/**中序遍历非递归**/

void In_Bt(BiTreeNode* Bt)
{
    int Ss_top = 0;
    BiTreeNode* ptr = Bt;
    BiTreeNode* Ss[1000];
    while (Ss_top >= 0)
    {
        while (ptr)
        {
            Ss[Ss_top++] = ptr;
            ptr = ptr->lchild;
        }
        if (Ss_top-- > 0)
        {
            ptr = Ss[Ss_top];
            printf("%c", ptr->data);
            ptr = ptr->rchild;
        }
    }
    printf("\n");
}

/**中序遍历递归**/

void In_BtRec(BiTreeNode* Bt)
{
    if(Bt)
    {
        In_BtRec(Bt->lchild);
        printf("%c",Bt->data);
        In_BtRec(Bt->rchild);
    }
}

/**后序遍历非递归**/

void Post_Bt(BiTreeNode* Bt)
{
    int Ss1_top = 0, Ss2_top = 0, Ss2[1000], flag;
    BiTreeNode* ptr = Bt;
    BiTreeNode* Ss1[1000];
    while (Ss1_top >= 0)
    {
        while (ptr)
        {
            Ss1[Ss1_top++] = ptr;
            Ss2[Ss2_top++] = 0;
            ptr = ptr->lchild;
        }
        if (Ss1_top-- > 0)
        {
            flag = Ss2[--Ss2_top];
            ptr = Ss1[Ss1_top];
            if (!flag)
            {
                Ss1[Ss1_top++] = ptr;
                Ss2[Ss2_top++] = 1;
                ptr = ptr->rchild;
            }
            else
            {
                printf("%c", ptr->data);
                ptr = NULL;
            }
        }
    }
    printf("\n");
}

/**后序遍历递归**/

void Post_BtRec(BiTreeNode* Bt)
{
    if(Bt)
    {
        Post_BtRec(Bt->lchild);
        Post_BtRec(Bt->rchild);
        printf("%c",Bt->data);
    }
}

/**根据二叉树先序和中序遍历生成二叉树**/

BiTreeNode* CreatBTFromPreIn(char* Pre, char* In, int len)
{
    BiTreeNode* root = (BiTreeNode* )malloc(sizeof(BiTreeNode));
    if (len <= 0)
    {
        root = NULL;
        return root;
    }
    root = CreatBiTreeNode(*Pre);
    int i;
    for (i = 0; i < len; ++i)
        if (*Pre == *(In+i))
            break;
    root->lchild = CreatBTFromPreIn(Pre+1, In, i);
    root->rchild = CreatBTFromPreIn(Pre+1+i, In+i+1, len-i-1);
    return root;
}

/*****************************************************************************/

typedef struct BiTreeNode1
{
    char data;
    int ltag, rtag;
    struct BiTreeNode1* lchild, * rchild;
}BiTreeNode1;

/**创建二叉树(先序输入)**/

BiTreeNode1* CreatBiTree1()
{
    char x;
    BiTreeNode1* root;
    scanf("%c", &x);
    getchar();
    if (x == '0')
        root = NULL;
    else
    {
        root = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
        root->data = x;
        root->lchild = CreatBiTree1();
        root->rchild = CreatBiTree1();
    }
    return root;
}

/**中序线索化二叉树**/

BiTreeNode1* InPre;//全局指针变量用于指向中序遍历过程中的直接前驱结点

void InThread(BiTreeNode1* Bt)
{
    if (Bt)
    {
        InThread(Bt->lchild);
        if (Bt->lchild == NULL)
        {
            Bt->lchild = InPre;
            Bt->ltag = 1;
        }
        else
            Bt->ltag = 0;
        if (InPre->rchild == NULL)
        {
            InPre->rchild = Bt;
            InPre->rtag = 1;
        }
        else
            InPre->rtag = 0;
        InPre = Bt;
        InThread(Bt->rchild);
    }
}

BiTreeNode1* Cr_InThread(BiTreeNode1* Bt)//为BT所指的二叉树添加头结点
{
    BiTreeNode1* root = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
    root->data = '0';
    root->ltag = 0;
    root->rtag = 1;
    root->rchild = Bt;
    if (Bt == NULL)
        root->lchild = root;
    else
    {
        root->lchild = Bt;
        InPre = root;
        InThread(Bt);
        InPre->rchild = root;
        InPre->rtag = 1;
        root->rchild = InPre;
    }
    return root;
}

/**基于中序线索二叉树,求指定节点在中序序列中的前驱**/

BiTreeNode1* InLtr_F(BiTreeNode1* ptr)
{
    BiTreeNode1* qtr = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
    if (ptr->ltag == 1)
        return ptr->lchild;
    else
    {
        qtr = ptr->lchild;
        while (qtr->rtag)
            qtr = qtr->rchild;
        return qtr;
    }
}

/**基于中序线索二叉树,求指定节点在中序序列中的后继**/

BiTreeNode1* InLtr_N(BiTreeNode1* ptr)
{
    BiTreeNode1* qtr = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
    if (ptr->rtag == 1)
        return ptr->lchild;
    else
    {
        qtr = ptr->rchild;
        while (qtr->ltag)
            qtr = qtr->lchild;
        return qtr;
    }
}

/**对中序线索二叉树进行中序遍历**/

void Ltr_Thread(BiTreeNode1* Bt)
{
    BiTreeNode1* ptr = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
    BiTreeNode1* qtr = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
    ptr = Bt;
    if (ptr)
    {
        while (ptr->ltag == 0)
            ptr = ptr->lchild;
        while (ptr && ptr->data != '0')
        {
            printf("%c", ptr->data);
            if (ptr->rtag == 1)
                ptr = ptr->rchild;
            else
            {
                qtr = ptr->rchild;
                while (qtr->ltag == 0)
                    qtr = qtr->lchild;
                ptr = qtr;
            }
        }
    }
}

int main()
{
    BiTreeNode1* Bt = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
    Bt = Cr_InThread(CreatBiTree1());
    Ltr_Thread(Bt);
    return 0;
}

Comments

你当前正在回复 博客/题目
存在问题!