二叉树的基本操作：创建，遍历，删除..........................

本程序实现的是：

0.先序遍历创建一棵二叉树

1.递归先序遍历

2.递归中序遍历

3.递归后序遍历

4.非递归的先序遍历(3)

5.非递归的中序遍历(2)

6.非递归的后序遍历(2)

7.非递归的层序遍历(2)

8.二叉树的深度(3)

9.二叉树的节点数

10.判断是否为完全二叉树

11.删除节点为x的根节点

12.将二叉树节点存储在一维数组

代码如下：

#include<iostream>
#include<cstdlib>
#include<stack>
#include<queue>
using namespace std;
char a[100];
typedef struct BitNode *Next;
typedef Next BinTree;
struct BitNode
{
    char data;          //数据域
    BinTree lchild;     //左孩子
    BinTree rchild;     //右孩子
};


//先序遍历创建二叉树
BinTree CreateTree(BinTree &bt)
{
    char ch;
    cin>>ch;
    if(ch == '#')
        bt = NULL;
    else
    {
        bt = new BitNode;
        bt->data = ch;
        cout<<"请输入"<<ch<<"的左孩子:";
        CreateTree(bt->lchild);
        cout<<"请输入"<<ch<<"的右孩子:";
        CreateTree(bt->rchild);
    }
    return bt;
}


//前序遍历的递归
void Preorder(BinTree &bt)
{
    if(bt == NULL)
        return ;
    cout<<bt->data;         //输出数据
    Preorder(bt->lchild);   //左子树递归
    Preorder(bt->rchild);   //右子树递归
}


//中序遍历的递归
void Inorder(BinTree &bt)
{
    if(bt == NULL)
        return ;
    Inorder(bt->lchild);
    cout<<bt->data;
    Inorder(bt->rchild);
}


//后序遍历的递归
void Postorder(BinTree &bt)
{
    if(bt == NULL)
        return ;
    Postorder(bt->lchild);
    Postorder(bt->rchild);
    cout<<bt->data;
}
/*
二叉树的非递归前序遍历，前序遍历思想：先让根进栈，只要栈不为空，就可以做弹出操作，
每次弹出一个结点，记得把它的左右结点都进栈，记得右子树先进栈，这样可以保证右子树在栈中总处于左子树的下面。
*/
//先序非递归算法1
void Preorder_Traverse_1(BinTree &bt)
{
    if(!bt)
        return ;
    stack<BinTree> s;
    while(bt)                   //当树存在
    {
        s.push(bt);             //根节点入栈
        cout<<bt->data<<" ";    //输出数据
        bt = bt->lchild;        //指向左子树
    }


    while(!s.empty())           //当栈不为空
    {
        BinTree cur = s.top()->rchild;  //指向右子树
        s.pop();                    //出栈
        while(cur)                  //当树存在
        {
            cout<<cur->data<<" ";   //输出数据
            s.push(cur);            //cur入栈
            cur = cur->lchild;      //指向左子树
        }
    }
}


//先序非递归算法2
void Preorder_Traverse_2(BinTree &bt)
{
    if(!bt)
        return ;
    stack<BinTree> s;
    BinTree cur = bt;
    while(cur != NULL || !s.empty())    //
    {
        while(cur != NULL)              //
        {
            cout<<cur->data<<" ";       //
            s.push(cur);                //
            cur = cur->lchild;          //
        }
        if(!s.empty())                  //
        {
            cur = s.top();              //
            s.pop();                    //
            cur = cur->rchild;          //
        }
    }
}


//先序非递归算法3
void Preorder_Traverse_3(BinTree &bt)
{
    if(!bt)
        return ;
    stack<BinTree> s;
    while(bt)
    {
        s.push(bt);
        cout<<bt->data<<" ";
        bt = bt->lchild;
    }
    while(!s.empty())
    {
        BinTree cur = s.top()->rchild;
        s.pop();
        while(cur)
        {
            cout<<cur->data<<" ";
            s.push(cur);
            cur = cur->lchild;
        }
    }
}


//
void Inorder_Traverse_1(BinTree &bt)
{
    if(!bt)
        return ;
    BinTree cur = bt;
    stack<BinTree> s;
    while(cur != NULL || !s.empty())
    {
        while(cur != NULL)
        {
            s.push(cur);
            cur = cur->lchild;
        }
        if(!s.empty())
        {
            cur = s.top();
            s.pop();
            cout<<cur->data<<" ";
            cur = cur->rchild;
        }
    }
}


//
void Inorder_Traverse_2(BinTree &bt)
{
    if(!bt)
        return ;
    stack<BinTree> s;
    BinTree cur = bt->lchild;
    s.push(bt);
    while(cur != NULL || !s.empty())
    {
        while(cur != NULL)
        {
            s.push(cur);
            cur = cur->lchild;
        }
        cur = s.top();
        s.pop();
        cout<<cur->data<<" ";
        cur = cur->rchild;
    }
}


//
void Postorder_Traverse_1(BinTree &bt)
{
    stack<BinTree> s;
    BinTree cur = bt;
    BinTree previsited = NULL;
    while(cur != NULL || !s.empty())
    {
        while(cur != NULL)
        {
            s.push(cur);
            cur = cur->lchild;
        }
        cur = s.top();
        if(cur ->rchild == NULL || cur->rchild == previsited)
        {
            cout<<cur->data<<" ";
            previsited = cur;
            s.pop();
            cur = NULL;
        }
        else
        {
            cur = cur->rchild;
        }
    }
}


//
void Postorder_Traverse_2(BinTree &bt)
{
    stack<BinTree> s1,s2;
    BinTree cur;
    s1.push(bt);
    while(!s1.empty())
    {
        cur = s1.top();
        s1.pop();
        s2.push(cur);
        if(cur->lchild)
            s1.push(cur->lchild);
        if(cur->rchild)
            s1.push(cur->rchild);
    }
    while(!s2.empty())
    {
        cout<<s2.top()->data;
        s2.pop();
    }
}


//
void Lever_Traverse_1(BinTree &bt)
{
    if (bt == NULL)
        return;
    BinTree binTree[100];   //数组迭代存储层序遍历的节点
    int head = 0, last = 0; //
    binTree[last++] = bt;
    while (head < last)     //通过迭代存储和遍历节点
    {
        BinTree temp = binTree[head++];
        cout<<temp->data<<" ";
        if (temp->lchild)     //左子树存在
            binTree[last++] = temp->lchild;
        if (temp->rchild)    //右子树存在
            binTree[last++] = temp->rchild;
    }
}


//
int visit(BinTree &bt)
{
    if(bt)
    {
        cout<<bt->data;
        return 1;
    }
    else
        return 0;
}
void Lever_Traverse_2(BinTree &bt)
{
    queue<BinTree> q;
    BinTree p;
    p = bt;
    if(visit(p) == 1)
        q.push(p);
    while(!q.empty())
    {
        p = q.front();
        q.pop();
        if(visit(p->lchild) == 1)
            q.push(p->lchild);
        if(visit(p->rchild) == 1)
            q.push(p->rchild);
    }
}


//
int depth_1(BinTree &bt)
{
    if(bt == NULL)//树为空，深度为0
        return 0;


    if(bt-> lchild == NULL && bt->rchild == NULL)//根节点下的左右节点均为空，度为1
        return 1;


    if(bt-> lchild == NULL)//左树为空，递归右树
        return 1 + depth_1(bt-> rchild);


    if(bt-> rchild == NULL)//右树为空，递归左树
        return 1 + depth_1(bt-> lchild);
    return depth_1(bt-> lchild)> depth_1(bt-> rchild)?1 + depth_1(bt-> lchild):1 + depth_1(bt-> rchild); //通过递归，返回树的深度
}


//
int depth_2(BinTree &bt)
{
    if(!bt)
        return 0;
    int d1,d2;
    d1 = depth_2(bt->lchild);
    d2 = depth_2(bt->rchild);
    return (d1>d2?d1:d2)+1;
}


//
bool DeleteNode(BinTree &bt,char x,bool flag)
{
    if(bt == NULL)
        return false;
    else
    {
        if(bt->data == x)
        {
            flag = true;
        }


        bool lef_ret = DeleteNode(bt->lchild,x,flag);
        bool rig_ret = DeleteNode(bt->rchild,x,flag);


        if(flag)
        {
            if(bt->data == x)
                return true;
            delete bt;
        }
        else
        {
            if(lef_ret)
                bt->lchild = NULL;
            if(rig_ret)
                bt->rchild = NULL;
        }
    }
    return false;
}


//
bool IsCompleteTree(BinTree &bt)
{
    if (bt == NULL)
    {
        return false;
    }
    queue<BinTree> q;
    q.push(bt);
    bool flag = false;//用来标志是否为满结点，也就是完全二叉树
    while (!q.empty())//当队列不为空的时候
    {
        BinTree cur = q.front();
        q.pop();
        if (flag)//flag==true，即已经出现过满结点的时候
        {
            //cur结点的左子树或者右子树不为空，一定不是完全二叉树
            if (cur->lchild != NULL || cur->rchild != NULL)
            {
                return false;
            }
        }
        //没有出现过满结点
        else
        {
            if (cur->lchild != NULL&&cur->rchild != NULL)
            {
                q.push(cur->lchild);
                q.push(cur->rchild);
            }
            //左子树为空，右子树不为空。一定不是完全二叉树
            else if (cur->lchild == NULL&&cur->rchild != NULL)
            {
                return false;
            }
            //左子树不为空，右子树为空
            else if (cur->lchild != NULL&&cur->rchild == NULL)
            {
                q.push(cur->lchild);
                flag = true;
            }
            //左子树和右子树都为空，则为完全二叉树
            else
            {
                flag = true;
            }
        }
    }
    return true;
}


//
void Tree_to_arr(BinTree &bt)
{
    int i = 0;
    BinTree p = bt;
    queue<BinTree> Q;
    Q.push(p);
    while(!Q.empty())
    {
        p = Q.front();
        Q.pop();
        a[++i] = p->data;
        if(p->lchild != NULL)
            Q.push(p->lchild);
        if(p->rchild != NULL)
            Q.push(p->rchild);
    }
    for(int j = 1; j <= i; j++)
        cout<<a[i]<<" ";
}


//
int CountNode(BinTree &bt)
{
    if(bt == NULL)
        return 0;
    return 1+CountNode(bt->lchild)+CountNode(bt->rchild);
}




int main()
{
    BinTree bt = NULL;
    int in = 1,k;
    bool flag;
    cout<<"                            本程序实现二叉树的基本操作                      "<<endl;
    cout<<"三种遍历的递归和非递归操作及其他操作"<<endl;;
    while(in)
    {
        cout<<endl;
        cout<<"|-------------------------------------------------------------------|"<<endl;
        cout<<"|---------------------------二叉树的基本操作------------------------|"<<endl;
        cout<<"|---------------------------0.先序遍历创建一棵二叉树----------------|"<<endl;
        cout<<"|---------------------------1.递归先序遍历--------------------------|"<<endl;
        cout<<"|---------------------------2.递归中序遍历--------------------------|"<<endl;
        cout<<"|---------------------------3.递归后序遍历--------------------------|"<<endl;
        cout<<"|---------------------------4.非递归的先序遍历----------------------|"<<endl;
        cout<<"|---------------------------5.非递归的中序遍历----------------------|"<<endl;
        cout<<"|---------------------------6.非递归的后序遍历----------------------|"<<endl;
        cout<<"|---------------------------7.非递归的层序遍历----------------------|"<<endl;
        cout<<"|---------------------------8.二叉树的深度--------------------------|"<<endl;
        cout<<"|---------------------------9.二叉树的节点数------------------------|"<<endl;
        cout<<"|---------------------------10.判断是否为完全二叉树-----------------|"<<endl;
        cout<<"|---------------------------11.删除节点为x的根节点------------------|"<<endl;
        cout<<"|---------------------------12.将二叉树节点存储在一维数组-----------|"<<endl;
        cout<<"|---------------------------13.退出程序-----------------------------|"<<endl;
        cout<<"|-------------------------------------------------------------------|"<<endl;
        cout<<"|-------------------------------------------------------------------|"<<endl;
        cout<<"                            请选择功能：                             "<<endl;
        cin>>k;
        switch(k)
        {
        case 0:
            cout<<" 建立一棵二叉树，输入二叉树的根节点:";
            CreateTree(bt);
            break;
        case 1:
            if(bt)
            {
                cout<<"递归先序遍历二叉树的结果为:";
                Preorder(bt);
                cout<<endl;
            }
            else
                cout<<"二叉树为空！"<<endl;
            break;
        case 2:
            if(bt)
            {
                cout<<"递归中序遍历二叉树的结果为:";
                Inorder(bt);
                cout<<endl;
            }
            else
                cout<<"二叉树为空！"<<endl;
            break;
        case 3:
            if(bt)
            {
                cout<<"递归后序遍历二叉树的结果为:";
                Postorder(bt);
                cout<<endl;
            }
            else
                cout<<"二叉树为空！"<<endl;
            break;
        case 4:
            if(bt)
            {
                cout<<"非递归先序遍历二叉树的结果为:";
                Preorder_Traverse_1(bt);
                cout<<endl;
            }
            else
                cout<<"二叉树为空！"<<endl;
            break;
        case 5:
            if(bt)
            {
                cout<<"非递归中序遍历二叉树的结果为:";
                Inorder_Traverse_1(bt);
                cout<<endl;
            }
            else
                cout<<"二叉树为空！"<<endl;
            break;
        case 6:
            if(bt)
            {
                cout<<"非递归后序遍历二叉树的结果为:";
                Postorder_Traverse_1(bt);
                cout<<endl;
            }
            else
                cout<<"二叉树为空！"<<endl;
            break;
        case 7:
            if(bt)
            {
                cout<<"非递归层序遍历二叉树的结果为:";
                Lever_Traverse_1(bt);
                cout<<endl;
            }
            else
                cout<<"二叉树为空！"<<endl;
            break;
        case 8:
            if(bt)
                cout<<"二叉树的深度为:"<<depth_1(bt)<<endl;
            else
                cout<<"二叉树为空！"<<endl;
            break;
        case 9:
            if(bt)
                cout<<"二叉树的节点个数为:"<<CountNode(bt)<<endl;
            else
                cout<<"二叉树为空！"<<endl;
            break;
        case 10:
            if(IsCompleteTree(bt))
                cout<<"该树是完全二叉树！"<<endl;
            else
                cout<<"该树不是完全二叉树！"<<endl;
            break;
        case 11:
            char x;
            cout<<"Please input x:";
            cin>>x;
            if(DeleteNode(bt,x,flag))
            {
                cout<<"删除节点x成功，删除后的二叉树为:";
                Preorder(bt);
                cout<<endl;
            }
            else
                cout<<"查找不到节点x,删除失败！"<<endl;
            break;
        case 12:
            if(bt)
            {
                cout<<"顺序存储的结果为：";
                Tree_to_arr(bt);
                cout<<endl;
            }
            else
                cout<<"二叉树为空！"<<endl;
            break;
        default:
            flag = 0;
            cout<<"程序运行结束，按任意键退出！"<<endl;
        }
    }
    return 0;
}