二叉树理论介绍

二叉树的种类

• 满二叉树
  
• 完全二叉树
  

满二叉树

满二叉树：假如一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。


这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。
完全二叉树

什么是完全二叉树？
完全二叉树的界说如下：在完全二叉树中，除了最底层节点大概没填满外，别的每层节点数都到达最大值，并且最下面一层的节点都会合在该层最左边的多少位置。若最底层为第 h 层，则该层包含 1~ 2^h -1  个节点。
各人要本身看完全二叉树的界说，很多同砚对完全二叉树着实不是真正的懂了。
我来举一个典型的例子如题：


信赖不少同砚末了一个二叉树是不是完全二叉树都中招了。
之前我们刚刚讲过优先级队列着实是一个堆，堆就是一棵完全二叉树，同时包管父子节点的次序关系。
二叉搜刮树

前面介绍的树，都没有数值的，而二叉搜刮树是有数值的了，二叉搜刮树是一个有序树。

• 若它的左子树不空，则左子树上全部结点的值均小于它的根结点的值；
  
• 若它的右子树不空，则右子树上全部结点的值均大于它的根结点的值；
  
• 它的左、右子树也分别为二叉排序树
  

下面这两棵树都是搜刮树

平衡二叉搜刮树

平衡二叉搜刮树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性子：它是一棵空树或它的左右两个子树的高度差的绝对值不凌驾1，并且左右两个子树都是一棵平衡二叉树。
如图：
末了一棵 不是平衡二叉树，由于它的左右两个子树的高度差的绝对值凌驾了1。
C++中map、set、multimap，multiset的底层实现都是平衡二叉搜刮树，以是map、set的增删操纵时间时间复杂度是logn，注意我这里没有说unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表。
以是各人使用本身认识的编程语言写算法，肯定要知道常用的容器底层都是怎样实现的，最根本的就是map、set等等，否则本身写的代码，本身对其性能分析都分析不清晰！
二叉树的存储方式

二叉树可以链式存储，也可以次序存储。
那么链式存储方式就用指针， 次序存储的方式就是用数组。
顾名思义就是次序存储的元素在内存是一连分布的，而链式存储则是通过指针把分布在散落在各个地点的节点串联一起。
链式存储如图：

链式存储是各人很认识的一种方式，那么我们来看看怎样次序存储呢？
着实就是用数组来存储二叉树，次序存储的方式如图：

用数组来存储二叉树怎样遍历的呢？
假如父节点的数组下表是i，那么它的左孩子就是i * 2 + 1，右孩子就是 i * 2 + 2。
但是用链式表现的二叉树，更有利于我们明确，以是一样平常我们都是用链式存储二叉树。
以是各人要了解，用数组依然可以表现二叉树。
二叉树的遍历方式

关于二叉树的遍历方式，要知道二叉树遍历的根本方式都有哪些。
一些同砚用做了很多二叉树的标题了，大概知道前中后序遍历，大概知道层序遍历，但是却没有框架。
我这里把二叉树的几种遍历方式列出来，各人就可以逐一串起来了。
二叉树主要有两种遍历方式：

• 深度优先遍历：先往深走，碰到叶子节点再往回走。（可以明确为栈，使用递归）
  
• 广度优先遍历：一层一层的去遍历。（队列）
  

这两种遍历是图论中最根本的两种遍历方式，反面在介绍图论的时间 还会介绍到。
那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

• 深度优先遍历
  
  
  
  • 前序遍历（递归法，迭代法）
    
  • 中序遍历（递归法，迭代法）
    
  • 后序遍历（递归法，迭代法）
    
  
  
• 广度优先遍历
  
  
  
  • 层次遍历（迭代法）
    
  
  

在深度优先遍历中：有三个次序，前中后序遍历， 有同砚总分不清这三个次序，常常搞混，我这里教各人一个本事。
这里前中后，着实指的就是中心节点的遍历次序，只要各人记着 前中后序指的就是中心节点的位置就可以了。
看如下中心节点的次序，就可以发现，中心节点的次序就是所谓的遍历方式

• 前序遍历：中左右
  
• 中序遍历：左中右
  
• 后序遍历：左右中
  各人可以对着如下图，看看本身明确的前后中序有没有问题。
  
  
  末了再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相干标题，常常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比力方便的。
  

之前我们讲栈与队列的时间，就说过栈着实就是递归的一种是实现结构，也就说前中后序遍历的逻辑着实都是可以借助栈使用非递归的方式来实现的。
而广度优先遍历的实现一样平常使用队列来实现，这也是队列先辈先出的特点所决定的，由于必要先辈先出的结构，才气一层一层的来遍历二叉树。
这里着实我们又了解了栈与队列的一个应用场景了。
具体的实现我们反面都会讲的，这里各人先要清晰这些理论根本。
二叉树的界说

刚刚我们说过了二叉树有两种存储方式次序存储，和链式存储，次序存储就是用数组来存，这个界说没啥可说的，我们来看看链式存储的二叉树节点的界说方式。
C++代码如下：