二叉树

一级目录

二级目录

三级目录

1.树的介绍

1.1树的定义

​ 树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。

把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点:

1. 每个节点有零个或多个子节点
2. 没有父节点的节点称为根节点
3. 每一个非根节点有且仅有一个父节点
4. 除了根节点之外，每个子节点可以分为多个不相交的子树

1.2树的基本术语

​ 若一个节点有子树，那么该节点称为子树根节点的“双亲“，子树的跟是该节点的“孩子”。有相同双亲的节点互为“兄弟节点”。一个节点的所有子树上的任何节点都是该节点的后裔。从根节点到某个节点的路径上的所有节点都是该节点的祖先。

• 节点的度：节点拥有的子树的数目。

• 叶子：度为零的节点

• 分支节点：度不为零的节点

• 树的度：树中节点最大的度

• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点

• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点

• 兄弟节点：具有相同父节点的节点互称为兄弟节点

• 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

• 层次：根节点的层次为1，其余节点的层次等于该节点的双亲节点加一

• 树的高度：树中节点的最大层次

• 无序树：如果树中节点的各子树的次序是不重要的，可以交换位置

• 有序树：如果树中结点的各子树的次序是重要的，不可以交换位置

• 森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林

1.3相关性质

• 树的节点数 = 所有节点度数+1
• 度为m的树第i层最多有m^(i-1)个节点
• 高度为h的m叉树最多（m^h -1/(m-1)) 个节点（等比数列求和)
• n个节点的m叉树最小高度 logm （n(m-1)+1)]

2.二叉树介绍

2.1定义

​ 二叉树是每个节点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；活着左、右子树皆为空。【以go语言和Java为例】

/*------go------*/
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

/*------Java------*/
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

2.2 性质

• 二叉树第i层上的节点数目最多为 2{i-1} (i≥1)
• 深度为k的二叉树至多有2{k}-1个节点（k>=1）
• 包含n个节点的二叉树的高度至少为log2 (n+1)
• 在任意一颗二叉树中，若终端节点的个数为n0，度为2的节点数为n2，则n0=n2+1

3.二叉树的种类

3.1 满二叉树

高度为h，并且由2{h} –1个结点的二叉树，被称为满二叉树。

3.2完全二叉树

​ 一棵二叉树中，只有最下面两层节点的度可以小于2，并且最下层的叶节点集中在靠左的若干位置上。

​ 叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。显然，一颗满二叉树必定是一颗完全二叉树，而完全而二叉树不一定是满二叉树。

3.3 二叉查找树

​ 二叉查找树（Binary Search Tree）,又被称为二叉搜索树。设x为二叉树中的一个节点，x节点包含关键字Key，节点x的Key值记为Key[x]。如果y是x的左子树中的一个节点，则Key[y]<=Key[x]；如果y是x的有子树的一个节点，则Key[y]>=Key[x]。

特点：

• 若任意节点的左子树不空，则左子树上所有的值均小于根节点的值
• 若任意节点的右子树不空，则右子树上所有节点的值均大于根节点的值（更大于左子树上的值）
• 任意节点的左、右子树也分别为二叉查找树
• 没有键值相等的节点

二叉查找树的节点包含的基本信息：

• key——关键值，是用来对二叉查找树的节点进行排序的
• left——指向当前节点的左孩子
• right——指向当前孩子的右节点
• parent——指向当前节点的父节点

3.4 平衡二叉树

​ 平衡二叉树搜索树：又被称为AVL(Adelson-Velsky and Landis)树，且具有以下性质：它是一颗空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。如图：

4.二叉树的遍历方式

二叉树主要有两种遍历方式，深度优先遍历和广度优先遍历

4.1深度优先遍历

深度优先遍历：先往深走，遇到叶子节点再往回走

• 前序遍历（递归法，迭代法）
• 中序遍历（递归法，迭代法）
• 后序遍历（递归法，迭代法）

这里的前中后三种顺序的遍历其实讲的就是中间节点的遍历顺序，例如前序遍历就是先遍历中间节点，再遍历该中间节点的左右两个子节点，同样的中序遍历说的就是先遍历左孩子在遍历中间节点，最后是右孩子。我们可以尝试一下力扣的三道题以便更好地理解这三种遍历方式：

• https://leetcode.cn/problems/binary-tree-preorder-traversal/
• https://leetcode.cn/problems/binary-tree-inorder-traversal/
• https://leetcode.cn/problems/binary-tree-postorder-traversal/

4.2广度优先遍历

• 广度优先遍历：一层一层的去遍历
  • 层次遍历（迭代法）