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

标签: 二叉树  

代码

/*************************************************************************
	> 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
‘’’
也就是说出栈的都是左结点部分全部访问完的,栈空且当前结点无右结点则遍历完毕
‘’’

后序遍历

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

层次遍历

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

构建的树如下:
在这里插入图片描述
运行结果如下:
在这里插入图片描述

版权声明:本文为weixin_45146520原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45146520/article/details/109034889

智能推荐

RxJava源码分析(2) 变换原理

RxJava源码分析基于RxJava1.3.8。 在上一章节中,主要介绍了RxJava的基本使用并对该部分的源码做了详细分析。在这一章节中,将主要介绍RxJava的另一大核心功能:变换。 变换,就是将事件序列中的对象或整个序列进行加工处理,转换成不同的事件或事件序列。 在RxJava中,提供了许多针对不同场景实现变换功能的操作符,如下: map() flatMap(), concatMap(), ...

CVE-2017-11176: A step-by-step Linux Kernel exploitation (part 4/4)

CVE-2017-11176: A step-by-step Linux Kernel exploitation (part 3/4) 本文的原文地址:https://blog.lexfo.fr/cve-2017-11176-linux-kernel-exploitation-part4.html 介绍 在最后的这个部分中,我们将会把任意调用转换成在ring0权限下的任意代码执行,修复内核拿到ro...

一道简单的Docker题

docker是什么? 我觉得大致可以理解为linux环境下的虚拟机(容器) 就跟windows环境下的vmware一样 在打中科大hackergame2020的时候发现有一道docker题 先复习下docker的相关命令: 这里! 然后开始做题 首先先配置好本地的docker环境,apt-get换成浙大源(经过测试这个源下载安装docker速度超快,吊打阿里清华源) 然后安装 docker 首先需...

企业权限管理系统---产品管理

查询所有产品 添加产品 具体实现: jsp页面内容: Cntroller层代码 service层 dao层...

拒绝无用功,封装一个通用的PopupWindow

作者: 夏至,欢迎转载,但请保留这段申明,谢谢 https://juejin.im/post/5961e03e51882568b13c3308 为了避免重复造轮子,我们一般都会封装一个通用的控件,比如这次,项目中需要用到比较多的 popupwindow ,如果需要一个个写,那么依旧会累死人,而且还是无用功,无意义,所以,封装一个通用的,除了让同事看了直刷666之外,自己还省了很多事情。 先上效果图...

猜你喜欢

【数据库】关系数据库(Relational Databases)

关系数据库(Relational Databases) 关系数据库,是建立在关系数据库模型基础上的数据库,借助于集合代数等概念和方法来处理数据库中的数据 Relational Query Languages Tuple Relational Calculus (TRC) Relational Algebra (RA) SQL 举例说明: 零、名词概念 1. 基数 和 参数数 cardinality...

zabbix多台监控-proxy分布式监控

zabbix:proxy分布式监控 server3:zabbix-proxy 1、安装 2、开启mysql 3、编写配置文件 4、网页配置添加代理 server1:zabbix-server server2:zabbix-agent...

Collection

Collection 中的方法,全部来自API,读者无需硬性记忆,只需牢记:集合类就像容器,显示生活中容器的功能,也就是添加对象、删除对象、清空容器、判断容器是否为空等,集合类就为这些功能提供了对应的方法。 Collection基本方法: 输出结果: 转自:https://blog.csdn.net/wxc880924/article/details/52639701...

hive on spark部署

1. 环境 Hive-on-MR is deprecated in Hive 2 and may not be available in the future versions. Consider using a different execution engine (i.e. tez, spark) or using Hive 1.X releases. hive默认使用mr作为计算引擎,当进入...

stm32每周学习报告2.0

STM32 通用定时器简介 STM32 的通用定时器是一个通过可编程预分频器(PSC)驱动的 16 位自动装载计数器(CNT) 构成。STM32 的通用定时器可以被用于:测量输入信号的脉冲长度(输入捕获)或者产生输出波 形(输出比较和 PWM)等。 使用定时器预分频器和 RCC 时钟控制器预分频器,脉冲长度和波形 周期可以在几个微秒到几个毫秒间调整。STM32 的每个通用定时器都是完全独立的,没有...