二叉树介绍及其前中后遍历实现

数据结构和算法►二叉树 , , 评论

本文示例代码已上传 github，可直接点击查看

前言

前一阵子在学习 HashMap 的时候，知道了在 java8 之后的 HashMap 使用数组+链表+红黑树的结构来实现，看代码的时候百思不得其解。

因此想要学一下”树”这个数据结构，为学习红黑树打下基础，同时，二叉树的一些相关算法也是面试过程中的常问题目，提前学习以备不时之需。

本文主要写一些二叉树通用的操作，如遍历，求高度等，添加及删除节点等操作依赖于具体的二叉树实现，如排序二叉树和完全二叉树等的插入方式不同，这里不做实现，在后续文章中具体实现。

二叉树是什么？（摘自维基百科和百度百科）

1. 定义

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

2. 性质

  1. 在非空二叉树中，第 i 层的结点总数不超过 , i>=1；
  2. 深度为 h 的二叉树最多有 个结点 (h>=1)，最少有 h 个结点；
  3. 对于任意一棵二叉树，如果其叶结点数为 N0，而度数为 2 的结点总数为 N2，则 N0=N2+1；
  4. 具有 n 个结点的完全二叉树的深度为 （注：[ ] 表示向下取整）
  5. 有 N 个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
    若 I 为结点编号则 如果 I>1，则其父结点的编号为 I/2；
    如果 2I<=N，则其左孩子（即左子树的根结点）的编号为 2*I；若 2*I>N，则无左孩子；
    如果 2    I+1<=N，则其右孩子的结点编号为 2*I+1；若 2*I+1>N，则无右孩子。
  6. 给定 N 个节点，能构成 h(N) 种不同的二叉树。
    h(N) 为卡特兰数的第 N 项。h(n)=C(2*n，n)/(n+1)。
  7. 设有 i 个枝点，I 为所有枝点的道路长度总和，J 为叶的道路长度总和 J=I+2i

3. 类型

  • 满二叉树
  • 完全二叉树
  • 平衡二叉树
  • 排序二叉树
  • 红黑树
  • 哈弗曼树

对各种二叉树的性质不再具体介绍，有兴趣可以自行百度。

Java 实现

基本数据结构的实现

首先定义节点类，保存当前节点数据以及左右孩子信息。

1
2
3
4
5
6
7
8
class Node{
  //节点保存的值，这里使用 int
  int val;
  //左孩子
  Node left;
  //右孩子
  Node right;
}

二叉树的类下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class BinaryTree {

  //根节点
  private Node root = null;

  //构造方法
  public BinaryTree() {
    this.root = new Node(1, new Node(2, new Node(4, null, null), new Node(5, null, null)),
        new Node(3, null, new Node(6, null, null)));
  }

  class Node {

    int val;
    //左孩子
    Node left;
    //右孩子
    Node right;

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

    @Override
    public String toString() {
      return String.valueOf(val);
    }
  }

}

在图中的构造方法中，我用粗暴的方式构造了一个形如下图的二叉树，方便后续的测试。

二叉树的操作实现

遍历实现

二叉树的遍历可以说是面试过程中的重难点了，初，中甚至高级工程师的面试中都有可能碰到，而且大部分是让你白板编程写遍历算法，所以这一块一定要理解原理并加上多多实践。

二叉树的遍历思路有两种，深度遍历和广度遍历，其中深度遍历又分为前序，中序，后续三种，下面将对这几种逐个实现。

1. 前序遍历的递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 前序遍历（递归）： 1、访问这个节点 2、调用自身来遍历节点的左子树 3、调用自身来遍历节点的右子树
 */
public List<Integer> preOrderTraversal() {
  List<Integer> result = new ArrayList<>();
  preOrder(root, result);
  return result;

}

private void preOrder(Node root, List<Integer> result) {
  if (null == root) {
    return;
  }
  result.add(root.val);
  preOrder(root.left, result);
  preOrder(root.right, result);
}

二叉树的定义本身就是一个递归的过程，二叉树的根节点的左右孩子又分别是二叉树，所以在遍历的过程中，使用递归的思想十分简单。

首先访问当前节点，如果当前节点为空则返回，不为空则将当前节点的值放入结果列表，然后调用自身遍历自己的左孩子和右孩子。

2. 前序遍历的非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 非递归先序遍历二叉树
 * */
private List<Integer> prerderTraversal2() {
  List<Integer> resultList=new ArrayList<>();
  Stack<Node> treeStack=new Stack<>();
  if(root==null) //如果为空树则返回
    return resultList;
  treeStack.push(root);
  while(!treeStack.isEmpty()){
    Node tempNode=treeStack.pop();
    if(tempNode!=null){
      resultList.add(tempNode.val);//访问根节点
      treeStack.push(tempNode.right); //入栈右孩子
      treeStack.push(tempNode.left);//入栈左孩子
    }
  }
  return resultList;
}

————————-这一块写的很繁琐，理解了的同学可以不用看了直接跳过————————

在非递归的前序遍历中我们借助了栈，这块刚开始有些难理解，我们来一步一步试一下：
以上面图中的二叉树为例：

  1. 根节点也就是 1 入栈。此时栈从底到顶为：1，结果列表为空。
  2. 栈不为空，进入 while 循环，将 1 出栈并且添加到结果中，然后入栈 1 的右孩子，左孩子。此时栈从底到顶为：3，2，结果列表为 1。
  3. 栈不为空，进入 while 循环，将 2 出栈并且添加到结果中，然后将入栈 2 的右孩子，左孩子。此时栈从底到顶为：3，5，4，结果列表为 1，2。
  4. 栈不为空，进入 while 循环，将 4 出栈并加入结果中，然后将 4 的右孩子左孩子入栈（皆为空）。此时栈从底到顶为：3，5，结果列表为 1，2，4。
  5. 栈不为空，进入 while 循环，将 5 出栈并加入结果，然后将 5 的右孩子，左孩子入栈（皆为空）。此时栈从底到顶为：3，结果列表为 1，2，4，5。
  6. 栈不为空，进入 while 循环，将 3 出栈并加入结果，将 3 的右孩子 (6)，左孩子（空）入栈。此时栈从底到顶为：6，结果列表为 1，2，4，5，3。
  7. 栈不为空，进入 while 循环，将 6 出栈并加入结果，然后将右孩子左孩子入栈（皆为空）。此时栈从底到顶为：空，结果列表为 1，2，4，5，3，6。
  8. 栈为空，结束循环返回结果。

——————-繁琐结束分割线—————————-

以上两种遍历方式返回的结果都为：1,2,4,5,3,6.

3. 中序遍历的递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 递归实现中序遍历
 */
private List<Integer> inrderTraversal() {
  List<Integer> result = new ArrayList<>();
  inOrder(root, result);
  return result;
}

private void inOrder(Node root, List<Integer> result) {
  if (null == root) {
    return;
  }
  inOrder(root.left, result);
  result.add(root.val);
  inOrder(root.right, result);
}

这个的实现思路和递归实现前序遍历很相似，这里不再赘述。

4. 中序遍历的非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 非递归实现中序遍历
 */
private List<Integer> inOrderTraversal2() {
  List<Integer> list = new ArrayList<>();

  Stack<Node> stack = new Stack<>();
  Node cur = root;

  while(cur!=null || !stack.empty()){
    while(cur!=null){
      stack.add(cur);
      cur = cur.left;
    }
    cur = stack.pop();
    list.add(cur.val);
    cur = cur.right;
  }
  return list;
}

非递归实现的中序遍历思想：首先找到二叉树最左下角的节点，即从根节点一直沿着左孩子向前走，直到某一节点没有左孩子，然后将该节点添加到结果列表，继续以相同的思路遍历该节点的右孩子。之后会退一个节点，执行相同的操作，由于二叉树的实现中，节点并不保存父节点的信息，所以也需要借助栈来保存回退的信息。

具体的思路不再讲解，如果不很理解可以照着代码写一遍前序遍历中那种繁琐的流程就懂了。

以上中序遍历的结果为：4,2,5,1,3,6.

5. 后序遍历的递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * 递归实现后序遍历
 */
private List<Integer> postOrderTraversal() {
  List<Integer> result = new ArrayList<>();
  postOrder(root, result);
  return result;
}

private void postOrder(Node root, List<Integer> result) {
  if (null == root) {
    return;
  }
  postOrder(root.left, result);
  postOrder(root.right, result);
  result.add(root.val);
}

原理与前面类似且十分简单，看代码即可。

6. 后序遍历的非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 非递归实现后序遍历
 */
private List<Integer> postOrderTraversal2() {
  Stack<Node> stack = new Stack<>();
  stack.push(root);
  List<Integer> resultList = new ArrayList<>();
  while (!stack.isEmpty()) {
    Node node = stack.pop();
    if (node != null) {
      resultList.add(node.val);
      stack.push(node.left);
      stack.push(node.right);
    }
  }
  Collections.reverse(resultList);
  return resultList;
}

其实后续遍历的实现有许多种，我自己也写了一种十分麻烦但是实现了功能的方法，但是后来在网上看到了这种取巧的办法，还是觉得应该写上这个方法，毕竟我们不是为了学习茴字的四种写法，而是为了学习一种足够好的方法去解决问题。

这种方法的思路是利用非递归实现的前序遍历，在前序遍历中，是根-左-右，那么我们将其稍微改一下，变成根-右-左，这样拿到结果之后翻转一下列表，就可以拿到后续遍历啦。

6. 层次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 层次遍历
 */
private List<Integer> levelIterator() {
  List<Integer> resultList = new ArrayList<>();
  if (root == null) {
    return resultList;
  }
  LinkedList<Node> queue = new LinkedList<Node>();
  Node current = null;
  queue.offer(root);//将根节点入队
  while (!queue.isEmpty()) {
      current = queue.poll();//出队队头元素并访问
    if (current != null) {
      resultList.add(current.val);
      queue.offer(current.left);
      queue.offer(current.right);
    }
  }
  return resultList;
}

层次遍历比较简单，借助了队列来实现，首先将根节点入队，然后从队首获取元素添加到结果中，并将其左孩子，右孩子依次入队，直到队列为空即可。

参考链接

https://www.jianshu.com/p/0190985635eb
https://blog.csdn.net/Double2hao/article/details/53286038


完。

ChangeLog

2018-11-04 完成

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十

呼延十Developer

个人简介。