二叉树的储存与遍历

二叉树的两种储存：顺序储存 链式储存

四种遍历：层次遍历 前序遍历 中序遍历 后序遍历

1.储存

- 顺序储存：
首先用零元素将二叉树填充为完全二叉树，再将填充后的二叉树节点按层次顺序的次序储存到数组中


存储后即为：

由于顺序储存效率低，所以一般不这样进行二叉树的储存。

- 链式储存：

二叉链表的结点结构为

template<class T>
struct BTNode
{
    T data;
    BTNode *left *right ;//指向左右孩子的指针
    BTNode(const T& item=T(),lptr=NULL,BTNode* rptr=NULL)：
            data(item),left(lptr),right(rplt){}
};

建立二叉链表结点的函数

template<class T>
BTNode <T> * GetBTNode(const T& item,BTNode<T> *lp=NULL,BTNode<T> *rp=NULL)
{
    BTNode <T> *p;
    p=new BTNode<T> (item,lp,rp);
    if(p==NULL)
    {
        cout<<"Memory allocation failure!"<<endl;
        exit(1);
    }
    return (p);
}

图一应用举例：

BTNode<char> *nullp = NULL;
BTNode<char> *fp = GetBTNode('F');
BTNode<char> *dp = GetBTNode('D', fp);
BTNode<char> *bp = GetBTNode('B', nullp, dp);//若直接用NULL，非法，由于无法确定NULL类型
BTNode<char> *ep = GetBTNode('E');//合法，左右孩子取，默认值
BTNode<char> *cp = GetBTNode('C', nullp, ep);
BTNode<char> *ap = GetBTNode('A', bp, cp);

2.遍历

- 层次遍历：
层次遍历顾名思义就是将结点一层一层的进行遍历，如例图中就为ABCDE

非递归层次遍历运用了队列，简单讲一下队列有着先进先出的原则，层次遍历可以出队之后访问，入队之前访问

出队之后访问：

template<class T>
void Level(const BTNode<T>* t)
{
    if(t==NUll)
    return ;
    queue<const BTNode<T>*> Q;
    Q.Push(t)//入栈函数,在queue.h内
    while(!Q.Empty())
    {
        t=Q.Pop();//出栈函数，移除第一个数据并赋给t指针
        cout<<t->data;
        if(t->left)
            Q.Push(t->left);
        if(t->right)
            Q.Push(t->right)
    }
}

出队之前访问

template<class T>
void Level(const BTNode<T>* t)
{
    if(t==NUll)
    return ;
    queue<const BTNode<T>*> Q;
    cout<<t->data;
    Q.Push(t)
    while(!Q.Empty())
    {
        t=Q.Pop();
        if(t->left)
        {
            cout<<t->left->data;
            Q.Push(t->left);
        }   
        if(t->right)
        {
            cout<<t->right->data;
            Q.Push(t->right);   
        }       
    }
}

- 前序遍历
前序遍历也称之为深度优先遍历，算法的递归描述为
1.访问根节点
2.前序遍历左子树
3.前序遍历右子树

例图中前序遍历即为ABDFCE，运用了用户栈，用户栈有着先进后出的原则，在前序遍历中栈实质是为了寄存右子树的根指针，将左指针所指的左子树遍历后，再遍历右子树。
代码如下：

template <class T>
void SimPreorder(const BTNode <T>* t)
{
    if(!t)
        return ;
    stack<const BTNode<T>*> S;//用户栈
    while(t||!S.Empty())
        if(t)
        {
            cout<<t->data;
            if(t->right)
                S.push(t->right);//入栈
            t=t->left;
        }
        else
                t=S.Pop();//清除栈的最后进入的一位
}

关于前序遍历，有些算法和它还是很相近的，比如二分快速排序，集合幂集求解。后期会补上相关博客

- 中序遍历
中序遍历中，也用到栈，其意义是寄存根节点，以便于左子树遍历完成后取出根指针，访问根指针并取出右子树进行遍历，算法的递归描述：
1.中序遍历左子树
2.访问根节点
3.中序遍历右子树
代码如下：

template<class T>
void Siminorder(const BTNode<T>* t)
{
    if(!t)
        return ;
    stack<const BTNode<T>*> S;
    while (t||!S.Empty())
    {
        if(t)
        {
            S.Push(t);
            t=t->left'
        }
        else
        {
            t=S.Pop();
            cout<<t->data;
            t-t->right;
        }
    }
}

- 后序遍历
后序遍历非递归算法任然是栈来实现，但是不同的是后序遍历用了两个栈，一个栈是为了寄存根节点，一个栈是为了记录相应的结点指针入栈的次数，后序遍历结点会进栈两次，第一次遍历左子树，第二次为了遍历右子树

递归算法描述：
1.后序遍历左子树
2.后序遍历右子树
3.访问根节点

代码实现：

template<class T>
void SimPostorder(const BTNode<T>* t)
{
    if (!t)
        return ;
    int tag;
    Stack<const BTNode<T>*> S;
    Stack<int> tagS;
    const BTNode <T>*temp;
    while (t || !S.Empty())
    {
        if (t)
        {
            S.Push(t);
            tagS.Push(1);
            t = t->left;
        }
        else
        {
            temp = S.Pop();
            tag = tagS.Pop();
            if (tag == 1)
            {
                S.Push(temp);
                tagS.Push(2);
                t = temp->right;
            }
            else
                cout << temp->data;
        }
    }
}

记录的还是有些粗略，后期会再进行详解

注： 片段代码或者语言如有错误望谅解并请指出。