阿里云优惠
 汇集各种优惠信息 技术资料

首页    编程语言    二叉树前序、中序、后序遍历的非递归写法

二叉树前序、中序、后序遍历的非递归写法

创建时间:2020-06-23 13:14
浏览量:0
收藏

前序和中序遍历的非递归写法都比较好实现,后序遍历稍微复杂一些.

数据结构定义:

struct Node{

char c;
pNode lchild, rchild;
Node(char c, pNode lchild = nullptr, pNode rchild = nullptr) :
    c(c), lchild(lchild), rchild(rchild) {}

};

申请阿里云服务时,可以使用2000元阿里云代金券,阿里云官网领取网址:https://dashi.aliyun.com/site/yun/youhui

二叉树形态:

   A
 /   \
B     C

/ / \
D E F G

   / \
  H   I


前序遍历:

先根遍历,拿到一个节点的指针,先判断是否为空,不为空就先访问该结点,然后直接进栈,接着遍历左子树;为空则要从栈中弹出一个节点来,这个时候弹出的结点就是其父亲,然后访问其父亲的右子树,直到当前节点为空且栈为空时,算法结束.

阿里云服务器1核2G低至82元/年,阿里云官活动网址:https://dashi.aliyun.com/site/yun/aliyun 可以用20代金券,即102-20=82。

void preVisitStack(pNode root)
{

stack<pNode> st;
pNode p = root;
while (p || !st.empty()) {
    if (p) {
        visit(p);
        st.push(p);
        p = p->lchild;
    } else {
        p = st.top();
        st.pop();
        p = p->rchild;
    }
}
cout << endl;

}

中序遍历:

和前序遍历一样,只不过在访问节点的时候顺序不一样,访问节点的时机是从栈中弹出元素时访问,如果从栈中弹出元素,就意味着当前节点父亲的左子树已经遍历完成,这时候访问父亲,就是中序遍历.

void midVisitStack(pNode root)
{

stack<pNode> st;
pNode p = root;
while (p || !st.empty()) {
    if (p) {
        st.push(p);
        p = p->lchild;
    } else {
        p = st.top();
        visit(p);
        st.pop();
        p = p->rchild;
    }
}
cout << endl;

}

后序遍历:

后续遍历就不一样了,首先肯定是先访问左子树,把父亲节点保存于栈中,问题是当元素从栈中弹出的时候,我们无法判断这个时候是该访问其右子树还是访问父亲节点,于是我们就需要一个标记,当访问左子树时我们把父亲节点的标记设为1,表示下一步如果弹出该节点,就访问其右子树;弹出一个节点时,我们要判断该节点的标记,如果是1,则访问其右子树,并把该节点的标记设置成2,表示下一步就访问该节点,然后把该节点继续入栈,如果是2,那么表示访问该节点,访问并且丢弃该节点.

为了不继续添加新的数据结构,我是用了STL中的pair来封装节点与标记.

void backVisitStack(pNode root)
{

stack<pair<pNode, int> > st;
pNode p = root;
while (p || !st.empty()) {
    if (p) {
        st.push(make_pair(p, 1));
        p = p->lchild;
    } else {
        auto now = st.top();
        st.pop();
        if (now.second == 1) {
            st.push(make_pair(now.first, 2));
            p = now.first->rchild;
        } else
            visit(now.first);
    }
}
cout << endl;

}

完整测试代码:

include

using namespace std;

typedef struct Node *pNode;

struct Node{

char c;
pNode lchild, rchild;
Node(char c, pNode lchild = nullptr, pNode rchild = nullptr) :
    c(c), lchild(lchild), rchild(rchild) {}

};

pNode build()
{

/*
         A
       /  \
     B     C
    / \   / \
   D   E F   G
        / \
       H   I
*/
pNode root = new Node('A');
root->lchild = new Node('B');
root->rchild = new Node('C');
root->lchild->lchild = new Node('D');
root->lchild->rchild = new Node('E');
root->rchild->lchild = new Node('F');
root->rchild->rchild = new Node('G');
root->rchild->lchild->lchild = new Node('H');
root->rchild->lchild->rchild = new Node('I');
return root;

}

void visit(pNode x)
{

cout << x->c << " ";

}

void preVisitStack(pNode root)
{

stack<pNode> st;
pNode p = root;
while (p || !st.empty()) {
    if (p) {
        visit(p);
        st.push(p);
        p = p->lchild;
    } else {
        p = st.top();
        st.pop();
        p = p->rchild;
    }
}
cout << endl;

}

void midVisitStack(pNode root)
{

stack<pNode> st;
pNode p = root;
while (p || !st.empty()) {
    if (p) {
        st.push(p);
        p = p->lchild;
    } else {
        p = st.top();
        visit(p);
        st.pop();
        p = p->rchild;
    }
}
cout << endl;

}

void backVisitStack(pNode root)
{

stack<pair<pNode, int> > st;
pNode p = root;
while (p || !st.empty()) {
    if (p) {
        st.push(make_pair(p, 1));
        p = p->lchild;
    } else {
        auto now = st.top();
        st.pop();
        if (now.second == 1) {
            st.push(make_pair(now.first, 2));
            p = now.first->rchild;
        } else
            visit(now.first);
    }
}
cout << endl;

}

int main()
{

pNode root = build();
preVisitStack(root);
midVisitStack(root);
backVisitStack(root);

}

测试结果:

依次为前序、中序、后序遍历的结果.

A B D E C F H I G
D B E A H F I C G
D E B H I F G C A

免费领取阿里云1888元代金券大礼包

 

阿里云新老用户均可领取!
自领取后:限时7天使用!

阿里云服务器2折优惠:低至293元/年

 

 

突发性能实例t5 1核1G:293元/年

突发性能实例t5 1核2G:459元/年

突发性能实例t5 2核4G:798元/年

共享型xn4实例1核1G内存:394元/年

共享型n4实例1核2G内存:653元/年

计算网络增强型实例2核4G内存:1566元/年

计算网络增强型实例4核8G内存:2991元/年

点此查看2折活动详情

阿里云高性能云服务器

 

 

网络增强型云服务器:2核4G ¥720元/年

高频应用云服务器:8核16G ¥4109元/年

本地SSD型云服务器:4核16G ¥6218.40元/年

大数据型云服务器:8核32G ¥11375.00元/年

GPU异构云服务器:16核40G ¥15563.00元/年

新用户满立减:每满1000立减50

 

1、到阿里云官网选购产品
2、加入到购物车
3、结算时立享满减

注意:新用户首次购买时必须先加到购物车,然后一起结算才享受此优惠。

腾讯云CVM云服务器22.07元起

 

 

腾讯云1核1G:22.07元/月、794.73元/3年

腾讯云2核2G:36.48元/月、1313.35元/3年

腾讯云2核4G:43.01元/月、1548.5元/3年

腾讯云4核8G:178.5元/月、6426元/3年