[数据结构与算法]链式二叉树的实现以及遍历

一、二叉树的二叉链表存储表示

//二叉树的二叉链表存储表示
typedef struct BiTNode
{
    ElemType data;//结点的数据域
    struct BiTNode *lchild, *rchild;//左右孩子指针
} BiTNode,*BiTree;

二、先序遍历的顺序创建二叉链表

算法步骤：

（1）扫描字符序列，读入字符ch

（2） 如果‘ch’是一个‘#’字符，则表明该二叉树为空树，即T为NULL；否则执行以下操作：

1）申请一个结点空间T；

2）将ch赋给T->data;

3）递归创建T的左子树；

4）递归创建递归的右子树；

void CreateBiTree(BiTree &T)
{
    //创建二叉链表表示的二叉树T
    char ch;
    cin>>ch;
    if(ch == '#')
    {
        T = NULL;
    }
    else
    {
        T = new BiTNode;//生成根结点
        T->data = ch;//根结点的数据域置为ch
        CreateBiTree(T->lchild);//递归创建左子树
        CreateBiTree(T->rchild);//递归创建右子树
    }
}

三、遍历二叉树

（1）先序遍历

//先序遍历二叉树
void PreOrderTraverse(const BiTree &T)
{
    if(T == NULL)
    {
        return;
    }
    else
    {
        cout<<"\t"<<T->data;
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);

    }
}

?（2）中序遍历

//中序遍历二叉树
void InOrderTraverse(const BiTree &T)
{
    if(T == NULL)
    {
        return;
    }
    else
    {
        InOrderTraverse(T->lchild);
        cout<<"\t"<<T->data;
        InOrderTraverse(T->rchild);
    }
}

（3）后序遍历

//后序遍历二叉树
void PostOrderTraverse(const BiTree &T)
{
    if(T == NULL)
    {
        return;
    }
    else
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout<<"\t"<<T->data;
    }
}

四、完整代码

?

#include <iostream>
#define ElemType char
using namespace std;
//typedef char ElemType;

//二叉树 Binary Tree

//二叉树的二叉链表存储表示
typedef struct BiTNode
{
    ElemType data;//结点的数据域
    struct BiTNode *lchild, *rchild;//左右孩子指针
} BiTNode,*BiTree;

//先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree &T)
{
    //创建二叉链表表示的二叉树T
    char ch;
    cin>>ch;
    if(ch == '#')
    {
        T = NULL;
    }
    else
    {
        T = new BiTNode;//生成根结点
        T->data = ch;//根结点的数据域置为ch
        CreateBiTree(T->lchild);//递归创建左子树
        CreateBiTree(T->rchild);//递归创建右子树
    }
}
//先序遍历二叉树
void PreOrderTraverse(const BiTree &T)
{
    if(T == NULL)
    {
        return;
    }
    else
    {
        cout<<"\t"<<T->data;
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);

    }
}
//中序遍历二叉树
void InOrderTraverse(const BiTree &T)
{
    if(T == NULL)
    {
        return;
    }
    else
    {
        InOrderTraverse(T->lchild);
        cout<<"\t"<<T->data;
        InOrderTraverse(T->rchild);
    }
}
//后序遍历二叉树
void PostOrderTraverse(const BiTree &T)
{
    if(T == NULL)
    {
        return;
    }
    else
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout<<"\t"<<T->data;
    }
}
void TestBiTree()
{
    BiTree T;
    cout<<"前序输入:";
    CreateBiTree(T);
    cout<<"\n前序输出：";
    PreOrderTraverse(T);
    cout<<"\n中序输出:";
    InOrderTraverse(T);
    cout<<"\n后序输出:";
    PostOrderTraverse(T);


}

int main()
{
    TestBiTree();
    return 0;
}