層次建立二叉樹攒驰、非遞歸遍歷二叉樹(C++實現(xiàn))

按層次建立二叉樹
按層次建立二叉樹移层，比較直觀方便仍翰。思路與按層次遍歷二叉樹一樣。
首先观话，輸入數(shù)據予借，數(shù)據存放在數(shù)組 a[ ] 中，若輸入 >0 則代表該二叉樹結點的數(shù)據，若 =0 則該結點為NULL灵迫，若<0則輸入結束秦叛。
1.開辟根結點內存，數(shù)據賦值瀑粥。放入隊列中
2.遍歷數(shù)組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 則代表該二叉樹結點的數(shù)據现柠，若 =0 則該結點為NULL，若<0則輸入結束
void createTree(node* &T) {
    queue<node*> que;
    int n ,i=0;
    cin >> n;
    while (true) {      //輸入弛矛，數(shù)據存放在數(shù)組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;   //從隊頭獲取到的 結點够吩，若為空，則跳過本次循環(huán)

        if (a[i] > 0) { //若 >0 則創(chuàng)建該二叉樹結點的左孩子
            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 則創(chuàng)建該二叉樹結點的右孩子
            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;
    }

}

非遞歸先序遍歷二叉樹
前序遍歷的遞歸定義：先根節(jié)點丈氓，后左子樹周循，再右子樹。
　　首先万俗，我們遍歷左子樹湾笛，邊遍歷邊打印，并把根節(jié)點存入棧中闰歪，以后需借助這些節(jié)點進入右子樹開啟新一輪的循環(huán)嚎研。還得重復一句：所有的節(jié)點都可看做是根節(jié)點。

//非遞歸方法實現(xiàn) 先序遍歷(棧實現(xiàn))
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 << " ";
        }
    }
}

非遞歸中序遍歷二叉樹
我們直到中序排列的順序是：左節(jié)點库倘，根節(jié)點临扮，右節(jié)點。那么我們在經過根節(jié)點的前面節(jié)點不能釋放教翩，因為后面還需要用到它公条。所以要用棧先儲存。
它的規(guī)則大致為：

棧依次存入左節(jié)點所有點迂曲，直到最左側在棧頂。
開始拋出棧頂并訪問寥袭。(例如第一個拋出2)路捧。如果有右節(jié)點关霸。那么將右節(jié)點加入棧中，然后右節(jié)點一致左下遍歷直到尾部杰扫。（這里5和7沒有左節(jié)點队寇，所以不加）但是如果拋出15。右節(jié)點加入23.再找23的左側節(jié)點加入棧頂章姓。就這樣循環(huán)下去直到棧為空佳遣。
可行性分析：中序是左—中—右的順序。訪問完左側凡伊。當拋出當前點的時候說明左側已經訪問完(或者自己就是左側)零渐，那么需要首先訪問當前點的右側。那么這個右節(jié)點把它當成根節(jié)點重復相同操作（因為右節(jié)點要滿足先左再右的順序）系忙。這樣其實就是模擬了一個遞歸的過程诵盼，需要自己思考。

//非遞歸方法實現(xiàn) 中序遍歷(棧實現(xiàn))
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();
        }
    }
}

非遞歸后序遍歷二叉樹
后序遍歷遞歸定義：先左子樹银还，后右子樹风宁，再根節(jié)點。
　　后序遍歷的難點在于：需要判斷上次訪問的節(jié)點是位于左子樹蛹疯，還是右子樹戒财。若是位于左子樹，則需跳過根節(jié)點捺弦，先進入右子樹饮寞，再回頭訪問根節(jié)點；若是位于右子樹羹呵，則直接訪問根節(jié)點骂际。直接看代碼，代碼中有詳細的注釋冈欢。

//非遞歸 后序遍歷
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();
        //一個根節(jié)點被訪問的前提是：無右子樹或右子樹已被訪問過
        if (p->rchirld == NULL || p->rchirld == lastPrint) {
            cout << p->data << " ";
            //修改最近被訪問的節(jié)點
            lastPrint = p;
        }
        else {
            //根節(jié)點再次入棧
            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 則代表該二叉樹結點的數(shù)據邻吭，若 =0 則該結點為NULL餐弱，若<0則輸入結束
void createTree(node* &T) {
    queue<node*> que;
    int n ,i=0;
    cin >> n;
    while (true) {      //輸入，數(shù)據存放在數(shù)組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;   //從隊頭獲取到的 結點，若為空膏蚓，則跳過本次循環(huán)

        if (a[i] > 0) { //若 >0 則創(chuàng)建該二叉樹結點的左孩子
            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 則創(chuàng)建該二叉樹結點的右孩子
            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);
    }
}

//非遞歸方法實現(xiàn) 先序遍歷(棧實現(xiàn))
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 << " ";
        }
    }
}

//非遞歸方法實現(xiàn) 中序遍歷(棧實現(xiàn))
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();
        //一個根節(jié)點被訪問的前提是：無右子樹或右子樹已被訪問過
        if (p->rchirld == NULL || p->rchirld == lastPrint) {
            cout << p->data << " ";
            //修改最近被訪問的節(jié)點
            lastPrint = p;
        }
        else {
            //根節(jié)點再次入棧
            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;      //數(shù)組初始化
    node *T;
    createTree(T);      
    prePrint(T);
    cout << endl;
    ordPrint(T);
    cout << endl;
    postPrint(T);
    return 0;
}

層次建立二叉樹着帽、非遞歸遍歷二叉樹(C++實現(xiàn))

層次建立二叉樹、非遞歸遍歷二叉樹(C++實現(xiàn))