数据结构与算法(5)----->二叉树
2024-09-08 08:15:16
1. 概念
二叉树节点的结构:
class Node{
int value; // value表示二叉树的节点值
Node left;
Node right; // left和right表示二叉树的两个孩子
Node(int data){
this.value = data;
}
}
如图:
2. 二叉数的遍历
2.1 按顺序遍历二叉树
- 先序遍历:中、左、右
- 中序遍历:左、中、右
- 后序遍历:左、右、中
- 以下图二叉树为例:
- 先序遍历结果为: 1 ,2,4,5,3,6,7
- 中序遍历结果为: 4,2,5,1,6,3,7
- 后序遍历结果为: 4,5,2,6,7,3,1
2.2 按层遍历二叉树
- 针对二叉树的宽度优先遍历;
- 宽度优先遍历常使用队列结构;
- (往往要求连同行号一起打印出来!!)
3. 平衡二叉树(AVL树)
概念:
- 空树是平衡二叉树;
- 如果一棵树不为空,并且其中所有的子树都满足各自的左子树与右子树的高度差都不超过1,是平衡二叉树;
- 例如:
- (平衡二叉树)
- (非平衡二叉树)
- 因为,对于上图中,以2为节点的子树,其左子树为2,右子树为0,高度差大于1,我所以不是平衡二叉树;
4. 搜索二叉树
搜索二叉树的特征:
每棵子树的头节点的值都比各自左子树上的所有节点值要大,也要比各自右子树上的所有节点值要小.
- 搜索二叉树按照中序遍历得到的序列,一定是从小到大排列的.
- 其中,红黑树/平衡二叉树(AVL树)等,都是搜索二叉树的不同实现.
5. 满二叉树
概念:满二叉树是除了最后一层节点无任何子节点外,剩下每一层上的节点都有两个子节点.
满二叉树的层数即为L,节点数即为N,则N=2L-1;L=log2(N+1).
5. 完全二叉树
概念:除了最后一层之外,其他每一层的节点数都是满的,最后一层如果也满了,是一颗满二叉树,也是完全二叉树.最后一层如果不满,缺少的节点也全部的集中右边,那也是一颗满二叉树.
如下,都是完全二叉树!!!
最新文章
- Js注释
- BPM 应用系统开发案例实战
- java多线程的常用方法(以及注意事项)
- Learning Puppet — Variables, Conditionals, and Facts
- 【 D3.js 高级系列 — 6.0 】 值域和颜色
- Putty使用公钥认证时,报错:Disconnected: No supported authentication methods available(server sent:public key) 问题的解决
- JComboBox
- Beego学习笔记——开始
- 项目总结一:响应式之CSS3 媒体查询
- EventBus猜想 ----手把手带你自己实现一个EventBus
- js--Dom Bom操作
- jsp页面从标签属性中获取值
- Codeforce A. Quasi-palindrome
- HashSet源码分析
- FFmpeg 常用指令集合
- Tomcat使用https
- 连接postgres特别消耗cpu资源而引发的PostgreSQL性能优化考虑
- C/S,B/S的区别
- EasyNetQ中使用自定义的ISerializer
- C#——LINQ语句
热门文章
- python3.x中xml.etree.ElementTree解析xml举例
- caffe学习--cifar10学习-ubuntu16.04-gtx650tiboost--1g--03--20171103
- 【GoldenGate】使用OGG,两个Oracle库之间单向同步数据
- Centos 7.0系统服务管理
- js 第二篇 (DOM 操作)
- C#多线程学习(六) 互斥对象
- Python中类方法、__new__方法和__init__方法解析
- SSIS
- EasyPlayer Android RTSP播放器延迟再优化策略
- 基于EasyNVR二次开发实现业务需求:直接集成EasyNVR播放页面到自身项目