二叉树基础：先序、中序、后序递归及非递归实现与层次遍历

目录

• • • 代码
    • 思路

代码

/*************************************************************************
	> File Name: treeSample.cpp
	> Author:Ryan 
	> Mail: 
	> Created Time: Sun Oct 11 10:35:22 2020
 ************************************************************************/

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
/* 
 *node of the tree  
 */
struct BTreeNode{
    int val;
    BTreeNode *LChild;
    BTreeNode *RChild;
    BTreeNode(int val):val(val),LChild(NULL),RChild(NULL){} 
};
/*
 *BTree 
 */ 
class BTree{
    private:
        BTreeNode *root;
        int n;
    public:
        BTree():root(NULL){}
        BTree(vector<int>);//bulid tree
        
        void createTree(vector<int>,BTreeNode *&);//build the tree in preorder by recursion
        
        void show();//show the tree by recursion
        void showTree(BTreeNode*);//show the tree in preorder by recursion
        void showTree1(BTreeNode*);//show the tree in midorder by recursion
        void showTree2(BTreeNode*);//show the tree in postorder by recursion

        void show1();//show the tree not by recursion
        void showTree3(BTreeNode*);//show the tree in preorder not by recursion
        void showTree4(BTreeNode*);//show the tree in midorder not by recursion
        void showTree5(BTreeNode*);//show the tree in postorder not by recursion
        
        void show2();    
        void show_lT(BTreeNode*); //show the tree's level_traversal
};     
/*
 *build the tree in preorder 
 */ 
BTree::BTree(vector<int> num){
    n=0;
    createTree(num,root);
}
void BTree::createTree(vector<int> num,BTreeNode *&node){
    if(num.size()>=n+1&&num[n]!=-1){
        node = new BTreeNode(num[n++]);
        createTree(num,node->LChild);
        createTree(num,node->RChild);
    }
    else{
        n++;
    }   
}

/*
 *show the tree by recursion 
 */ 
 void BTree::show(){
    /*show in preorder*/
    cout<<"Here shows in preorder by recursion"<<endl;
    showTree(root);
    cout<<endl;

    /*show in midorder*/ 
    cout<<"Here shows in midorder by recursion"<<endl;
    showTree1(root);
    cout<<endl;
    
    /*show in postorder*/
    cout<<"Here shows in postorder by recursion"<<endl;
    showTree2(root);
    cout<<endl;
}

/*
 *show in preorder by recursion
 */ 
void BTree::showTree(BTreeNode *node){
    if(node!=NULL){
        cout<<node->val;
        showTree(node->LChild);
        showTree(node->RChild);
    }
}

/*
 *show in midorder by recursion
 */ 
void BTree::showTree1(BTreeNode *node){
    if(node!=NULL){
        showTree1(node->LChild);
        cout<<node->val;
        showTree1(node->RChild);
    }
}

/*
 *show in postorder by recursion
 */ 
void BTree::showTree2(BTreeNode *node){
    if(node!=NULL){
        showTree2(node->LChild);
        showTree2(node->RChild);
        cout<<node->val;
    }
}

/*
 *show the tree not by recursion
 */ 
 void BTree::show1(){
    
    /*show in preorder*/
    cout<<"Here shows in preorder"<<endl;
    showTree3(root);
    cout<<endl;

    /*show in midorder*/ 
    cout<<"Here shows in midorder"<<endl;
    showTree4(root);
    cout<<endl;
    
    /*show in postorder*/
    cout<<"Here shows in postorder"<<endl;
    showTree5(root);
    cout<<endl;
 }
/*
 *show in preorder
 */ 
void BTree::showTree3(BTreeNode *node){
    stack<BTreeNode*> s;
    if(node!=NULL) s.push(node);

    while(!s.empty()){
        BTreeNode *tmp = s.top();s.pop();
        cout<<tmp->val;
        if(tmp->RChild!=NULL) s.push(tmp->RChild);
        if(tmp->LChild!=NULL) s.push(tmp->LChild);
    }
}
/*
 *show in midorder
 */ 
void BTree::showTree4(BTreeNode *node){
    BTreeNode *p = node;
    stack<BTreeNode*> s;

    while(1){
        if(p->LChild!=NULL){ 
            s.push(p);
            p = p->LChild;
        }
        else if(!p->LChild){
            cout<<p->val;
            if(p->RChild!=NULL) {p=p->RChild;continue;}
            while(!s.empty()&&!p->RChild){
                p = s.top();s.pop();
                cout<<p->val;
            }
            if(p->RChild!=NULL) p=p->RChild;
            else if(p->RChild==NULL) break;
        }
    }
}

/*
 *show in postorder
 */ 
void BTree::showTree5(BTreeNode *node){
    cout<<"不想敲，可以参考网址：https://www.cnblogs.com/SHERO-Vae/p/5800363.html"<<endl;
}

/*
 *show the tree's level_traversal
 */ 
 void BTree::show2(){
    cout<<"Here's level_traversal"<<endl;
    show_lT(root);
    cout<<endl;
 }

 void BTree::show_lT(BTreeNode *node){
    queue<BTreeNode*> q;
    if(node!=NULL) q.push(node);
    
     BTreeNode *tmp;
     while(!q.empty()){
         tmp = q.front();q.pop();
         cout<<tmp->val;
         if(tmp->LChild!=NULL) q.push(tmp->LChild);
         if(tmp->RChild!=NULL) q.push(tmp->RChild);
     }
 }

int main(){
    vector<int> tmp {1,2,-1,-1,3,4,-1,-1,5,6,-1,-1,7,-1,-1};
    BTree *btree = new BTree(tmp);
    btree->show();
    btree->show1();
    btree->show2();
}

思路

这里记录下非递归的一些思路：

先序遍历

先序遍历循环处理：
1.获取栈顶结点为当前节点
2.访问且右结点和左结点进栈（若有）

中序遍历

中序遍历循环处理：
1.有左结点，进栈，当前结点为左结点，例1,3,5
2.无左结点，访问，
若有右结点，使当前结点为右结点
若无右结点，栈非空前循环退栈直到有右结点的结点为当前结点，也就是1,3,5
3.上述执行完后，若无右结点，则退出循环，例 7
‘’’
也就是说出栈的都是左结点部分全部访问完的，栈空且当前结点无右结点则遍历完毕
‘’’

后序遍历

后序遍历循环处理，貌似要添加记录变量，懒得敲（菜）
参考博客：二叉树先序、中序、后序非递归实现

层次遍历

层次遍历：
这个比较简单，利用队列结构先进先出特点。

构建的树如下：

运行结果如下：