二叉树建立与遍历

网上很多算法通过直接将二叉树结点连接，从而构成二叉树，这里我构建了一个二叉树类，通过用户控制输入来建立二叉树。

有层序遍历，递归、非递归的前序遍历、中序遍历、后序遍历算法。

#include<iostream>
#include<queue>
#include<stack>
using namespace std;
class Binarytreenode
{
    public:
        int data;
        Binarytreenode *leftchild;
        Binarytreenode *rightchild;
        Binarytreenode(){};
        Binarytreenode(const int &a,Binarytreenode *l=NULL,Binarytreenode*r=NULL)
        {
            this->data=a;
            this->leftchild=l;
            this->rightchild=r;
        }
};

class BinaryTree
{
    private:
        
    public:
        Binarytreenode *root;
        BinaryTree(){root =new  Binarytreenode;};
        ~BinaryTree(){delete[]root;}
        void visit(Binarytreenode*t)
        {
            cout<<t->data<<" ";
        }
        Binarytreenode* creatTree(Binarytreenode* temp)
        {
            int n;
            cout<<"请输入2叉树结点的值,输入-1以表示停止创建某子树"<<endl;
            cin>>n;
            if(n==-1)
            {
                return NULL;
            }
            else{
                temp = new Binarytreenode;
                temp->data=n;
                temp->leftchild=creatTree(temp->leftchild);
                temp->rightchild=creatTree(temp->rightchild);
                }
            root=temp;
            return root;
        }
        void levelOrder()
        {
            queue <Binarytreenode *> nodeQueue;
            Binarytreenode *p=root;
            if (p)
                nodeQueue.push(p);
            while(!nodeQueue.empty())
            {
                p=nodeQueue.front();
                visit(p);
                nodeQueue.pop();
                if (p->leftchild)
                {
                    nodeQueue.push(p->leftchild);
                }
                if (p->rightchild)
                {
                    nodeQueue.push(p->rightchild);
                }
            }
            
        }
        void preOrder0(Binarytreenode *root)//先序递归
        {
            if (root!=NULL)
            {
                visit(root);
                preOrder0(root->leftchild);
                preOrder0(root->rightchild);
            }
        }
        void inOrder0(Binarytreenode *root)//中序递归
        {
            if (root!=NULL)
            {
                inOrder0(root->leftchild);
                visit(root);
                inOrder0(root->rightchild);
            }
        }
        void postOrder0(Binarytreenode *root)//后序递归
        {
            if (root!=NULL)
            {
                postOrder0(root->leftchild);
                postOrder0(root->rightchild);
                visit(root);
            }
        }
        void preOrder1(Binarytreenode *root)
        {
            stack<Binarytreenode *>nodeStack;
            Binarytreenode *p=root;
            while (!nodeStack.empty()||p)
            {
                
                if(p)
                {
                    visit(p);//先访问当前结点，也就是根
                    if (p->rightchild!=NULL)//若右子树不空，则先存到栈中
                    {
                        nodeStack.push(p->rightchild);
                    }
                    p=p->leftchild;//p指向左子树，开始访问。
                }else//左子树遍历完毕后，进行弹栈，继续遍历
                {
                    p=nodeStack.top();
                    nodeStack.pop();
                }   
            }   
        }
        void inOrder1(Binarytreenode *root)
        {
            stack<Binarytreenode *>nodeStack;
            Binarytreenode *p=root;
            while (!nodeStack.empty()||p)
            {
                
                if(p)
                {
                    nodeStack.push(p);//一路向左全压栈。
                    p=p->leftchild;
                }else
                {
                    p=nodeStack.top();
                    visit(p);
                    p=p->rightchild;
                    nodeStack.pop();
                }   
            }   
        }
        void postOrder1(Binarytreenode *root)
        {
            stack<Binarytreenode *>nodeStack;
            Binarytreenode *p=root;
            Binarytreenode *pre=root;
            while (p)
            {
                while(p->leftchild!=NULL)//向左搜索全压栈，直到没有左子树。
                {
                    nodeStack.push(p);
                    p=p->leftchild;
                }
                //读取栈顶，访问右子树
                while (p!=NULL&& (p->rightchild==NULL || p->rightchild==pre))
                {
                    visit(p);
                    pre=p;
                    if (nodeStack.empty())
                    {
                        return;
                    }
                    p=nodeStack.top();
                    nodeStack.pop();
                }
                nodeStack.push(p);
                p=p->rightchild;
                
            }
            

        }
};

int main()
{
    BinaryTree t1;
    t1.creatTree(t1.root);
    cout<<"层次遍历:"<<endl;
    t1.levelOrder();
    cout<<endl<<"前序遍历(递归):"<<endl;
    t1.preOrder0(t1.root);
    cout<<endl<<"前序遍历(非递归):"<<endl;
    t1.preOrder1(t1.root);
    cout<<endl<<"中序遍历(递归):"<<endl;
    t1.inOrder0(t1.root);
    cout<<endl<<"中序遍历(非递归):"<<endl;
    t1.inOrder0(t1.root);
    cout<<endl<<"后序遍历(递归):"<<endl;
    t1.postOrder0(t1.root);
    cout<<endl<<"后序遍历(非递归):"<<endl;
    t1.postOrder0(t1.root);
    cout<<endl;
    return 0;
}
//      1
//   2     3
// 4  5       7
//输入1 2 4 -1 -1 5 -1 -1 3 -1 7 -1 -1
//层序: 1 2 3 4 5 7
//前序: 1 2 4 5 3 7
//中序: 4 2 5 1 3 7
//后序: 4 5 2 7 3 1