数据结构-二叉树[非递归遍历]

1.二叉树概念

2.二叉树的构造及删除

不得不说下二叉树的构造，本来我是想找非递归实现的，结果只看到了完全二叉树和满二叉树（下文有）的构造方法，所以这一部分我暂时函数用前序的方法构造和删除，然后二叉树的概念在上篇文：二叉树的递归实现有介绍所以放个传送门大家自己去看看。

传送门: 点击打开链接

3.完全二叉树和满二叉树的非递归构造

(1)思路：利用完全和满二叉树双亲节点与左右孩子节点编号的关系

①双亲节点编号=左孩子或右孩子节点编号/2

②孩子节点编号%2=1，该孩子节点是右孩子节点

③孩子节点编号%2=0，该孩子节点是左孩子节点

利用节点地址数组储存节点，并按照上述关系建立节点联系

（2）实现代码

template<class T>
int Binary_tree<T>::Create_BTree(Bt_Node<T>* &Tree)        //满二叉树和完全二叉树的创建方法（非递归）
{
    Bt_Node<T>* Bt_Node_List[MAXSIZE];        //创建节点指针数组
    //Bt_Node_List = new Bt_Node<T>*[MAXSIZE];
    Bt_Node<T>* Start_Node;
    T Data;
    int Index, FindParent;        //Index为树节点编号，FindParent是查找双亲节点的编号
    cin >> Index >> Data;        //输入树节点的编号及数据
    while (Index != 0 && Data != -1)        //编号不为0且输入数据为-1代表结束
    {
        Start_Node = new Bt_Node<T>;
        Start_Node->Data = Data;
        Start_Node->Left_Child = NULL;        //左孩子和右孩子节点先赋值空
        Start_Node->Right_Child = NULL;
        Bt_Node_List[Index] = Start_Node;
        if (Index != 1)        //当该节点不是根节点
        {
            FindParent = Index / 2;            //寻找该节点的双亲节点
            if (Index % 2)                    //若该节点编号对2取余结果为1，说明该节点是其双亲节点的右孩子节点，否则为左孩子节点
                Bt_Node_List[FindParent]->Right_Child = Start_Node;            //双亲节点找到自己的孩子
            else
                Bt_Node_List[FindParent]->Left_Child = Start_Node;
        }
        cin >> Index >> Data;        //继续输入数据
    }
    Tree = Bt_Node_List[1];            //在节点地址数组的位置为1的节点为根节点
    return 1;

4.二叉树的非递归遍历（正文开始）

非递归遍历的思路：递归在一定意义上就是将每一步操作入栈然后在满足停止入栈时开始出栈，所以对于二叉树的非递归遍历，也是借用栈，通过对节点的出栈入栈，实现各种遍历。

（1）先序遍历

①思路：

先序是：根左右，每一次都将一个节点出栈并访问节点数组，然后先入栈右非空节点，再入栈左非空节点（因为栈满足后进先出），直到栈空时结束遍历。

②代码实现：

template<class T>
void Binary_tree<T>::PreOrder_Op(Bt_Node<T>* &Tree)
{
    Bt_Node<T>* BtNode_Stack[MAXSIZE],*Stack_Top;        //BtNode_Stack[MAXSIZE]为节点指针数组，用于模拟栈操作，Stack_Top用于存放栈顶根节点
    int Top = -1;        //初始栈空
    if (Tree)            //根节点非空时
    {
        BtNode_Stack[++Top] = Tree;        //根节点入栈
        while (Top > -1)        //栈非空时，遍历
        {
            Stack_Top = BtNode_Stack[Top--];        //将栈顶节点出栈
            cout << Stack_Top->Data << endl;
            if (Stack_Top->Right_Child != NULL)            //右孩子非空先入栈
                BtNode_Stack[++Top] = Stack_Top->Right_Child;
            if (Stack_Top->Left_Child != NULL)            //左孩子非空再入栈
                BtNode_Stack[++Top] = Stack_Top->Left_Child;
        }
    }
}

（2)中序遍历

①思路：

中序：左根右，中序都是从树的最左边节点开始遍历的，所以对于每个节点下属的子树，都是找到该子树的最左节点，将该方向上的节点全部入栈，然后在栈非空的条件下出栈一个节点，访问该节点的数据，后入栈该节点的右节点，直到当前节点空并且栈空时结束遍历。

②代码实现：

template<class T>
void Binary_tree<T>::InOrder_Op(Bt_Node<T>* &Tree)
{
    Bt_Node<T>* BtNode_Stack[MAXSIZE], *Stack_Top;        //BtNode_Stack[MAXSIZE]为节点指针数组，用于模拟栈操作，Stack_Top用于存放栈顶根节点
    int Top = -1;        //初始栈空
    if (Tree)//根节点非空下
    {
        Stack_Top = Tree;        //根节点
        while (Top > -1 || Stack_Top)        //如果栈非空或者节点非空
        {
            while (Stack_Top)            //将该方向上所有的左孩子（包括当前的双亲节点入栈）
            {
                BtNode_Stack[++Top] = Stack_Top;
                Stack_Top = Stack_Top->Left_Child;
            }
            if (Top > -1)        //栈非空时可以访问
            {
                Stack_Top = BtNode_Stack[Top--];        //出栈节点
                cout << Stack_Top->Data << endl;        //访问该节点元素
                Stack_Top = Stack_Top->Right_Child;        //指向右孩子节点
            }
        }
    }
}

（3)后序遍历

①思路：

与中序遍历相同，都是将左节点沿最左方向先入栈，但因为后续遍历的根节点是最后被访问的，所以要出栈必须满足它的左右节点均被访问，所以需要记录前一次访问的节点，如果当前节点的左子树节点刚好是前一次访问的节点，那么出栈原节点。分状态执行，一种状态是原节点模式（袖珍树的遍历），一种是新节点模式，需要入栈方向左树。

②代码：

template<class T>
void Binary_tree<T>::PostOrder_Op(Bt_Node<T>* &Tree)
{
    Bt_Node<T>* BtNode_Stack[MAXSIZE], *Stack_Top;        //BtNode_Stack[MAXSIZE]为节点指针数组，用于模拟栈操作，Stack_Top用于存放栈顶根节点
    Bt_Node<T> *Last_Check;                //保存刚访问过的节点
    int Top = -1;        //初始栈空
    int Flag;
    Stack_Top = Tree;
    if (Tree)        //根节点非空时进行遍历
    {
        do
        {
            while (Stack_Top)        //将该节点所有左孩子节点入栈
            {
                BtNode_Stack[++Top] = Stack_Top;
                Stack_Top = Stack_Top->Left_Child;
            }
            Last_Check = NULL;            //Last_Check指向栈顶节点的前一个已访问过的节点
            Flag = 1;                //Flag=1表示处理根节点，Flag=0表示处理新的节点，此时需要将该节点的所以左孩子入栈
            while (Top != -1 && Flag == 1)        //栈非空并且程序处于处理原节点状态
            {
                Stack_Top = BtNode_Stack[Top];
                if (Stack_Top->Right_Child == Last_Check)        //如果已经处理完右孩子节点或者右孩子节点为空，可以访问栈顶节点
                {
                    cout << Stack_Top->Data << endl;
                    Top--;
                    Last_Check = Stack_Top;        //Last_Check指向刚刚访问过的节点
                }
                else               
                {
                    Stack_Top = Stack_Top->Right_Child;        //准备处理右孩子节点
                    Flag = 0;
                }
            }
        } while (Top!=-1);
    }
}

(4)层次遍历

①思路：

不同于前三种遍历方式，层次遍历不能依靠完全递归实现，在上一篇二叉树递归实现中我介绍了一种方法是通过穷举二叉树的层数，并对每一层进行递归遍历，这种方法的优点是可以通过每一层遍历完换行清晰看出每一层的数据情况。而下面介绍的这种方法，是通过循环队列，循环入队根节点，左节点，右节点，模拟层次遍历，而说到循环队列，什么时候比较困我就发出来吧，毕竟压了特别久。

②代码：

template<class T>
void Binary_tree<T>::LevelOrder_Op(Bt_Node<T>* &Tree)
{
    Bt_Node<T> *Queue_Top;            //队头节点
    Bt_Node<T>* BtNode_Queue[MAXSIZE];            //定义循环队列
    int Front, Rear;            //队头，队尾
    Front = Rear = -1;
    BtNode_Queue[++Rear] = Tree;        //入队根节点
    while (Front != Rear)        //队未空
    {
        Front = (Front + 1) % MAXSIZE;        //循环队列特有的队头循环（通过取余实现）
        Queue_Top = BtNode_Queue[Front];        //将队头节点出队
        cout << Queue_Top->Data << endl;        //访问节点数据
        if (Queue_Top->Left_Child != NULL)        //左孩子节点非空入队
        {
            Rear = (Rear + 1) % MAXSIZE;
            BtNode_Queue[Rear] = Queue_Top->Left_Child;
        }
        if (Queue_Top->Right_Child != NULL)        //右孩子节点非空入队
        {
            Rear = (Rear + 1) % MAXSIZE;
            BtNode_Queue[Rear] = Queue_Top->Right_Child;
        }
    }
}

5.类实现代码（全部）

#include<iostream>
using namespace std;
#define MAXSIZE 100
template<class T>
struct Bt_Node
{
    T Data;
    Bt_Node* Left_Child;
    Bt_Node* Right_Child;
};
template<class T>
class Binary_tree
{
private:
    Bt_Node<T> *Tree;
    /*内部实现函数*/
    int Create_BTree(Bt_Node<T>* &Tree);            //创建二叉树（构造内调用）
    int Distory_BTree(Bt_Node<T>* &Tree);            //析构二叉树的递归子函数（在析构内调用）
    void PreOrder_Op(Bt_Node<T>* &Tree);                //先序遍历(非递归实现函数）
    void InOrder_Op(Bt_Node<T>* &Tree);                    //中序遍历（非递归实现函数）
    void PostOrder_Op(Bt_Node<T>* &Tree);                //后序遍历（非递归实现函数）
    void LevelOrder_Op(Bt_Node<T>* &Tree);                //层次遍历的非递归子函数
public:
    /*接口函数*/
    Binary_tree();                            //类构造
    ~Binary_tree();                            //析构
    void PreOrder();                    //先序遍历
    void InOrder();                        //中序遍历
    void PostOrder();
    void LevelOrder();                        //层次遍历
};
/*template<class T>
int Binary_tree<T>::Create_BTree(Bt_Node<T>* &Tree)        //满二叉树和完全二叉树的创建方法（非递归）
{
    Bt_Node<T>* Bt_Node_List[MAXSIZE];        //创建节点指针数组
    //Bt_Node_List = new Bt_Node<T>*[MAXSIZE];
    Bt_Node<T>* Start_Node;
    T Data;
    int Index, FindParent;        //Index为树节点编号，FindParent是查找双亲节点的编号
    cin >> Index >> Data;        //输入树节点的编号及数据
    while (Index != 0 && Data != -1)        //编号不为0且输入数据为-1代表结束
    {
        Start_Node = new Bt_Node<T>;
        Start_Node->Data = Data;
        Start_Node->Left_Child = NULL;        //左孩子和右孩子节点先赋值空
        Start_Node->Right_Child = NULL;
        Bt_Node_List[Index] = Start_Node;
        if (Index != 1)        //当该节点不是根节点
        {
            FindParent = Index / 2;            //寻找该节点的双亲节点
            if (Index % 2)                    //若该节点编号对2取余结果为1，说明该节点是其双亲节点的右孩子节点，否则为左孩子节点
                Bt_Node_List[FindParent]->Right_Child = Start_Node;            //双亲节点找到自己的孩子
            else
                Bt_Node_List[FindParent]->Left_Child = Start_Node;
        }
        cin >> Index >> Data;        //继续输入数据
    }
    Tree = Bt_Node_List[1];            //在节点地址数组的位置为1的节点为根节点
    return 1;
}*/
template<class T>
int Binary_tree<T>::Create_BTree(Bt_Node<T>* &Tree)
{
    T Data;
    cin >> Data;
    if (Data == -1)
        Tree = NULL;
    else
    {
        Tree = new Bt_Node<T>;
        Tree->Data = Data;
        Create_BTree(Tree->Left_Child);
        Create_BTree(Tree->Right_Child);
    }
    return 1;
}
template<class T>
int Binary_tree<T>::Distory_BTree(Bt_Node<T>* &Tree)
{
    if (Tree)
    {
        Bt_Node<T>* LeftTree = Tree->Left_Child;
        Bt_Node<T>* RightTree = Tree->Right_Child;
        //cout << Tree->Data << endl;
        delete Tree;
        if (LeftTree)
            Distory_BTree(LeftTree);
        if (RightTree)
            Distory_BTree(RightTree);
    }
    return 0;
}
template<class T>
void Binary_tree<T>::PreOrder_Op(Bt_Node<T>* &Tree)
{
    Bt_Node<T>* BtNode_Stack[MAXSIZE],*Stack_Top;        //BtNode_Stack[MAXSIZE]为节点指针数组，用于模拟栈操作，Stack_Top用于存放栈顶根节点
    int Top = -1;        //初始栈空
    if (Tree)            //根节点非空时
    {
        BtNode_Stack[++Top] = Tree;        //根节点入栈
        while (Top > -1)        //栈非空时，遍历
        {
            Stack_Top = BtNode_Stack[Top--];        //将栈顶节点出栈
            cout << Stack_Top->Data << endl;
            if (Stack_Top->Right_Child != NULL)            //右孩子非空先入栈
                BtNode_Stack[++Top] = Stack_Top->Right_Child;
            if (Stack_Top->Left_Child != NULL)            //左孩子非空再入栈
                BtNode_Stack[++Top] = Stack_Top->Left_Child;
        }
    }
}
template<class T>
void Binary_tree<T>::InOrder_Op(Bt_Node<T>* &Tree)
{
    Bt_Node<T>* BtNode_Stack[MAXSIZE], *Stack_Top;        //BtNode_Stack[MAXSIZE]为节点指针数组，用于模拟栈操作，Stack_Top用于存放栈顶根节点
    int Top = -1;        //初始栈空
    if (Tree)//根节点非空下
    {
        Stack_Top = Tree;        //根节点
        while (Top > -1 || Stack_Top)        //如果栈非空或者节点非空
        {
            while (Stack_Top)            //将该方向上所有的左孩子（包括当前的双亲节点入栈）
            {
                BtNode_Stack[++Top] = Stack_Top;
                Stack_Top = Stack_Top->Left_Child;
            }
            if (Top > -1)        //栈非空时可以访问
            {
                Stack_Top = BtNode_Stack[Top--];        //出栈节点
                cout << Stack_Top->Data << endl;        //访问该节点元素
                Stack_Top = Stack_Top->Right_Child;        //该节点的右孩子节点入栈
            }
        }
    }
}
template<class T>
void Binary_tree<T>::PostOrder_Op(Bt_Node<T>* &Tree)
{
    Bt_Node<T>* BtNode_Stack[MAXSIZE], *Stack_Top;        //BtNode_Stack[MAXSIZE]为节点指针数组，用于模拟栈操作，Stack_Top用于存放栈顶根节点
    Bt_Node<T> *Last_Check;                //保存刚访问过的节点
    int Top = -1;        //初始栈空
    int Flag;
    Stack_Top = Tree;
    if (Tree)        //根节点非空时进行遍历
    {
        do
        {
            while (Stack_Top)        //将该节点所有左孩子节点入栈
            {
                BtNode_Stack[++Top] = Stack_Top;
                Stack_Top = Stack_Top->Left_Child;
            }
            Last_Check = NULL;            //Last_Check指向栈顶节点的前一个已访问过的节点
            Flag = 1;                //Flag=1表示处理根节点，Flag=0表示处理新的节点，此时需要将该节点的所以左孩子入栈
            while (Top != -1 && Flag == 1)        //栈非空并且程序处于处理原节点状态
            {
                Stack_Top = BtNode_Stack[Top];
                if (Stack_Top->Right_Child == Last_Check)        //如果已经处理完右孩子节点或者右孩子节点为空，可以访问栈顶节点
                {
                    cout << Stack_Top->Data << endl;
                    Top--;
                    Last_Check = Stack_Top;        //Last_Check指向刚刚访问过的节点
                }
                else               
                {
                    Stack_Top = Stack_Top->Right_Child;        //准备处理右孩子节点
                    Flag = 0;
                }
            }
        } while (Top!=-1);
    }
}
template<class T>
void Binary_tree<T>::LevelOrder_Op(Bt_Node<T>* &Tree)
{
    Bt_Node<T> *Queue_Top;            //队头节点
    Bt_Node<T>* BtNode_Queue[MAXSIZE];            //定义循环队列
    int Front, Rear;            //队头，队尾
    Front = Rear = -1;
    BtNode_Queue[++Rear] = Tree;        //入队根节点
    while (Front != Rear)        //队未空
    {
        Front = (Front + 1) % MAXSIZE;        //循环队列特有的队头循环（通过取余实现）
        Queue_Top = BtNode_Queue[Front];        //将队头节点出队
        cout << Queue_Top->Data << endl;        //访问节点数据
        if (Queue_Top->Left_Child != NULL)        //左孩子节点非空入队
        {
            Rear = (Rear + 1) % MAXSIZE;
            BtNode_Queue[Rear] = Queue_Top->Left_Child;
        }
        if (Queue_Top->Right_Child != NULL)        //右孩子节点非空入队
        {
            Rear = (Rear + 1) % MAXSIZE;
            BtNode_Queue[Rear] = Queue_Top->Right_Child;
        }
    }
}
template<class T>
Binary_tree<T>::Binary_tree()
{
    Create_BTree(Tree);
}
template<class T>
Binary_tree<T>::~Binary_tree()
{
    Distory_BTree(Tree);
}
template<class T>
void Binary_tree<T>::PreOrder()
{
    PreOrder_Op(Tree);
}
template<class T>
void Binary_tree<T>::InOrder()
{
    InOrder_Op(Tree);
}
template<class T>
void Binary_tree<T>::PostOrder()
{
    PostOrder_Op(Tree);
}
template<class T>
void Binary_tree<T>::LevelOrder()
{
    LevelOrder_Op(Tree);
}

日常BB:

这算是这半年来觉得最难啃的代码了，可能自己比较弱鸡，不过的确写完之后我自己都还是对整个过程有点模糊，慢慢看吧~共勉，其实后面还有难的，就是将二叉树线索化，重点来了，下篇见~