树的相关基础算法

树的相关基础算法，先序、中序、后序递归与非递归，层次遍历，建立二叉搜索树。

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

typedef struct Tree {
    int val;
    struct Tree *lchild, *rchild;
    int flag;
}BSTree;

BSTree* newBSTree(int n)
{
    BSTree *tree = new BSTree;
    tree->val = n;
    tree->lchild = NULL;
    tree->rchild = NULL;
    tree->flag = 0;
    return tree;
}

void createTree(BSTree *&root, int val)
{
    if(NULL == root)
        root = newBSTree(val);
    else
    {
        BSTree* p = root;
        while(p)
        {
            if(val < p->val)
            {
                if(p->lchild)
                    p = p->lchild;
                else
                {
                    p->lchild = newBSTree(val);
                    return;
                }
            }
            else if(val > p->val)
            {
                if(p->rchild)
                    p = p->rchild;
                else
                {
                    p->rchild = newBSTree(val);
                    return;
                }
            }
        }

    }
}

/***************************************************************************/
/*递归遍历系列*/
void PreOrderRecursion(BSTree* root)        //先序遍历：根——左——右
{
    if(root == NULL)
        return;
    cout << root->val << endl;
    if(root->lchild)
        PreOrderRecursion(root->lchild);
    if(root->rchild)
        PreOrderRecursion(root->rchild);
}

void InOrderRecursion(BSTree* root)            //中序遍历：左——根——右
{
    if(root == NULL)
        return;
    if(root->lchild)
        InOrderRecursion(root->lchild);
    cout << root->val << ' ';
    if(root->rchild)
        InOrderRecursion(root->rchild);
}

void PostOrderRecursion(BSTree* root)        //后序遍历：左——右——根
{
    if(root == NULL)
        return;
    if(root->lchild)
        PostOrderRecursion(root->lchild);
    if(root->rchild)
        PostOrderRecursion(root->rchild);
    cout << root->val << ' ';
}

/***************************************************************************/
/*非递归遍历系列*/
void PreOrderNonRecursion(BSTree* root)            //先序非递归
{
    if(!root)
        return;

    BSTree* pRoot = root;
    stack<BSTree*> st;

    while(pRoot || !st.empty())
    {
        while(pRoot)
        {
            cout << pRoot->val << ' ';
            st.push(pRoot);
            pRoot = pRoot->lchild;
        }

        if(!st.empty())
        {
            pRoot = st.top();
            st.pop();
            pRoot = pRoot->rchild;
        }
    }
}

void InOrderNonRecursion(BSTree* root)        //中序非递归
{
    if(!root)
        return;

    BSTree* pRoot = root;
    stack<BSTree*> st;

    while(pRoot || !st.empty())
    {
        while(pRoot)
        {
            st.push(pRoot);
            pRoot = pRoot->lchild;
        }

        if(!st.empty())
        {
            pRoot = st.top();
            st.pop();
            cout << pRoot->val << ' ';
            pRoot = pRoot->rchild;
        }
    }
}

void PostOrderNonRecursion(BSTree* root)        //后序非递归
{
    if(!root)
        return;

    BSTree* pRoot = root, *q = NULL;
    stack<BSTree*> st;

    while(pRoot || !st.empty())
    {
        while(pRoot)
        {
            st.push(pRoot);
            pRoot = pRoot->lchild;
        }
        pRoot = st.top();
        if(pRoot->rchild == NULL || pRoot->rchild == q)
        {
            cout << pRoot->val << ' ';
            q = st.top();
            st.pop();
            pRoot = NULL;
        }
        else
            pRoot = pRoot->rchild;
    }
}

void LevelReverse(BSTree* root)        //层次递归
{
    if(!root)
        return;

    queue<BSTree*> qu;
    qu.push(root);

    while(!qu.empty())
    {
        BSTree* pRoot = qu.front();
        cout << pRoot->val << ' ';
        qu.pop();

        if(pRoot->lchild)
            qu.push(pRoot->lchild);
        if(pRoot->rchild)
            qu.push(pRoot->rchild);
    }
}

/***************************************************************************/
int main()
{
    int array[] = {10, 8, 12, 6, 9, 11, 13};
    BSTree *root = NULL;
    int i, length = sizeof array / sizeof array[0];

    for(i = 0; i < length; i++)
        createTree(root, array[i]);

    LevelReverse(root);
    cout << endl;
}