二叉树的基本操作 C++代码实现

首先定义节点

typedef struct BTree
{
    int    value;
    struct BTree *lchild;
    struct BTree *rchild;
}BTree;

前序递归建立二叉树

/*
**num 前序序列
**index 下标
*/
BTree *CreateBTree(BTree *node,int *num,int& index)
{
    if(num[index] == 0)
        return NULL;
    else
    {
        node = new BTree;
        node -> value = num[index];
        node -> lchild = CreateBTree(node->lchild,num,++index);
        node -> rchild = CreateBTree(node->rchild,num,++index);
    }
    return node;
}

几种遍历

递归－－前序遍历

void preOrder(BTree * root)
{
    if(root == NULL)
        return;
    cout << root -> value << " ";　　//先输出树的根节点的值
    preOrder(root -> lchild);       //递归　左子树
    preOrder(root -> rchild);       //递归　右子树   
}

非递归－－前序遍历

void preOrder_dxm(BTree * root)
{
    stack<BTree*> S;
    BTree *p = root;
    while(p != NULL || !S.empty())
    {
        while(p != NULL)
        {
            cout << p -> value << " ";
            S.push(p);
            p = p -> lchild;
        }
        if(!S.empty())
        {
            S.pop();
            if(S.empty())
                return ;
            p = S.top();
            S.pop();
            p = p -> rchild;
        }
    }
}

递归－－中序遍历

void inOrder(BTree * root)
{
    if(root == NULL)
        return;
    inOrder(root -> lchild);
    cout << root -> value << " ";
    inOrder(root -> rchild);
}

非递归－－中序遍历

void inOrder_dxm(BTree * root)
{
    stack<BTree*> S;
    BTree *p = root;
    while(p != NULL || !S.empty())
    {
        while(p != NULL)
        {
            //cout << p -> value << " ";
            S.push(p);
            p = p -> lchild;
        }
        if(!S.empty())
        {
            p = S.top();
            cout << p -> value << " ";
            S.pop();
            if(S.empty())
                return ;
            //S.pop();
            p = S.top();
            cout << p -> value << " ";
            S.pop();
            p = p -> rchild;
        }
    }
}

递归－－后序遍历

void postOrder(BTree * root)
{
    if(root == NULL)
        return;
    postOrder(root -> lchild);
    postOrder(root -> rchild);
    cout << root -> value << " ";
}

非递归－－后序遍历

void postOrder_dxm(BTree * root)
{
    stack<BTree*> S;
    BTree *cur;
    BTree *pre = NULL;
    S.push(root);
    while(!S.empty())
    {
        cur = S.top();
        if((cur -> lchild == NULL && cur -> rchild == NULL) || 
           (pre != NULL && (pre == cur -> lchild || pre == cur ->rchild)))
        {
            cout << cur -> value << " ";
            S.pop();
            pre = cur;
        }
        else
        {
            if(cur -> rchild != NULL)
                S.push(cur -> rchild);
            if(cur -> lchild != NULL)
                S.push(cur -> lchild);
        }
    }
}

求二叉树的深度

int getdepth(BTree *root)
{
    if(root == NULL)
        return 0;
    int lchild_depth = getdepth(root -> lchild);
    int rchild_depth = getdepth(root -> rchild);
    return max(lchild_depth,rchild_depth) + 1;
}

求二叉树叶子节点的个数

int getleaves(BTree *root)
{
    if(root == NULL)
        return 0;
    if(root -> lchild == NULL && root -> rchild == NULL)
        return 1;    
    return 1 + getleaves(root -> lchild) + getleaves(root -> rchild);
}

树状打印二叉树

void print(BTree *root,int h)
{
    if(root != NULL)
    {
        print(root -> rchild,h+1);
        for(int i=0; i<h; i++)
            cout << "   ";
        cout << root -> value;
        print(root -> lchild,h+1);
    }
    cout << endl;
}

主函数

int main()
{
    int num[] = {1,2,4,8,0,0,9,0,0,5,10,0,0,11,0,0,3,6,12,0,0,13,0,0,7,14,0,0,15,0,0};
    BTree *root = NULL;
    int index = 0;
    root = CreateBTree(root,num,index);

    cout << "前序非递归遍历: " << endl;
    preOrder_dxm(root);
    cout << endl;

    cout << "中序递归遍历: " << endl;
    inOrder_dxm(root);
    cout << endl;

    cout << "后续非递归遍历: " << endl;
    postOrder_dxm(root);
    cout << endl << endl;;

    cout << "此二叉树的形状为: " << endl;
    print(root,1);

    return 0;
}

输出结果

---

由给定二叉树的两种序列创建二叉树

前序序列：根在前，且左孩子在右孩子前
中序序列：根在中间，左边为左孩子，右边为右孩子
后序序列：根在最后，且左孩子在右孩子前

根据二叉树前序序列和中序序列创建二叉树：

1. 前序序列的第一个元素就是二叉树的根节点
2. 在中序序列中找到根节点，根据根节点将中序序列分为两部分：此节点左边的是左子树的中序序列，右边是右子树的中序序列；
3. 将除去根节点的前序序列分为两部分：左子树在前，剩下为右子树
4. 递归创建左右子树

/*************************************************************************
    > File Name: 中序＆先序建立二叉树.cpp
    > Author: Tanswer
    > Mail: 98duxm@gmail.com
    > Created Time: 2016年10月24日 星期一 17时33分24秒
 ************************************************************************/

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
typedef struct BTree
{
    char value;
    struct BTree *lchild;
    struct BTree *rchild;
}BTree;


BTree *Created(BTree *root,string pre,string in)
{

    if(pre.length() == 0)
    {
        root = NULL;
        return NULL;
    }
    //前序的第一个值　为　根
    int root_value = pre[0];
    //找到根在中序中的位置 :下标
    int index = in.find(root_value);
    //左孩子的中序序列
    string lchild_in = in.substr(0,index);
    //右孩子的中序序列
    string rchild_in = in.substr(index+1);
    //左孩子结点个数
    int lchild_length = lchild_in.length();
    //右孩子结点个数
    int rchild_length = rchild_in.length();
    //左孩子的前序序列
    string lchild_pre = pre.substr(1,lchild_length);
    //右孩子的前序序列
    string rchild_pre = pre.substr(1+lchild_length);

    root = new BTree;
    if(root != NULL)
    {
        root -> value = root_value;
        //root -> lchild = new BTree;
        root -> lchild = Created(root -> lchild,lchild_pre,lchild_in);
        //root -> rchild = new BTree;
        root -> rchild = Created(root -> rchild,rchild_pre,rchild_in);
    }
    return root;
}

/*树状打印二叉树*/
void print(BTree *root,int h)
{
    if(root != NULL)
    {
        print(root -> rchild,h+1);
        for(int i=0; i<h; i++)
            cout << "   ";
        cout << root -> value;
        print(root -> lchild,h+1);
    }
    cout << endl;
}

int main()
{
    cout << "先序序列为:  ABDECFG" << endl;
    cout << "中序序列为:  DBEAFCG" << endl;
    cout << "二叉树为: " << endl;;
    string pre = "ABDECFG";
    string in = "DBEAFCG";
    BTree *root = NULL;
    root = Created(root,pre,in);
    print(root,1);

    return 0;
}

输出结果：
　　　

根据二叉树后序序列和中序序列创建二叉树：

过程和上面的类似，就不再写了，直接上代码

BTree *Created(BTree *root,string post,string in)
{

    if(post.length() == 0)
    {
       root = NULL;
        return NULL;
    }

    /*后序序列的结点个数*/
    int size = post.size();

    //后序的最后一个值　为　根
    int root_value = post[size - 1];
    //找到根在中序中的位置 :下标
    int index = in.find(root_value);
    //左孩子的中序序列
    string lchild_in = in.substr(0,index);
    //右孩子的中序序列
    string rchild_in = in.substr(index+1);
    //左孩子结点个数
    int lchild_length = lchild_in.length();
    //右孩子结点个数
    int rchild_length = rchild_in.length();
    //左孩子的后序序列
    string lchild_post = post.substr(0,lchild_length);
    //右孩子的后序序列
    string rchild_post = post.substr(lchild_length,rchild_length);

    root = new BTree;
    if(root != NULL)
    {
        root -> value = root_value;

        root -> lchild = Created(root -> lchild,lchild_post,lchild_in);

        root -> rchild = Created(root -> rchild,rchild_post,rchild_in);
    }
    return root;
}