层次建立二叉树、非递归遍历二叉树(C++实现)

按层次建立二叉树
按层次建立二叉树，比较直观方便。思路与按层次遍历二叉树一样。
首先，输入数据，数据存放在数组 a[ ] 中，若输入 >0 则代表该二叉树结点的数据，若 =0 则该结点为NULL，若<0则输入结束。
1.开辟根结点内存，数据赋值。放入队列中
2.遍历数组a[ ] ；取出队头结点，判断当前 a[i] 和 a[i+1]，注意：若a[i] == 0 或 a[i+1] == 0 则不开辟内存，若a[i]>0给其左子树开辟内存，左子树的data = a[i] ，左子树放入队列尾中；若a[i + 1]>0，给其右子树开辟内存，右子树放入队列尾中。i++ 。

完整可运行代码在末尾

按层次建立二叉树 代码：

//层次遍历方式 建立二叉树
//按层次遍历方式输入，若 >0 则代表该二叉树结点的数据，若 =0 则该结点为NULL，若<0则输入结束
void createTree(node* &T) {
    queue<node*> que;
    int n ,i=0;
    cin >> n;
    while (true) {      //输入，数据存放在数组a[]中
        a[i] = n;
        cin >> n;
        if (n < 0) break;
        i++;
    }
    T = new node;
    T->data = a[0];
    T->lchirld = NULL;
    T->rchirld = NULL;
    node *p = T , *q;
    que.push(p);
    i = 1;
    while (!que.empty()) {
        p = que.front();    //获取对头的结点指针
        que.pop();
        if (!p) continue;   //从队头获取到的 结点，若为空，则跳过本次循环

        if (a[i] > 0) { //若 >0 则创建该二叉树结点的左孩子
            q = new node;
            q->data = a[i];
            q->lchirld = NULL;
            q->rchirld = NULL;
            p->lchirld = q;
        }
        else {      //否则该结点的左孩子为空
            p->lchirld = NULL;
        }
        que.push(p->lchirld);   //左孩子进队列

        if (a[i + 1] > 0) { //若 >0 则创建该二叉树结点的右孩子
            q = new node;
            q->data = a[i + 1];
            q->lchirld = NULL;
            q->rchirld = NULL;
            p->rchirld = q;
        }
        else {  //否则该结点的右孩子为空
            p->rchirld = NULL;
        }
        que.push(p->rchirld);   //右孩子进队列

        i += 2;
        if (a[i] == -1) return;
    }

}

非递归 先序遍历二叉树
前序遍历的递归定义：先根节点，后左子树，再右子树。
　　首先，我们遍历左子树，边遍历边打印，并把根节点存入栈中，以后需借助这些节点进入右子树开启新一轮的循环。还得重复一句：所有的节点都可看做是根节点。

//非递归方法实现 先序遍历(栈实现)
void prePrint(node* T) {
    stack<node* > s;
    node* p = T;
    s.push(p);
    while (!s.empty()) {
        p = s.top();
        s.pop();
        if (p) {
            s.push(p->rchirld);
            s.push(p->lchirld);
            cout << p->data << " ";
        }
    }
}

非递归 中序遍历二叉树
我们直到中序排列的顺序是：左节点，根节点，右节点。那么我们在经过根节点的前面节点 不能释放， 因为后面还需要用到它。所以要用栈先储存。
它的规则大致为：

栈依次存入左节点所有点，直到最左侧在栈顶。
开始抛出栈顶并访问。(例如第一个抛出2)。如果有右节点。那么将右节点加入栈中，然后右节点一致左下遍历直到尾部。（这里5和7没有左节点，所以不加）但是如果抛出15。右节点加入23.再找23的左侧节点加入栈顶。就这样循环下去直到栈为空。
可行性分析：中序是左—中—右的顺序。访问完左侧。当抛出当前点的时候说明左侧已经访问完(或者自己就是左侧)，那么需要首先访问当前点的右侧。那么这个右节点把它当成根节点重复相同操作（因为右节点要满足先左再右的顺序）。这样其实就是模拟了一个递归的过程，需要自己思考。

//非递归方法实现 中序遍历(栈实现)
void ordPrint(node* T) {
    stack<node* > s;
    node* p = T;
    s.push(p);
    p = p->lchirld;
    while (!s.empty() || p) {
        while (p) {
            s.push(p);
            p = p->lchirld;
        }
        if (!s.empty()) {
            cout << s.top()->data<<" ";
            p = s.top()->rchirld;
            s.pop();
        }
    }
}

非递归 后序遍历二叉树
后序遍历递归定义：先左子树，后右子树，再根节点。
　　后序遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。直接看代码，代码中有详细的注释。

//非递归 后序遍历
void postPrint(node* T) {
    stack<node* > s;
    node* p = T ,* lastPrint = NULL;    //lastPrint记录上一次被遍历的结点
    while (p) {
        s.push(p);
        p = p->lchirld;
    }

    while (!s.empty()) {
        //走到这里，p都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
        p = s.top();
        s.pop();
        //一个根节点被访问的前提是：无右子树或右子树已被访问过
        if (p->rchirld == NULL || p->rchirld == lastPrint) {
            cout << p->data << " ";
            //修改最近被访问的节点
            lastPrint = p;
        }
        else {
            //根节点再次入栈
            s.push(p);
            //进入右子树，且可肯定右子树一定不为空
            p = p->rchirld;
            while (p) {
                s.push(p);
                p = p->lchirld;
            }
        }
    }
}

完整可运行代码:


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

/*
问题描述：
       按层次建立二叉树
       非递归 先序、中序、后序遍历
*/
int a[100];

struct node {
    int data;
    struct node* lchirld;
    struct node* rchirld;
};

//层次遍历方式 建立二叉树
//按层次遍历方式输入，若 >0 则代表该二叉树结点的数据，若 =0 则该结点为NULL，若<0则输入结束
void createTree(node* &T) {
    queue<node*> que;
    int n ,i=0;
    cin >> n;
    while (true) {      //输入，数据存放在数组a[]中
        a[i] = n;
        cin >> n;
        if (n < 0) break;
        i++;
    }
    T = new node;
    T->data = a[0];
    T->lchirld = NULL;
    T->rchirld = NULL;
    node *p = T , *q;
    que.push(p);
    i = 1;
    while (!que.empty()) {
        p = que.front();    //获取对头的结点指针
        que.pop();
        if (!p) continue;   //从队头获取到的 结点，若为空，则跳过本次循环

        if (a[i] > 0) { //若 >0 则创建该二叉树结点的左孩子
            q = new node;
            q->data = a[i];
            q->lchirld = NULL;
            q->rchirld = NULL;
            p->lchirld = q;
        }
        else {      //否则该结点的左孩子为空
            p->lchirld = NULL;
        }
        que.push(p->lchirld);   //左孩子进队列

        if (a[i + 1] > 0) { //若 >0 则创建该二叉树结点的右孩子
            q = new node;
            q->data = a[i + 1];
            q->lchirld = NULL;
            q->rchirld = NULL;
            p->rchirld = q;
        }
        else {  //否则该结点的右孩子为空
            p->rchirld = NULL;
        }
        que.push(p->rchirld);   //右孩子进队列

        i += 2;
        if (a[i] == -1) return;
    }

}

void print(node* &T) {      //先序遍历
    if (T) {
        cout << T->data<<" ";
        print(T->lchirld);
        print(T->rchirld);
    }
}

//非递归方法实现 先序遍历(栈实现)
void prePrint(node* T) {
    stack<node* > s;
    node* p = T;
    s.push(p);
    while (!s.empty()) {
        p = s.top();
        s.pop();
        if (p) {
            s.push(p->rchirld);
            s.push(p->lchirld);
            cout << p->data << " ";
        }
    }
}

//非递归方法实现 中序遍历(栈实现)
void ordPrint(node* T) {
    stack<node* > s;
    node* p = T;
    s.push(p);
    p = p->lchirld;
    while (!s.empty() || p) {
        while (p) {
            s.push(p);
            p = p->lchirld;
        }
        if (!s.empty()) {
            cout << s.top()->data<<" ";
            p = s.top()->rchirld;
            s.pop();
        }
    }
}

//非递归 后序遍历
void postPrint(node* T) {
    stack<node* > s;
    node* p = T ,* lastPrint = NULL;
    while (p) {
        s.push(p);
        p = p->lchirld;
    }

    while (!s.empty()) {
        //走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
        p = s.top();
        s.pop();
        //一个根节点被访问的前提是：无右子树或右子树已被访问过
        if (p->rchirld == NULL || p->rchirld == lastPrint) {
            cout << p->data << " ";
            //修改最近被访问的节点
            lastPrint = p;
        }
        else {
            //根节点再次入栈
            s.push(p);
            //进入右子树，且可肯定右子树一定不为空
            p = p->rchirld;
            while (p) {
                s.push(p);
                p = p->lchirld;
            }
        }
    }
}



int main() {
    for (int i = 0; i < 100; i++)
        a[i] = -1;      //数组初始化
    node *T;
    createTree(T);      
    prePrint(T);
    cout << endl;
    ordPrint(T);
    cout << endl;
    postPrint(T);
    return 0;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,919评论 6赞 502
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,567评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 163,316评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,294评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,318评论 6赞 390
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,245评论 1赞 299
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,120评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,964评论 0赞 275
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,376评论 1赞 313
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,592评论 2赞 333
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,764评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,460评论 5赞 344
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,070评论 3赞 327
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,697评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,846评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,819评论 2赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,665评论 2赞 354