本文共 23412 字，大约阅读时间需要 78 分钟。

数据结构和算法系列共八篇

先介绍个工具

1.概念

1-1.什么是树

树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。

没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。

1-2.度

度(degree)分为

• 节点的度, 含有几个子节点(儿子)
• degree为0的节点，称为叶子节点leaf
• 最上层的曾为根节点root
• degree不为0的节点，除根以外称为内部节点
• 树的度，各节点的最大degree称为树的degree (m叉树)

1-3.深度

深度(depth)又叫层次(level),root为第一层，其子节点为第二层，子的子为第三层…以此类推

1-4.树的分类

顺序分

如果树的节点是有顺序的，那就是有序树，没有顺序的则是无序的

节点分

按树所有node里，某node的子node最多树为m，那就是m叉树 (以最多的为基准，即树的degree)

树的个数分

多棵树组成一个森林，一个树只是特殊的森林。

1-5.节点间关系

直接关系

• 父节点：一个节点直接前节点
• 子节点：一个节点直接后节点
• 兄弟节点：同一父节点的，其他节点

间接关系

• 祖先：从根到该节点所经分支上的所有节点；
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟

2.二叉树

二叉树，是m叉树为2的特殊树(即:树的degree小于等于2)。

2-1.二叉树特性

有兴趣的可以看下其证明

2-2.二叉树分类

2-2-1.满二叉树

高度为k并且有$2^{k+1}-1$个结点的二叉树。

2-2-2.完全二叉树

基于满二叉树，在最下层从最右侧起去掉相邻的若干叶子结点，得到的二叉树称为完全二叉树。

2-3.二叉树的存储结构

• 顺序数组存储
• 链结构存储

2-3-1.顺序数组存储

如果是完全二叉树，用顺序存储很好。但是不是完全二叉树的话，中间会有空留，占用空间。

2-3-2.链结构存储

链表结构比较适合二叉树存储。node节点结构：左子节点、数据、右子节点。

这样的数据结构，只能保证父找到子，不能保证子找父的。(如需子找到父，那还得需要多加个父节点存储)

3.遍历

二叉树遍历根据root的位置分三种

• 前序遍历：根-左-右 DLR
• 中序遍历：左-根-右 LDR
• 后序遍历：左-右-根 LRD

3-1.前序遍历

心法口诀：首先访问根，再先序遍历左子树，最后先序遍历右子树

传统分析

1.找到root-1，然后左边子node-4，右边子node-1。得到1 4_ 2_

2.再分析左边的node-4，node-4的左子node没有，右子node为node-5。得到1 4 5 2_

3.左边没有，在分析右边node-2，node-2的左子node-3，右子node-6。得到1 4 5 2 3 6 _

4.再分析node-3的，左右子node都没有，是leaf

5.再分析node-6，左子node没有，右子node-7。得到1 4 5 2 3 6 7

个人技巧

注意上面箭头方向。从最左上，每次一层，所得的结果就是前序结果。

用咱的小技巧去试试前面的二叉树吧，看是不是得到一样的结果。

3-2.中序遍历

心法口诀：首先中序遍历左子树，再访问根，最后中序遍历右子树

传统分析

1.找到root-1放中间，然后左边子node-4放左侧，右边子node-1放右侧。得到_4_ 1 2_(此时下划线是4和2的)

2.再分析左边的node-4，node-4的左子node没有，右子node为node-5。得到4 5 1 _2_(此时下划线是2的)

3.左边没有，在分析右边node-2，node-2的左子node-3放左侧，右子node-6放右测。得到4 5 1 _3_2_6_(此时下划线是3和6的)

4.再分析node-3的，左右子node都没有，是leaf。4 5 1 3 2_6_(3没有左右，那么就将3的左右下划线删去)

5.再分析node-6，左子node没有，右子node-7放右测。得到4 5 1 3 2 6 7

个人技巧

因为根在中间，那不就是跟我们二叉树一样吗!!!(左根右，LDR)，所以直接把二叉树压平到一条线，不就是需要的顺序吗? 是不是so easy😀!

我相信你看到这，肯定想将文章拉到最后，要给我一个大大的赞👍或者来段评论啥的(去吧，不拦你😄，记得回来找我，接着往下看)。

用咱的小技巧去试试前面的二叉树吧，看是不是得到一样的结果。

3-3.后序遍历

心法口诀：首先中序遍历左子树，再中序遍历右子树，最后访问根

传统分析

1.找到root-1放最后，然后左边子node-4放左1侧，右边子node-1放左2侧。得到_4 _2 1(此时下划线是4和2的)

2.再分析左边的node-4，node-4的左子node没有，右子node为node-5放左2侧。得到5 4 _2 1(此时下划线是2的)

3.左边没有，在分析右边node-2，node-2的左子node-3放左1侧，右子node-6放左2测。得到5 4 _3 _6 2 1(此时下划线是3和6的)

4.再分析node-3的，左右子node都没有，是leaf。5 4 3 _6 2 1(3没有左右，那么就将3的左右下划线删去)

5.再分析node-6，左子node没有，右子node-7放左2侧。得到5 4 3 7 6 2 1

个人技巧

这个小技巧没上面个两种直观。但也能出来，比较啰嗦。说下，能理解的就用，不理解的话，还是使用传统方式

口诀：由左到右,由下往上的顺序(左的优先级比下高)。先左看再右看最后向前看齐(跟中国式过马路似的，先左再右看，最后前看。下面右解释)，每遇到root有分叉，将root放局部最后位置。(因为是后序遍历，所以遇到是root的，直接放到局部域最后位置)

1. 6虽比9层次低，但是6比9靠左，左的优先级比下高。6开始，往上找祖先，直到遇到4分叉了。先左看再右看，最后向前看。将2放局部最后。结果为：7 6 4 _ 2 (此时下划线是2的)
2. 继续找左分支上，最左且最下层没有处理过的node为9。往上走找祖先，直到2没遇到分叉。结果为：7 6 4 9 8 5 2
3. 2继续找祖先,遇到了1分支。将1放局部最后。结果为：7 6 4 9 8 5 2 _ 1 (此时下划线是1的，代表1右节点遍历数据)
4. 看右测的最左且最下层是10，往上找祖先，直到遇到1分叉。结果为：7 6 4 9 8 5 2 10 12 11 3 1

这有几点说明：

• 左的优先级比下高：6虽比9层次低，但是6比9靠左，左的优先级比下高。（虽然9在第5层，6和4在第4和3层）。因为左比层次(下)优先级高。
• 先左看再右看，最后向前看：意思6是4的左节点，7在4的右子节点上。那是先6再7最后4的顺序。

说下马路过程：(大家都知道中国交通规则是靠右行的)，直接上图吧

1.过马路，还没过一半前，先左边看，因为汽车是靠右行的，防止有车冲过来。

2.过完一半后，再左边看，防止另一半车再冲过来

3.过完马路了，左右都安全了，最后往前看走路

4.代码实战

4-1.接口

接口

public interface ITree {
       /**     * 是否空树     *     * @return     */    public boolean isEmpty();    /**     * 树结点数量     *     * @return     */    public int size();    /**     * 获取二叉树的高度     *     * @return     */    public int getHeight();    /**     * 查询指定值的结点     *     * @param value     * @return     */    public TreeNode findKey(int value); // 查找    /**     * 前序递归遍历     */    public void preOrderTraverse();    /**     * 中序遍历递归操作     */    public void inOrderTraverse();    /**     * 后序遍历递归操作     */    public void postOrderTraverse();    /**     * 中序遍历非递归操作     * 1）对于任意节点current，若该节点不为空则将该节点压栈，并将左子树节点置为current，重复此操作，直到current为空。     * 2）若左子树为空，栈顶节点出栈，访问节点后将该节点的右子树置为current     * 3) 重复1、2步操作，直到current为空且栈内节点为空。     */    public void inOrderByStack();    /**     * 前序遍历非递归操作     * 1）对于任意节点current，若该节点不为空则访问该节点后再将节点压栈，并将左子树节点置为current，重复此操作，直到current为空。     * 2）若左子树为空，栈顶节点出栈，将该节点的右子树置为current     * 3) 重复1、2步操作，直到current为空且栈内节点为空。     */    public void preOrderByStack();    /**     * 后序遍历非递归操作     * 1）对于任意节点current，若该节点不为空则访问该节点后再将节点压栈，并将左子树节点置为current，重复此操作，直到current为空。     * 2）若左子树为空，取栈顶节点的右子树，如果右子树为空或右子树刚访问过，则访问该节点，并将preNode置为该节点     * 3) 重复1、2步操作，直到current为空且栈内节点为空。     */    public void postOrderByStack();    /**     * 按照层次遍历二叉树     */    public void levelOrderByQueue();}

二叉node节点定义

public class TreeNode {
       private Object data;    private TreeNode leftChild;    private TreeNode rightChild;    public TreeNode(Object data, TreeNode leftChild, TreeNode rightChild) {
           this.data = data;        this.leftChild = leftChild;        this.rightChild = rightChild;    }    public Object getData() {
           return data;    }    public void setData(Object data) {
           this.data = data;    }    public TreeNode getLeftChild() {
           return leftChild;    }    public void setLeftChild(TreeNode leftChild) {
           this.leftChild = leftChild;    }    public TreeNode getRightChild() {
           return rightChild;    }    public void setRightChild(TreeNode rightChild) {
           this.rightChild = rightChild;    }    @Override    public String toString() {
           return "TreeNode{" + "data=" + data + ", leftChild=" + leftChild.getData() + ", rightChild=" + rightChild.getData() + '}';    }}

4-2.实现代码

整体实现代码最后整体给出，这先每个片段给出，并分析。

分析尽我最大解释，实在不懂，那就得靠自己悟了

4-2-1.空判断

public class MyListBinaryTree implements ITree {
       private TreeNode root;    public MyListBinaryTree(TreeNode root) {
           this.root = root;    }    @Override    public boolean isEmpty() {
           return root == null;    }}

只要判断root是否为空

4-2-2.大小

public int size() {
           return size(this.root);    }private int size(TreeNode node) {
       // 为null时返回0，不为null时加一    if (node == null) {
           return 0;    }    int leftSize = size(node.getLeftChild());    int rightSize = size(node.getRightChild());    // 左右子节点都会掉一次，所以只要node为null的只要自己加一就行    return leftSize + rightSize + 1;}

使用递归方式，每次将left child和 right child传进去。空的时候，就返回0，否则加一

4-2-3.树深度

@Override    public int getHeight() {
           // 求深度，即求从root出来的child node谁最长        return getHeight(root);    }private int getHeight(TreeNode node) {
       if (node == null) {
           return 0;    }    // 左子节点    int leftNum = getHeight(node.getLeftChild());    // 右子节点    int rightNum = getHeight(node.getLeftChild());    // 返回大的+1    return leftNum > rightNum ? leftNum + 1 : rightNum + 1;}

使用递归方式，每次将left child和 right child传进去。空的时候，就返回0，否则将左右返回值中较大的加一

4-2-4.查找

@Override    public TreeNode findKey(Object value) {
           return this.findKey(value, root);    }private TreeNode findKey(Object value, TreeNode node) {
       if (node == null) {
           return null;    }    if (node.getData().equals(value)) {
           return node;    }    TreeNode leftNode = findKey(value, node.getLeftChild());    TreeNode rightNode = findKey(value, node.getRightChild());    if (leftNode != null) {
           return leftNode;    }    if (rightNode != null) {
           return rightNode;    }    return null;}

递归查找

4-2-5.前序遍历

递归方式实现

@Overridepublic void preOrderTraverse() {
       this.preOrderTraverse(root);}private void preOrderTraverse(TreeNode node) {
       if (node == null) {
           return;    }    // d输出    System.out.print(node.getData() + " ");    // l处理    preOrderTraverse(node.getLeftChild());    // r处理    preOrderTraverse(node.getRightChild());}

擦，不知从何讲起呀。(理解一眼就明白，不明白的，言语也解释不了😂)

递归：

1.给出终止条件，node为空结束

2.将根节点传给方法，因为前序遍历，所以要将d先输出

3.再将左子节点传给方法，作为根继续处理

4.将右子节点也传给递归方法，作为根继续处理

栈方式实现

@Overridepublic void preOrderByStack() {
       Deque
   
     stack = new LinkedList<>();    if (root == null) {
           return;    }    // 心法：以当前node移动，根据DLR、LDR、LRD的顺序去如何存取到stack中去    // 指向树的当前移动node点    TreeNode current = root;    List
    
   

上面代码有注释

大体思路:

从根起，将所有左节点全入栈中(从栈顶到栈尾为：6、4、2、1)，因为前序遍历，所以这时就要输出了，此时current为空跳出内部的while循环

到达if判断，从栈中弹出栈顶6，并赋值给current，并将6的右子节点7再赋给current（没有），此时4为栈顶。

循环一次while，将4弹出栈，将4右子节点给current，此时2成为栈顶了。

再做一次while循环，将7下面所有节点处理一边。发现没有，继续弹出2…(以此类推)

4-2-6.中序遍历

递归方式实现

@Overridepublic void inOrderTraverse() {
       this.inOrderTraverse(root);}private void inOrderTraverse(TreeNode node) {
       if (node == null) {
           return;    }    // l处理    inOrderTraverse(node.getLeftChild());    // d输出    System.out.print(node.getData() + " ");    // r处理    inOrderTraverse(node.getRightChild());}

递归：

1.给出终止条件，node为空结束

2.将根节点传给方法，因为中序遍历，所以要将d先放l和r中间

栈方式实现

@Overridepublic void inOrderByStack() {
       Deque
   
     stack = new LinkedList<>();    if (root == null) {
           return;    }    // 心法：以当前node移动，根据DLR、LDR、LRD的顺序去如何存取到stack中去    // 指向树的当前移动node点    TreeNode current = root;    List
    
   

上面代码有注释

大体思路:

从根起，将所有左节点全入栈中(从栈顶到栈尾为：6、4、2、1)，此时current为空跳出内部的while循环

到达if判断，从栈中弹出栈顶6，并赋值给current，因为是中序遍历，所以弹栈时就要输出，再将6的右子节点给current（为null），此时4成为栈顶。

再做一次while循环,从栈中弹出栈顶4, 将4的右子节点7再赋给current, 此是2成为了栈顶

再做一次while循环，将7下面所有节点处理一边。发现没有，继续弹出2…(以此类推)

4-2-7.后序遍历

递归方式实现

@Overridepublic void postOrderTraverse() {
       this.postOrderTraverse(root);}private void postOrderTraverse(TreeNode node) {
       if (node == null) {
           return;    }    // l处理    postOrderTraverse(node.getLeftChild());    // r处理    postOrderTraverse(node.getRightChild());    // d输出    System.out.print(node.getData() + " ");}

递归：

1.给出终止条件，node为空结束

2.将根节点传给方法，因为中序遍历，所以要将d先放l和r后面

栈方式实现1

@Overridepublic void postOrderByStack() {
       // 方式一：    Deque
   
     stack = new LinkedList<>();    if (root == null) {
           return;    }    List
    
   

思想：

将节点压到栈中，然后通过栈顶元素去判断有没子节点，有则入栈，没有则出栈。

出栈时打印结果。注意打印的条件两个

• 没有子节点，即leaf，需要打印
• 出栈的节点的有子节点，但是前一次出栈的节点，也需要打印

栈方式实现2

@Overridepublic void postOrderByStack() {
       // 方式二    Deque
   
     stack = new LinkedList<>();    if (root == null) {
           return;    }    // 心法：以当前node移动，根据DLR、LDR、LRD的顺序去如何存取到stack中去    // 指向树的当前移动node点    TreeNode current = root;    List
    
   

思路：

此要放结合前序栈方式遍历来理解(前序栈方式，以左子节点为先，一直while循环压榨)，而这后序栈方式，以右为先进行压栈

不过最后结果饭的，需要反转一下

4-2-8.水平遍历

@Overridepublic void levelOrderByQueue() {
       Deque
   
     queue = new LinkedList<>();    if (root == null) {
           return;    }    List
    
   

水平遍历要借助队列的特性来处理，将每层的放进queue里队尾，从头取出(每次while加一层数据，需要取将queue里数据都取出)

4-3.整体代码

package com.iworkh.da.lesson03;import java.util.ArrayList;import java.util.Deque;import java.util.LinkedList;import java.util.List;/** * 自定义二叉树 * * @author: iworkh-沐雨云楼 * @date: 2020-07-02 */public class MyListBinaryTree implements ITree {
       private TreeNode root;    public MyListBinaryTree(TreeNode root) {
           this.root = root;    }    @Override    public boolean isEmpty() {
           return root == null;    }    @Override    public int size() {
           return size(this.root);    }    private int size(TreeNode node) {
           // 为null时返回0，不为null时加一        if (node == null) {
               return 0;        }        int leftSize = size(node.getLeftChild());        int rightSize = size(node.getRightChild());        // 左右子节点都会掉一次，所以只要node为null的只要自己加一就行        return leftSize + rightSize + 1;    }    @Override    public int getHeight() {
           // 求深度，即求从root出来的child node谁最长        return getHeight(root);    }    private int getHeight(TreeNode node) {
           if (node == null) {
               return 0;        }        // 左子节点        int leftNum = getHeight(node.getLeftChild());        // 右子节点        int rightNum = getHeight(node.getLeftChild());        // 返回大的+1        return leftNum > rightNum ? leftNum + 1 : rightNum + 1;    }    @Override    public TreeNode findKey(Object value) {
           return this.findKey(value, root);    }    private TreeNode findKey(Object value, TreeNode node) {
           if (node == null) {
               return null;        }        if (node.getData().equals(value)) {
               return node;        }        TreeNode leftNode = findKey(value, node.getLeftChild());        TreeNode rightNode = findKey(value, node.getRightChild());        if (leftNode != null) {
               return leftNode;        }        if (rightNode != null) {
               return rightNode;        }        return null;    }    @Override    public void preOrderTraverse() {
           this.preOrderTraverse(root);    }    private void preOrderTraverse(TreeNode node) {
           if (node == null) {
               return;        }        // d输出        System.out.print(node.getData() + " ");        // l处理        preOrderTraverse(node.getLeftChild());        // r处理        preOrderTraverse(node.getRightChild());    }    @Override    public void inOrderTraverse() {
           this.inOrderTraverse(root);    }    private void inOrderTraverse(TreeNode node) {
           if (node == null) {
               return;        }        // l处理        inOrderTraverse(node.getLeftChild());        // d输出        System.out.print(node.getData() + " ");        // r处理        inOrderTraverse(node.getRightChild());    }    @Override    public void postOrderTraverse() {
           this.postOrderTraverse(root);    }    private void postOrderTraverse(TreeNode node) {
           if (node == null) {
               return;        }        // l处理        postOrderTraverse(node.getLeftChild());        // r处理        postOrderTraverse(node.getRightChild());        // d输出        System.out.print(node.getData() + " ");    }    @Override    public void preOrderByStack() {
           Deque
   
     stack = new LinkedList<>();        if (root == null) {
               return;        }        // 心法：以当前node移动，根据DLR、LDR、LRD的顺序去如何存取到stack中去        // 指向树的当前移动node点        TreeNode current = root;        List
    
   

4-4.测试代码

造的tree就是我们前面文章一直分析的树

public class MyListBinaryTreeTest {
       public static void main(String[] args) {
           TreeNode root = genBTree();        MyListBinaryTree myListBinaryTree = new MyListBinaryTree(root);        System.out.println("是否为空：" + myListBinaryTree.isEmpty());        System.out.println("树的高度：" + myListBinaryTree.getHeight());        System.out.println("树节点数：" + myListBinaryTree.size());        System.out.println("查找3： " + myListBinaryTree.findKey(3));        System.out.println("查找20：" + myListBinaryTree.findKey(20));        System.out.println("前序递归遍历：");        myListBinaryTree.preOrderTraverse();        System.out.println("");        System.out.println("中序递归遍历：");        myListBinaryTree.inOrderTraverse();        System.out.println("");        System.out.println("后序递归遍历：");        myListBinaryTree.postOrderTraverse();        System.out.println("");        System.out.println("前序栈遍历：");        myListBinaryTree.preOrderByStack();        System.out.println("");        System.out.println("中序栈遍历：");        myListBinaryTree.inOrderByStack();        System.out.println("");        System.out.println("后序栈遍历：");        myListBinaryTree.postOrderByStack();        System.out.println("");        System.out.println("水平队列遍历：");        myListBinaryTree.levelOrderByQueue();    }    private static TreeNode genBTree() {
           TreeNode treeNode6 = new TreeNode(6, null, null);        TreeNode treeNode7 = new TreeNode(7, null, null);        TreeNode treeNode4 = new TreeNode(4, treeNode6, treeNode7);        TreeNode treeNode9 = new TreeNode(9, null, null);        TreeNode treeNode8 = new TreeNode(8, null, treeNode9);        TreeNode treeNode5 = new TreeNode(5, treeNode8, null);        TreeNode treeNode2 = new TreeNode(2, treeNode4, treeNode5);        TreeNode treeNode10 = new TreeNode(10, null, null);        TreeNode treeNode12 = new TreeNode(12, null, null);        TreeNode treeNode11 = new TreeNode(11, null, treeNode12);        TreeNode treeNode3 = new TreeNode(3, treeNode10, treeNode11);        return new TreeNode(1, treeNode2, treeNode3);    }}

结果

是否为空：false树的高度：4树节点数：12查找3： TreeNode{data=3, leftChild=10, rightChild=11}查找20：null前序递归遍历：1 2 4 6 7 5 8 9 3 10 11 12 中序递归遍历：6 4 7 2 8 9 5 1 10 3 11 12 后序递归遍历：6 7 4 9 8 5 2 10 12 11 3 1 前序栈遍历：[1, 2, 4, 6, 7, 5, 8, 9, 3, 10, 11, 12]中序栈遍历：[6, 4, 7, 2, 8, 9, 5, 1, 10, 3, 11, 12]后序栈遍历：[6, 7, 4, 9, 8, 5, 2, 10, 12, 11, 3, 1]水平队列遍历：[1, 2, 3, 4, 5, 10, 11, 6, 7, 8, 12, 9]

5.链接

6.推荐

能读到文章最后，首先得谢谢您对本文的肯定，你的肯定是对博主最大的鼓励。

你觉本文有帮助，那就点个👍

你有疑问，那就留下您的💬 怕把我弄丢了，那就把我⭐ 电脑不方便看，那就把发到你📲

转载地址：http://kkhws.baihongyu.com/