一、什么是二叉树？

image.png

二、二叉树的遍历方法

先序遍历：根—>左—>右
中序遍历：左—>根—>右
后序遍历：左—>右—>根

先根后左逆
例：
二叉树学习笔记 - 图2
image.png
代码实现先序遍历：

  2.     /**
  3.      * 先序遍历
  4.      * @param rootTreeNode  根节点
  5.      */
  6.     public static void preTraverseBTree(TreeNode rootTreeNode) {
  7.         //如果中序或后序遍历只需要改变下面代码的顺序就好了
  8.         if (rootTreeNode != null) {
  10.             //访问根节点
  11.             System.out.println(rootTreeNode.getValue());
  13.             //访问左节点
  14.             preTraverseBTree(rootTreeNode.getLefTreeNode());
  16.             //访问右节点
  17.             preTraverseBTree(rootTreeNode.getRightNode());
  18.         }
  19.     }

注意：
通过先序和中序或者中序和后序我们可以还原出原始的二叉树，但是通过先序和后续是无法还原出原始的二叉树的，即必须知道中序遍历的结果才能还原二叉树；

三、二叉查找树

定义：当前根节点的左边全部比根节点小，当前根节点的右边全部比根节点大。
优点：明眼人可以看出，这对我们来找一个数是非常方便快捷的
往往我们动态创建二叉树都是创建二叉查找树
二叉树学习笔记 - 图4
动态创建二叉树代码实现：
TreeRoot.java表示根节点

  1. public class TreeRoot {
  3.     private TreeNode treeRoot;
  5.     public TreeNode getTreeRoot() {
  6.         return treeRoot;
  7.     }
  9.     public void setTreeRoot(TreeNode treeRoot) {
  10.         this.treeRoot = treeRoot;
  11.     }
  12. }

比较与根谁大，大的往右边，小的往左边：

  3.   /**
  4.      * 动态创建二叉查找树
  5.      *
  6.      * @param treeRoot 根节点
  7.      * @param value    节点的值
  8.      */
  9.     public static void createTree(TreeRoot treeRoot, int value) {
  12.         //如果树根为空(第一次访问)，将第一个值作为根节点
  13.         if (treeRoot.getTreeRoot() == null) {
  14.             TreeNode treeNode = new TreeNode(value);
  15.             treeRoot.setTreeRoot(treeNode);
  17.         } else  {
  19.             //当前树根
  20.             TreeNode tempRoot = treeRoot.getTreeRoot();
  22.             while (tempRoot != null) {
  23.                 //当前值大于根值，往右边走
  24.                 if (value > tempRoot.getValue()) {
  26.                     //右边没有树根，那就直接插入
  27.                     if (tempRoot.getRightNode() == null) {
  28.                         tempRoot.setRightNode(new TreeNode(value));
  29.                         return ;
  30.                     } else {
  31.                         //如果右边有树根，到右边的树根去
  32.                         tempRoot = tempRoot.getRightNode();
  33.                     }
  34.                 } else {
  35.                     //左没有树根，那就直接插入
  36.                     if (tempRoot.getLefTreeNode() == null) {
  37.                         tempRoot.setLefTreeNode(new TreeNode(value));
  39.                         return;
  40.                     } else {
  41.                         //如果左有树根，到左边的树根去
  42.                         tempRoot = tempRoot.getLefTreeNode();
  43.                     }
  44.                 }
  45.             }
  46.         }
  47.     }

测试代码：

  2.     int[] arrays = {2, 3, 1, 4, 5};
  4.     //动态创建树
  6.     TreeRoot root = new TreeRoot();
  7.     for (int value : arrays) {
  8.         createTree(root, value);
  9.     }
  11.     //先序遍历树
  12.     preTraverseBTree(root.getTreeRoot());
  13.     System.out.println("---------------");
  15.     //中序遍历树
  16.     inTraverseBTree(root.getTreeRoot());
  17.     System.out.println("---------------");

测试结果：
image.png


本文参考于：https://juejin.im/post/6844903582202855438#heading-5