c++二叉树实现

#include<iostream>
using namespace std;
#include<stack>
#include<malloc.h>
#include<vector>
typedef  int ElemType;
#define MaxSize 100
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//创建节点
BiTree createNode(int value)
{
    BiTree pnode = (BiTree )malloc(sizeof(BiTNode));
    pnode->data = value;
    pnode->rchild = pnode->lchild = nullptr;
    return pnode;
}

//增加结点
BiTree addNode(int value,BiTree pnode)
{
    if(pnode == nullptr)
        return createNode(value);

    if (value == pnode->data)
        return pnode;

    if(value<pnode->data)
    {
        if(pnode->lchild == nullptr)
        {
            pnode->lchild = createNode(value);
            return pnode->lchild;
        }
        else
        {
            return addNode(value,pnode->lchild);
        }
    }else
    {
        if(pnode->rchild == nullptr)
        {
            pnode->rchild = createNode(value);
            return pnode->rchild;
        }
        else{
            return addNode(value,pnode->rchild);
        }
    }
}


//三种遍历方式 时间复杂度为O(n) 空间复杂度为O(n)
//先序遍历 根左右
void PreOrder(BiTree T)
{
    if(T!=nullptr)
    {
        cout<<T->data<<" ";  //王道的visit函数就是这个意思
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }

}

//中序遍历 左根右
void InOrder(BiTree T)
{
    if(T)
    {
        InOrder(T->lchild);
        cout<<T->data<<" ";
        InOrder(T->rchild);
    }
}

//后序遍历 左右根
void PostOrder(BiTree T)
{
    if(T)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout<<T->data<<" ";
    }
}




//二叉树的深度
int Treeheight(BiTree pnode)
{
    int ld,rd;
    if(pnode == nullptr)
        return 0;
    else
    {
        ld = Treeheight(pnode->lchild);
        rd = Treeheight(pnode->rchild);
        return (ld >= rd ? ld : rd)+1;
    }
}

//三种遍历方式的非递归实现
void PreOrder_nonrecursion(BiTree T)
{
    stack<BiTree> s;
    int top = -1;
    BiTree p = T;
    cout<<"前序遍历非递归序列为:";
    while(p!=nullptr || top!=-1)
    {
        if(p!=nullptr)
        {
            ++top;
            s.push(p);
            cout<<p->data<<" ";
            p = p->lchild;
        }
        else
        {
            p = s.top();
            top--;
            s.pop();
            p = p->rchild;
        }
    }
    cout<<endl;
}


void InOrder_nonrecursion(BiTree T)
{
    stack<BiTree> s;
    int top = -1;
    BiTree p = T;
    cout<<"中序遍历非递归序列为:";
    while(p!=nullptr || top!= -1)
    {
        if(p!=nullptr)
        {
            ++top;
            s.push(p);
            p = p->lchild;
        }
        else
        {
            p = s.top();
            top--;
            s.pop();
            cout<<p->data<<" ";
            p = p->rchild;
        }
    }
    cout<<endl;
}


void PostOrder_nonrecursion(BiTree T)
{
    stack<BiTree> s;
    int top = -1;
    BiTree p = T;
    vector<ElemType> flag(MaxSize,0);
    cout<<"后序遍历非递归序列为:";
    while(p!=nullptr || top !=-1)
    {
        if(p!=nullptr)
        {
            ++top;
            s.push(p);
            flag[top] = 1;
            p = p->lchild;
        }
        else
        {
            if(flag[top] == 1)
            {
                p = s.top();
                flag[top] = 2;
                p = p->rchild;
            }
            else
            {
                p = s.top();
                top--;
                s.pop();
                cout<<p->data<<" ";
                p = nullptr;
            }
        }
    }
    cout<<endl;
}


int main()
{
    int newvalue = 0;
    BiTree root = NULL;
    char answer = 'n';
    do
    {
        printf("Enter the node value:");
        scanf("%d", &newvalue);
        if(root == NULL)
        {
            root = createNode(newvalue);
        }
        else
        {
            addNode(newvalue, root);
        }
        printf("Do you want to enter another (y or n)? ");
        scanf(" %c", &answer);
    } while(tolower(answer) == 'y');

        PreOrder_nonrecursion(root);
    InOrder_nonrecursion(root);
    PostOrder_nonrecursion(root);

    printf("The height of tree is %d!", Treeheight(root));

    return 0;
}

结果图：