1、二叉树

树有很多种，每个结点最多只能有两个子结点的成为二叉树，二叉树的结点分为左结点和右结点。

二叉树遍历：
1、前序遍历：从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。
2、中序遍历：从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。
3、后序遍历：从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。
4、层序遍历：层次遍历就是按照树的层次自上而下的遍历二叉树**

  1. /**
  2.  *  二叉树遍历：
  3.  */
  4. public class BinaryTree {
  6.     /**
  7.      * 根结点
  8.      */
  9.     private TreeNode rootNode;
  11.     /**
  12.      * 结点类
  13.      */
  14.     private class TreeNode {
  15.         private String name;
  16.         private TreeNode left;
  17.         private TreeNode right;
  19.         public TreeNode(String name, TreeNode left, TreeNode right) {
  20.             this.name = name;
  21.             this.left = left;
  22.             this.right = right;
  23.         }
  25.         /**
  26.          * 前序遍历
  27.          */
  28.         public void beforeOrder() {
  29.             if (this == null) {
  30.                 return;
  31.             }
  32.             // 1、输出结点
  33.             System.out.printf("%s ", this.name);
  34.             // 2、前序遍历左子树
  35.             if (this.left != null) {
  36.                 this.left.beforeOrder();
  37.             }
  38.             // 3、前序遍历右子树
  39.             if (this.right != null) {
  40.                 this.right.beforeOrder();
  41.             }
  42.         }
  44.         /**
  45.          * 中序遍历
  46.          */
  47.         public void middleOrder() {
  48.             if (this == null) {
  49.                 return;
  50.             }
  51.             // 1、中序遍历左子树
  52.             if (this.left != null) {
  53.                 this.left.middleOrder();
  54.             }
  55.             // 2、输出结点
  56.             System.out.printf("%s ", this.name);
  57.             // 3、中序遍历右子树
  58.             if (this.right != null) {
  59.                 this.right.middleOrder();
  60.             }
  61.         }
  63.         /**
  64.          * 后序遍历
  65.          */
  66.         public void afterOrder() {
  67.             if (this == null) {
  68.                 return;
  69.             }
  70.             // 1、后序遍历左子树
  71.             if (this.left != null) {
  72.                 this.left.afterOrder();
  73.             }
  74.             // 2、后序遍历右子树
  75.             if (this.right != null) {
  76.                 this.right.afterOrder();
  77.             }
  78.             // 3、输出结点
  79.             System.out.printf("%s ", this.name);
  80.         }
  82.         /**
  83.          * 查找结点（前序遍历）
  84.          */
  85.         public boolean beforeOrderSearch(TreeNode node) {
  86.             if (this == null) {
  87.                 return false;
  88.             }
  89.             // 1、比较查找值跟当前结点是否相等，如果相等则直接返回
  90.             if (Objects.equals(node.name, this.name)) {
  91.                 return true;
  92.             }
  93.             // 2、当前结点没找到的话，则继续从左子树去查找
  94.             boolean bool = false;
  95.             if (this.left != null) {
  96.                 bool = this.left.beforeOrderSearch(node);
  97.             }
  98.             // 3、左子树没找到的话，则继续从右子树去查找
  99.             if (!bool) {
  100.                 if (this.right != null) {
  101.                     bool = this.right.beforeOrderSearch(node);
  102.                 }
  103.             }
  104.             return bool;
  105.         }
  107.         /**
  108.          * 删除结点
  109.          */
  110.         public void deleteNode(TreeNode node){
  111.             // 由于结点是单向的，根据父结点可以找到子结点，而子结点找不到父结点，所以需要判断子结点是不是要删除的结点
  112.             if (this == null) {
  113.                 return;
  114.             }
  115.             // 1、如果左结点就是删除结点，则将左结点设为null，直接返回
  116.             if (this.left != null && Objects.equals(this.left.name, node.name)) {
  117.                 this.left = null;
  118.                 return;
  119.             }
  120.             // 2、如果右结点就是删除结点，则将右结点设为null，直接返回
  121.             if (this.right != null && Objects.equals(this.right.name, node.name)) {
  122.                 this.right = null;
  123.                 return;
  124.             }
  125.             // 3、找不到删除结点，则分别向左右结点递归
  126.             this.left.deleteNode(node);
  127.             this.right.deleteNode(node);
  128.         }
  129.     }
  131.     public BinaryTree() {
  132.         // 初始化二叉树
  133.         //       A
  134.         //      / \
  135.         //     B   C
  136.         //    / \
  137.         //   D   E
  138.         TreeNode E = new TreeNode("E", null, null);
  139.         TreeNode D = new TreeNode("D", null, null);
  140.         TreeNode B = new TreeNode("B", D, E);
  141.         TreeNode C = new TreeNode("C", null, null);
  142.         this.rootNode = new TreeNode("A", B, C);
  143.     }
  145.     /**
  146.      * 前序遍历
  147.      */
  148.     public void beforeOrderPrint() {
  149.         if (rootNode == null) {
  150.             System.out.println("前序遍历为空");
  151.             return;
  152.         }
  153.         rootNode.beforeOrder();
  154.     }
  156.     /**
  157.      * 中序遍历
  158.      */
  159.     public void middleOrderPrint() {
  160.         if (rootNode == null) {
  161.             System.out.println("中序遍历为空");
  162.             return;
  163.         }
  164.         rootNode.middleOrder();
  165.     }
  167.     /**
  168.      * 后序遍历
  169.      */
  170.     public void afterOrderPrint() {
  171.         if (rootNode == null) {
  172.             System.out.println("空树遍历为空");
  173.             return;
  174.         }
  175.         rootNode.afterOrder();
  176.     }
  178.     /**
  179.      * 查找（前序遍历）
  180.      */
  181.     public Boolean beforeOrderSearch(String name) {
  182.         if (rootNode == null) {
  183.             return false;
  184.         }
  185.         TreeNode node = new TreeNode(name, null, null);
  186.         return rootNode.beforeOrderSearch(node);
  187.     }
  189.     /**
  190.      * 删除结点
  191.      */
  192.     public void deleteNode(String name){
  193.         if (rootNode == null) {
  194.             System.out.println("二叉树为空，无法删除");
  195.             return;
  196.         }
  197.         // 删除根结点时，则直接将根结点设为null
  198.         if (Objects.equals(rootNode.name, name)) {
  199.             rootNode = null;
  200.             return;
  201.         }
  202.         TreeNode node = new TreeNode(name, null, null);
  203.         rootNode.deleteNode(node);
  204.     }
  206.     public static void main(String[] args) {
  207.         BinaryTree binaryTree = new BinaryTree();
  208.         // A B D E C
  209.         System.out.print("前序遍历：");
  210.         binaryTree.beforeOrderPrint();
  211.         System.out.println();
  213.         // D B E A C
  214.         System.out.print("中序遍历：");
  215.         binaryTree.middleOrderPrint();
  216.         System.out.println();
  218.         // D E B C A
  219.         System.out.print("后序遍历：");
  220.         binaryTree.afterOrderPrint();
  221.         System.out.println();
  223.         System.out.println("查找(前序遍历)：" + binaryTree.beforeOrderSearch("D"));
  225.         binaryTree.deleteNode("C");
  226.         System.out.print("删除结点后：");
  227.         binaryTree.beforeOrderPrint();
  229.     }
  231. }


二叉树存储方式：**
1、顺序存储
2、链式存储

/**
 * 《顺序存储二叉树》
 *      二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。
 *  从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组
 *
 *           A[0]
 *         /     \                           0  1  2  3  4  5  6
 *        B[1]   C[2]              ---->     |  |  |  |  |  |  |
 *      /   \    /   \                      [A, B, C, D, E, F, G]
 *    D[3] E[4] F[5] G[6]
 *
 * 顺序存储二叉树的特点:
 *   (1)顺序二叉树通常只考虑完全二叉树
 *   (2)第n个元素的左子节点为 2 * n + 1
 *   (3)第n个元素的右子节点为 2 * n + 2
 *   (4)第n个元素的父节点为 (n-1) / 2
 * n：表示二叉树中的第几个元素(按0开始编号如图所示)
 *
 */
public class ArrayBinaryTree {

    private String[] arr;

    public ArrayBinaryTree(String[] arr) {
        this.arr = arr;
    }

    /**
     * 前序遍历
     */
    public void beforeOrder() {
        this.beforeOrder(0);
    }

    private void beforeOrder(int index) {
        if (index >= arr.length) {
            return;
        }
        // 1、输出结点
        System.out.printf("%s ", arr[index]);
        // 2、前序遍历左结点
        beforeOrder(2 * index + 1);
        // 3、前序遍历右结点
        beforeOrder(2 * index + 2);
    }

    public static void main(String[] args) {
        String[] arr = new String[]{"A", "B", "C", "D", "E", "F", "G"};
        ArrayBinaryTree tree = new ArrayBinaryTree(arr);
        // A  B  D  E  C  F  G
        tree.beforeOrder();
    }
}

2、多叉树

在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树（multiway tree）
树 - 图1