数据结构 | 二叉树 先根、中根、后根遍历的非递归算法

数据结构 | 二叉树 先根、中根、后根遍历的非递归算法

---

上期文章： 数据结构 | 树与二叉树

参考教材：《数据结构》，刘大有

编程语言： C++

---

目录

（一）二叉树的存储结构

（二）二叉树的遍历

先根遍历非递归算法

中根遍历非递归算法

后根遍历非递归算法

---

（一）二叉树的存储结构

 二叉树在计算机中具有顺序存储和链式存储两种存储方式。在本文所讨论的算法中，二叉树均是采用二叉链表的存储方式

struct Node{
    Node *left;
    Node *right;
    char data;
    Node():left(nullptr),right(nullptr),data('#'){}
};

其中left为指向该结点左儿子的指针，right为指向该结点右儿子的指针 

（二）二叉树的遍历 先根遍历非递归算法

先根遍历的顺序为①访问根、②遍历左子树、③遍历右子树

为了实现先根遍历的非递归算法，我们需要引进一个辅助堆栈，栈的元素为Node *类型

//栈
class Stack{
public:
    Stack():top(0){
        for(int i=0;i 
先根遍历的非递归算法较为简单，用自然语言描述就是：
 
根结点入栈判断，如果栈为空则结束算法；否则，当栈不为空时：d栈，访问该结点；如果该结点右儿子存在则入栈；如果该结点左儿子存在则入栈返回第2步
void nPreOrder(Node * root){
    if(root == nullptr){
        return;
    }
    Stack s;
    Node *p=root;
    //根节点入栈
    s.push(p);
    //栈不为空时:
    while(!s.isEmpty()){
        //d栈:
        p=s.pop();
        cout<data;
        //右儿子入栈:
        if(p->right!=nullptr){
            s.push(p->right);
        }
        //左儿子入栈:
        if(p->left!=nullptr){
            s.push(p->left);
        }
    }
    return;
}
 
 
 
以下面这棵树为例
 
 
 
 
算法执行过程中，栈的变化情况如下，最终输出的先根序列为ABDFCE：
 
 
 
 

中根遍历非递归算法 
中根遍历的顺序为①遍历左子树、②访问根、③遍历右子树
 
中根遍历的非递归算法也需要引入辅助堆栈，栈的结构与上面先根遍历非递归算法用到的栈Stack相同
 
中根遍历非递归算法思想：
 
令p=root判断，如果栈不为空或p不等于nullptr，执行下一步；否则算法结束当p不等于nullptr（空指针）时，让p结点入栈；如果p结点的左儿子存在，也让其左儿子入栈；如果p结点左儿子的左儿子存在，依然让其左儿子的左儿子入栈......以此类推，直到p的某一个后裔结点不存在左儿子时，执行下一步d出栈顶元素（这时候栈一定不为空），访问该结点，把该结点的右儿子的地址赋值给p；返回第2步
void nInOrder(Node * root){
    if(root==nullptr){
        return;
    }
    Stack s;
    Node *p=root;

    while( (!s.isEmpty()) || (p!=nullptr) ){
        while(p!=nullptr){
            s.push(p);
            p=p->left;
        }
        p=s.pop();
        cout<data;
        p=p->right;
    }
}
 
 
 
以下面这棵树为例
 
 
 
 
算法执行过程中，栈的变化情况如下，最终输出的中根序列为BFDAEC：
 
 
 
 

后根遍历非递归算法 
后根遍历的顺序为①遍历左子树、②遍历右子树、③访问根
 
后根遍历的非递归算法依然需要引入辅助堆栈。但是注意，这里栈的结构与上面的栈结构不同，这里栈的元素为包含Node *和int 类型的结构体
 
//栈2元素的结构
struct NodeOfStack{
    Node *pnode;
    int times;//入栈次数
    NodeOfStack():pnode(nullptr),times(0){}
};
 
其中pnode为Node *类型的指针，times记录了该结点入栈的次数 ，times的值可取0,1,2
 
栈2的定义如下：
 
//栈2
class Stack2{
public:
    Stack2():top(0){
        for(int i=0;i0){
            top--;
            return s[top];
        }
    }
    bool isEmpty(){
        if(top==0)
            return true;
        else
            return false;
    }
private:
    const int s_size=20;
    NodeOfStack s[20];
    int top;
};
 
后根遍历的非递归算法：
 
(root,0)入栈判断，如果栈为空，结束算法；否则，栈不为空时：d栈，记为(p,times)。①若times==0，(p,1)入栈，如果p的左儿子存在则(p->left,0)也压入栈。②若times==1，(p,2)入栈，如果p的右儿子存在则(p->right,0)也压入栈。③若times==2，访问p结点返回第2步

void nPostOrder(Node * root){
    if(root==nullptr){
        return;
    }
    Stack2 s;
    s.push(root,0);
    while(!s.isEmpty()){
        NodeOfStack nos=s.pop();//中间变量，存储每一次栈d出的数据
        Node *p=nos.pnode;
        if(nos.times==0){
            s.push(nos.pnode,1);
            if(p->left!=nullptr){
                s.push(p->left,0);
            }
        }else if(nos.times==1){
            s.push(nos.pnode,2);
            if(p->right!=nullptr){
                s.push(p->right,0);
            }
        }else if(nos.times==2){
            cout<data;
        }
    }
}
 
 
 
 以下面这棵树为例
 
 
 
 
最终输出的后根序列为FDBECA
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5719097.html