主要记录一下对于二叉树，进行遍历的几种方式，包括：

• 前序遍历
• 中序遍历
• 后序遍历
• 深度优先遍历
• 广度优先遍历

我们以下面的这个二叉树结构为例，分别描述一下这几种遍历的方式有什么不同，以及给出java实现的代码。

基于《算法》一书的红黑树的插入和删除。看过不同的教材，也有不同的实现方式，但是最终的结果也大致相同，感觉这个比较容易理解，就采用这种的方式来进行简单实现。

定义树节点的实体类型

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

private static final boolean RED = true;
private static final boolean BLACK = false;

/**
	 * 红黑树的节点结构
	 * 保存的值，左节点，右节点以及颜色(true为红色，false为黑色)
	 * 默认添加一个红节点
	 *
	 * @param <E>
	 */
static final class RedBlackTreeNode<E extends Comparable<E>> {

  E val;
  RedBlackTreeNode<E> left;
  RedBlackTreeNode<E> right;
  boolean color = RED;


  RedBlackTreeNode(E val) {
    this.val = val;
  }

}

这里简单的定义了一下红黑树，并且只有节点，并不是map这样的k-v结构。如果定义k-v结构到时比较的时候比较k即可。

用了泛型，并且要支持比较(继承自Comparable)，不然无法比较大小进行插入。

然后定义了一个值，左节点和右节点，然后颜色默认为红色。

再增加一个构造函数即可

题目来源

今天做了个题：

将一个链表里的数据组装树形结构，链表里的数据已经满足树形结构要求

这道题描述的很简单，但是有很多种情况。他只说了链表数据满足树形结构要求，并没有说明数据到底是什么样的，也就是题目参数具有多样性，这样其实我们给出一种解决方案就可以。而且也只要求将链表转换为树，并没有说是什么树。所以这道题说难也难，说简单也简单。

解题思路

最近也将平衡二叉树的原理看了一下，正好借着这道题将代码手写一下。

我写了一个平衡二叉树的插入方法。我们不管链表里面的数据是如何排序的，我们只要调用树的插入方法即可。在插入方法内部实现树的平衡。

所以我们这道题也就转换成了手写平衡二叉树的插入过程。

二叉树

定义

• 二叉树由节点的有限集合构成
• 这个有限集合或者为空集
• 或者为由一个根节点(root)及两棵互不相交、分别称为这个根的左子树和右子树的二叉树组成的集合

在 java 中用代码定义为：

1
2
3
4
5
6
7
8

class TreeNode {
    Object val;
    TreeNode leftNode;
    TreeNode rightNode;
    
    ...
        
}

性质

1. 在二叉树中，第 i 层上最多有2^i^ 个节点(i>=0)
2. 深度为 k 的二叉树至多有2^k+1^-1个节点(k>=0)
3. 有 n 个节点的完全二叉树的高度为 log2(n+1)

它主要有五种基本形态：

满二叉树

定义：除最后一层无任何子节点外，每一层上的所有节点都有两个子节点的二叉树。

大体的意思就是：一颗二叉树的节点要么是叶子节点（也就是最后一层），要么它就要有两个子节点。如果这个二叉树的层数为 k，且节点总数是(2^k^-1)，则它就是满二叉树。

完全二叉树

定义：设二叉树的深度为 k，除第 k 层外，其他各层(1~(k-1)层)的节点都都达到最大值，其第 k 层所有的节点都连续集中在最左边，这样的树就是完全二叉树

这些是二叉树的一些基本定义以及变形，它对于数据的存储并没有要求，只是要求了结构。所以对于实际应用中还存在很多的不足，比如对于一个 n 个节点的树，判断一个节点是不是在树里面，它的复杂度还是 o(n)。所以我们下面介绍几种对于存储有要求的树。