二叉树图解(定义特征及模型分类)

二叉树定义

二叉树作为一种重要的树形结构类型，通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

 

二叉树形态

满足以下两个条件的树就是二叉树：

1）本身是有序树；

2）树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

下图中这棵树，就是一颗典型的二叉查找树：

各个节点都没有超过2，这就是典型的二叉树。

比如：下面这棵树，多出来的红色节点，节点已经是3了，超过最多2个节点了，这就不属于二叉树了。

二叉树的意思就是说：每个节点不能多于有两个儿子。

 

二叉树特征

1. 一棵树至少会有一个节点(根节点)；
2. 树由节点组成，每个节点的数据结构是这样的：一个数据、两个指针(如果有节点就指向节点、没有节点就指向null)；
3. 二叉树中，第 i 层最多有 2^( i-1)个结点；
4. 如果二叉树的深度为 K，那么此二叉树最多有 2^K-1 个结点；

 

二叉树分类

二叉树还可以继续分类，衍生出满二叉树和完全二叉树。

1.满二叉树

棵树高度为h，高度为h，由2^h-1个节点构成的二叉树，就称为满二叉树，如下图所示：

 

2.完全二叉树

完全二叉树是由满二叉树而引出来的，如下图所示：

3.完全二叉树与满二叉树的区别

完全二叉树除最后一层，其它层都是满结点的，这就是完全二叉树与满二叉树的区别所在。

满二叉树最后一层都是满节点的，而完全二叉树不是。

 

 

二叉树遍历

二叉树遍历：主要分为先序遍历、中序遍历、后序遍历。

1.先序遍历

• 首先：访问根结点；
• 然后：前序遍历其左子树；
• 最后：前序遍历其右子树。

2.中序遍历

• 首先：中序遍历左子树；
• 然后：访问根节点；
• 最后：中序遍历右子树。

3.后序遍历

• 首先：后序遍历左子树;
• 然后：后序遍历右子树
• 最后：访问根节点。

作者简介

陈睿|mikechen，10年+大厂架构经验，BAT资深面试官，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

👇阅读更多mikechen架构文章👇

阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师

以上

关注作者「mikechen」公众号，获取更多技术干货！

后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》