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

二叉树图解(定义特征及模型分类)-mikechen的互联网架构

二叉树定义

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

 

二叉树形态

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

1)本身是有序树;

2)树中包含的各个节点的度不能超过 2,即只能是 0、1 或者 2;

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

二叉树图解(定义特征及模型分类)-mikechen的互联网架构

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

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

二叉树图解(定义特征及模型分类)-mikechen的互联网架构

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

 

二叉树特征

二叉树图解(定义特征及模型分类)-mikechen的互联网架构

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

 

二叉树分类

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

1.满二叉树

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

二叉树图解(定义特征及模型分类)-mikechen的互联网架构

 

2.完全二叉树

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

二叉树图解(定义特征及模型分类)-mikechen的互联网架构

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

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

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

 

 

二叉树遍历

二叉树图解(定义特征及模型分类)-mikechen的互联网架构

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

1.先序遍历

二叉树图解(定义特征及模型分类)-mikechen的互联网架构

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

2.中序遍历

二叉树图解(定义特征及模型分类)-mikechen的互联网架构

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

3.后序遍历

二叉树图解(定义特征及模型分类)-mikechen的互联网架构

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

以上!

关注「mikechen的互联网架构」公众号,第一时间获知最新架构技术干货!

在公众号菜单栏对话框回复【合集】,即可获取mikechen原创《阿里架构师进阶从0到1全部合集》,助力大家2023高薪进阶。

评论交流
    说说你的看法