关于二叉树，你应该知道这个……转载本文请联系CodeCaprice公众号。二叉树理论基础讲二叉树。每个人都熟悉二叉树。在这篇文章中，我不想以教科书的方式重复二叉树的基本内容，所以我会讲一些更重要的内容。相信只要您耐心阅读，一定会有所收获！二叉树的类型在我们求解问题的过程中，二叉树主要有两种形式：满二叉树和完全二叉树。满二叉树满二叉树：如果一棵二叉树只有度数为0的节点和度数为2的节点，且度数为0的节点在同一层，则该二叉树为满二叉树。如图：这棵二叉树是一棵满二叉树，也可以说是一棵深度为k，节点数为2^k-1的二叉树。完全二叉树什么是完全二叉树？完全二叉树的定义如下：在一棵完全二叉树中，除了最底层的节点可能未被填充外，每一层的节点数都达到最大值，并且最底层的节点全部集中在这一层最左边的几个位置。如果最底层是第h层，那么这一层包含1~2^h-1个节点。大家要自己看完全二叉树的定义。很多同学并不是很了解完全二叉树。给大家举个像题目这样的典型例子：最后一棵二叉树，不管是不是完全二叉树，相信很多同学都赢过。前面我们刚刚说过，优先级队列其实是一个堆，堆是一棵完全二叉树，同时保证了父子节点的顺序关系。二叉搜索树前面介绍的树是没有值的，但是二叉搜索树是有值的，二叉搜索树是有序树。如果其左子树不为空，则左子树上所有节点的值都小于其根节点的值；如果其右子树不为空，则右子树上所有节点的值都大于其根节点的值；它的左右子树也是二叉排序树。下面两棵树是搜索树。VelskyandLandis）树，并且具有以下性质：为空树或其左右子树高度差的绝对值不超过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。但是用chain表示的二叉树更利于我们的理解，所以一般我们用存储二叉树的链。所以大家应该明白，二叉树还是可以用数组来表示的。二叉树遍历方法关于二叉树遍历方法，需要了解二叉树遍历的基本方法。有的同学做了很多二叉树的题目。他们可能知道前中后序遍历，可能知道层序遍历，但是他们没有框架。这里我列举了几种二叉树的遍历方法，大家可以一一串起来。二叉树的遍历方式主要有两种：深度优先遍历：先往深处走，遇到叶子节点再往回走。广度优先遍历：逐层遍历。这两种遍历是图论中最基本的两种遍历方法，后面介绍图论的时候再介绍。那么，由深度优先遍历和广度优先遍历进一步扩展，有如下遍历方式：深度优先遍历前序遍历（递归法、迭代法）中序遍历（递归法、迭代法）后序-序遍历（递归法、迭代法）)广度优先遍历层次遍历（迭代法）在深度优先遍历中：有前序、中序、后序三种遍历。这里的前中后其实是指中间节点的遍历顺序，大家只要记住前中后的顺序是指中间节点的位置。看下面中间节点的顺序，可以发现中间节点的顺序就是所谓的遍历法。前序遍历：middle，left，中序遍历：left，middle，right，后序遍历：left-right，middle。大家可以看下图自己看看。是不是前后顺序有问题？最后说一下二叉树中深度优先和广度优先遍历的实现。在二叉树相关的题目中，我们经常使用递归来实现深度优先遍历，即实现前中后序遍历。使用递归更方便。之前讲栈和队列的时候，我们说栈其实是一种递归的实现结构，也就是说前中后序遍历的逻辑其实可以借助于非递归的方式实现的堆栈。广度优先遍历的实现一般使用队列来实现，这也是由先进先出队列的特性决定的，因为遍历二叉树层需要先进先出的结构按层。其实到这里我们就了解了栈和队列的一个应用场景。具体的实现我们后面再说，这里首先要了解这些理论基础。二叉树的定义刚才我们说了二叉树有两种存储方式：顺序存储和链式存储。顺序存储存储在一个数组中。这个定义没什么好说的。我们先看一下链式存储的二叉树节点的定义。方式。C++代码如下：structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(NULL),right(NULL){}};你会发现二叉树的定义类似于链表，和链表相比，二叉树的结点多了一个指针，而且有两个指针，分别指向左右孩子。这里要提醒大家注意二叉树节点定义的写法。现场面试时，面试官可能会要求手写代码，所以数据结构的定义和简单逻辑的代码一定要写在白纸上。因为我们刷leetcode的时候，节点的定义是默认定义的。到了面试的时候，需要我们自己写节点定义的时候，有时候会很迷茫！综上所述，二叉树是一种基本的数据结构，在算法面试中都是常客，是很多数据结构的基石。在本文中，我们介绍了二叉树的类型、存储方式、遍历方式和定义，更全面地介绍了二叉树各个方面的要点，帮助大家扫一扫基础。其他语言版本Java：publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}Go：typeTreeNodestruct{ValintLeft*TreeNodeRight*TreeNode}
