数据结构之 二叉树
发布日期:2021-08-25 00:32:37 浏览次数:8 分类:技术文章

本文共 1409 字,大约阅读时间需要 4 分钟。

对象由指针所构成的关系有很多种,如果没有循环可以广义称为树,否则称为图。

而二叉树是一种特殊的树形结构。常用与二叉树排序的应用。
二叉树的定义:  每个结点最多有两个子树的结构称为二叉树。所以两个分叉可以分别称为左子树和右子树
根节点:每棵树中只有1个根节点
中间节点:有一个或两个孩子
叶子节点:没有子节点的节点
 
 
前序遍历(先根序遍历):原理 根——>左——>右  先访问根节点,再访问左子树,在访问右子树
中序遍历:                        原理 左——>根——>右  先访问左子树,再访问根节点,在访问右子树
后序:                               原理 左——>右——>根  先访问左子树,再访问右子树,在访问根节点
那么上图的前序遍历 :ABCDEFGHK        中序遍历:BDCAEHGKF 这里后序就不写了
重点举例:中须遍历 
1、先访问左子树 所以先排序 BCD。
2、在BCD中 B节点为根节点 而不存在子节点 所以第一个就是B,而B的子节点是一棵树,所以在此暂时不对C进行排序
3、当前C节点下有一个左叶子节点,按照(左根右)的排序规则,就应该是DC 那么联合B 目前的排序就是BDC
4、在中序遍历中 先访问左子树 --->根节点----->右子树的规则,第四个就是根节点A   目前BDCA
5、剩下EFGHK 这个节点组成的右子树,第一个E根节点下只有右节点而右节点是一颗树,所以只能排E这个节点  BDCAE
6、F节点是棵树,而G作为F节点的左子节点也是颗树 无法排序,继续往下,H左叶子节点 OK就是它了  HGK 这个树就排好了
7、剩下F 因为F作为根节点 排完左子树后就排根节点,所以现在就是F  HGKF 该节点没有右子树,所以将之前排序的合并 就是上面写的 BDCAEHGKF
 
以下通过java 实现二叉树排序
/** * 二叉树的遍历 * 12 9 5 8 11 20  通过二叉树排序  增加一个规则如果加入的节点比本身节点小,那么放在左边否则放在右边 * 第一步 将 12 作为根节点  * 第二步 由于 9<12 所以9作为根节点的左叶子节点 * 第三步 5<12 放左边但左边已经有了一个左叶子节点 所以应该放 在9这个节点的下方作为左节点、 * 同理后面也依次排序,最后二叉树如下: *           12 *          /    \ *         9      20 *       /   \  *      5     11 *       \ *        8     * @author Administrator * 在java 中 treeMap 就是实现二叉树而提供的集合。 * 博客地址:二叉树的理解   */public class Binary {    private int data;    private Binary left;        private Binary right;    public  Binary(int i) {        data=i;    }    public void add(Binary binary) {        //根据之前的逻辑 就应该是将 当前传入的这个节点将本节点进行比较        if(binary.data

 

 

转载于:https://www.cnblogs.com/lanSeGeDiao/p/9142163.html

转载地址:https://blog.csdn.net/weixin_33836223/article/details/94454625 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:简单远程遥控程序【网络程序设计 - 简单远程遥控程序,C实现】
下一篇:StringBuffer类常用方法

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年03月05日 13时40分23秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

linux 条件判断 取非_Linux awk 系列文章之 awk 多重条件判断 2019-04-21
c语言中如何将字符串的元素一个一个取出_C语言中常用的字符串操作函数 2019-04-21
2d游戏地图编辑器_王者荣耀:新版本爆料!地图编辑器“天工”即将开测,游戏怎么玩由你定!... 2019-04-21
.net framework服务启动后停止_dos命令net图文教程,start启动系统服务stop停止服务批处理脚本... 2019-04-21
8k分辨率需要多大带宽_超乎想象!用RTX3080显卡连索尼8K电视玩游戏感受如何?... 2019-04-21
win10怎么开启aptx_Win10未来的黑科技?微软SurfaceFleet大曝光 2019-04-21
creo视图管理器使用方法_学以致用之中望3D—浅谈使用中望3D的初步感受 2019-04-21
周育如的音标口诀大全_花鸟画口诀大全,实用! 2019-04-21
心电图计算心率公式_医学常用的计算公式口诀(内外妇儿),赶快收藏! 2019-04-21
select 移动端 第一个无法选中_Python爬虫微博(移动端)评论 2019-04-21
华为云welink成像是反的_华为发布智能办公神器WeLink,可连接会议室开会,还可一键遥控报销和智能翻译... 2019-04-21
唱好铁血丹心谐音正规_趙贤典:打好“感情牌” 唱好“大合唱” 2019-04-21
aix系统vi修改命令_Linux基础知识必备:利用vi编辑器创建和编辑正文文件 2019-04-21
天涯明月刀开发_玩家被天涯明月刀手游“冷落”?六大门派角色竟不带正眼看人... 2019-04-21
this指向undefined uiapp_一个this都没有,真好 2019-04-21
add p4 多个文件_2-3【微信小程序全栈开发课程】index页面完善--vue文件代码解析... 2019-04-21
5w2h原则指的是什么_什么是5W2H分析法?一首小诗带入进入大门。 2019-04-21
技校毕业是什么学历_中等职业学校是什么_中等职业学校毕业是什么学历 2019-04-21
2压缩备份数据库_MySQL数据备份与恢复(二) xtrabackup工具 2019-04-21
英特尔cpu发布时间表_被嘲讽的英特尔核显,强大能力其实超乎你的想象 2019-04-21