【数据结构】二叉树结点插入和前序、中序、后序遍历的递归实现

1.二叉树结点定义

struct node{
    int data;     //int可换成其他的数据类型
    struct node* left;
    struct node* right;
};

每一个二叉树结点都有一个数据域，一个左指针和一个右指针。叶子结点的左指针和右指针均为NULL。

2.结点插入操作

结点插入可以分为两个操作，一个实现创建新结点，一个实现在合适的位置插入操作。

2.1创建新结点

struct node* newNode(int data)
{
    struct node* a = new node;
    a->data = data;
    a->left = NULL;
    a->right = NULL;
    return a;
}

实现非常简单，即申请一个新结点；给新结点数据域赋值；将新结点 left 指针和 right 指针置NULL；返回结点指针。

2.2插入操作

struct node* insert(struct node* node,int data)
{
    if(node==NULL)
        return newNode(data);
    else
    {
        if(data<=node->data)
            node->left=insert(node->left,data);
        else
            node->right=insert(node->right,data);

        return node;//注意return node的位置
    }
}

插入操作分为三步：

判断传进来的结点指针是否为NULL，如果为NULL则调用newNode()函数，创建一个新结点，并返回新结点的结点指针。
如果传进来的结点指针不为NULL，判断data和node->data的大小，如果data<=node->data，则调用insert(node->left,data)函数在node的左子树插入结点，如果data>node->data，则调用insert(node->right,data)函数在node的右子树插入结点。
返回根节点地址。

3.树的前序遍历

void PreOrderVisit(struct node* node)
{
    if(node==NULL)
        return;
    else
        {
            cout<<node->data<<' ';
            PreOrderVisit(node->left);
            PreOrderVisit(node->right);
        }   
}

该过程可分为两步：

判断传入的指针是否为NULL，如果为NULL，则返回(即退出遍历函数)。
如果传入的指针不为NULL，则打印node数据，接着遍历node的左子树，然后遍历其右子树。

4.树的中序遍历和后序遍历

4.1中序遍历

由树的前序遍历我们就可以知道中序遍历该怎样操作，那就是将cout<<node->data<<' ';和PreOrderVisit(node->left);调换一下位置即可(当然PreOrderVisit()函数也要相应的变成InOrderVisit()函数)，即：

void InOrderVisit(struct node* node)
{
    if(node==NULL)
        return;
    else
        {
            InOrderVisit(node->left);
            cout<<node->data<<' ';
            InOrderVisit(node->right);
        }   
}

4.2后序遍历

同样的，后序遍历即将cout<<node->data<<' ';放到最后面即可，即：

void PostOrderVisit(struct node* node)
{
    if(node==NULL)
        return;
    else
        {
            PostOrderVisit(node->left);
            PostOrderVisit(node->right);
            cout<<node->data<<' ';
        }   
}

5.验证

下面给出一个完整的程序例子，验证结果是否正确。

程序代码：

#include<iostream>
using namespace std;
struct node{
    int data;
    struct node* left;
    struct node* right;
};
void visit(struct node* node);
struct node* newNode(int data);
struct node* insert(struct node* node,int data);
void PreOrderVisit(struct node* node);
void InOrderVisit(struct node* node);
void PostOrderVisit(struct node* node);
int main()
{
        node* BT = new node;   //申请结点
        int n,m;
        cin>>n;           //n为树的结点总数
        cin>>m;
        BT->data = m;     //给根结点赋值
        BT->left =NULL;   //根结点指针置NULL
        BT->right=NULL;
        //插入n-1个结点，因为根结点已经有了
        for(int i=n-1;i>0;i--)   
            {
                cin>>m;
                insert(BT,m);
            }
        cout<<"PreOrderVisit: ";
        PreOrderVisit(BT);  //前序遍历
        cout<<endl;
        cout<<"InOrderVisit: ";
        InOrderVisit(BT);   //中序遍历
        cout<<endl;
        cout<<"PostOrderVisit: ";
        PostOrderVisit(BT);   //后序遍历
        cout<<endl;
    return 0;   
}
struct node* newNode(int data)
{
    struct node* a = new node;
    a->data = data;
    a->left = NULL;
    a->right = NULL;
    return a;
}
struct node* insert(struct node* node,int data)
{
    if(node==NULL)
        return newNode(data);
    else
    {
        if(data<=node->data)
            node->left=insert(node->left,data);
        else
            node->right=insert(node->right,data);

        return node;
    }
}


void PreOrderVisit(struct node* node)
{
    if(node==NULL)
        return;
    else
        {
            cout<<node->data<<' ';      
            PreOrderVisit(node->left);
            PreOrderVisit(node->right);


        }   
}
void InOrderVisit(struct node* node)
{
    if(node==NULL)
        return;
    else
        {

            InOrderVisit(node->left);
            cout<<node->data<<' ';
            InOrderVisit(node->right);


        }   
}
void PostOrderVisit(struct node* node)
{
    if(node==NULL)
        return;
    else
        {

            PostOrderVisit(node->left);
            PostOrderVisit(node->right);
            cout<<node->data<<' ';  

        }   
}

例：假设有下面这样一个树：

这棵树有四个结点，分析可知，三种遍历的结果应该如下：

前序遍历：2 1 10 5
中序遍历：1 2 5 10
后序遍历：1 5 10 2

来看程序运行结果是否与分析的结果一致，运行程序，依次输入4 2 1 10 5得到如下结果：

可见，程序运行结果和分析得到的结果一致，证明程序算法是正确的。需要注意的是：

创建树的时候，输入元素顺序必须从上至下，从左至右，如下面这棵树输入顺序必须是：2 1 10 5，如果输入顺序不对，得到的将是另外一棵树，比如，输入2 10 1 5得到的是: