数据结构 二叉树的建立、遍历、销毁的递归算法(C语言)

hanyujianke 2019-11-01

这些是较为简单的二叉树的建立、遍历、销毁的递归算法。
假设二叉树都用二叉链作为存储结构,并约定根节点的指针用T表示。

为了简化问题,我们用char类型的字符代替树中的数据,并且用前序遍历的算法,建立二叉树过程如下:

  1. 输入一个根节点。
  2. 若输入的是“ ”(即空格字符),则表明改结点为空,T设置为NULL;
  3. 若输入的不是“ ”(空格字符),则将字符存入到T->data中,并依次递归建立它的左子树T->lchild,和右子树T->rchild;

测试的源代码如下:

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

typedef struct BTREE {
    char data;
    struct BTREE *lchild, *rchild;
}BT,*LBTREE;



void Creat(LBTREE *T)                        //前序遍历的递归算法
{
    char ch;
    ch=getchar();                            //从缓冲一个个读取字符
    if (ch == ‘ ‘)                //输入空格则该节点为空(即不存在)
        *T = NULL;                
    else
    {
        (*T) = (LBTREE)malloc(sizeof(BT));
        (*T)->data=ch;
        Creat(&((*T)->lchild));
        Creat(&((*T)->rchild));
    }

}

void Pretravers(LBTREE T)                    //前序遍历
{
    if (T != NULL)
    {
        printf("% c", T->data);
        Pretravers(T->lchild);
        Pretravers(T->rchild);
    }
    
}

void Inortravers(LBTREE T)                    //中序遍历
{
    if (T != NULL)
    {
        Inortravers(T->lchild);
        printf("% c", T->data);
        Inortravers(T->rchild);
    }
}

void Postravers(LBTREE T)                    //后续遍历
{
    if (T != NULL)
    {
        Postravers(T->lchild);
        Postravers   (T->rchild);
        printf("% c", T->data);
    }
}

void Distroyb(LBTREE T)            //销毁二叉树(同样使用递归的方式)
{
    if (T != NULL)
    {
        Distroyb(T->lchild);
        Distroyb(T->rchild);
        free(T);
    }
}

void main(void)
{
    LBTREE T=NULL;
    puts("输入二叉树数据");                        //这里用的是             
        getchar(),                                  //会读取换行符,应将所有数据在一行输入
    Creat(&T);
    puts("前序遍历输出:");
    Pretravers(T);
    puts("");
    puts("中序遍历输出:");
    Inortravers(T);
    puts("");
    puts("后续遍历输出:");
    Postravers(T);
    puts("");
    Distroyb(T);
}

结果如下:
数据结构 二叉树的建立、遍历、销毁的递归算法(C语言)

建立的二叉树是这样的:

数据结构 二叉树的建立、遍历、销毁的递归算法(C语言)

相关推荐