数据结构--树_数据结构 树

一、树的概念

这是一颗大自然的树

这是数据结构中的树

二者看起来是如此的相像，现实中的树是根在地上，枝干往上长，叶子在整颗树的最顶端。而数据结构中的树如此相似却又刚好相反，树的根在上面，枝干往下长，叶子在树的最底端。先在脑子里有这么个概念，具体有关于树的术语在下文详细提及。

定义

树是一种非线性结构，由n（n >= 0）个结点组成，当n=0的时候，此时的树被称为空树。当n>0时，此时的树存在一个结点被称为根结点（如上图的A结点），而除根结点外的其它结点可以分为m个集合，每个集合本身又是一颗树，被称为根结点的子树。
由定义可以看出，树中结点最多只能有一个父结点，可以有0个或多个子结

分析

这里即将介绍一些树的术语：

• 树的根结点：一棵树的根结点位于这个树的最上面，它没有父结点。
• 结点的度：一个结点包含子树的数目称为该结点的度。
• 叶子结点：度为0的结点称为叶子结点。
• 结点的层次：从根结点开始，根结点的层次为1，根结点的子结点为第二层，如此往下类推。
• 树的度：树中结点的度的最大值。上图树的度为3.
• 树的高度或深度：树中结点的最大层次。
• 父结点：每个结点的前驱结点称为父结点。如上图的B是E和F的父结点。
• 子结点：每个结点的后继结点称为子结点。如上图的E和F是B的子结点。
• 兄弟结点：同个父结点下的子结点称为兄弟结点。如上图的E和F，K和L。
• 结点的高度：结点距最底层的叶子结点的距离称为结点的高度。如上图B结点的高度为4。
• 结点的深度：结点距根结点的距离称为结点的深度。如上图的B结点的深度为2。

从10和11可以看出一个结点的高度和深度未必相等。但是对于一棵树而言，高度和深度是同一个概念。

二、二叉树

二叉树：所有结点下最多只能有两个子结点，满足该条件即为二叉树；顾名思义，二叉树最多只能有两个分叉；

二叉树遍历：

• 先序遍历
  父结点–>左子树—>右子树
  

• 中序遍历
  左子树–>父节点–>右子树
  

• 后序遍历
  左子树–>右子树–>父节点
  

其实很好理解，顺序说的都是父结点的顺序，先序就是先父结点再左右，中序就是父结点总是在中间，后序就是父结点总在最后；子结点都是先左后右

算法代码：

public class TreeNode<T> {
    
    private T val;
    private TreeNode<T> left;
    private TreeNode<T> right;
    
    public T getVal() {
        return val;
    }
    public void setVal(T val) {
        this.val = val;
    }
    public TreeNode<T> getLeft() {
        return left;
    }
    public void setLeft(TreeNode<T> left) {
        this.left = left;
    }
    public TreeNode<T> getRight() {
        return right;
    }
    public void setRight(TreeNode<T> right) {
        this.right = right;
    }
    //先序
    public static <T> void  preOrderTraverse(TreeNode<T> tree) {
        if(tree==null) return;
        System.out.println(tree.getVal());
        preOrderTraverse(tree.getLeft());
        preOrderTraverse(tree.getRight());
    }
    //中序
    public static <T> void  inOrderTraverse(TreeNode<T> tree) {
        if(tree==null) return;
        preOrderTraverse(tree.getLeft());
        System.out.println(tree.getVal());
        preOrderTraverse(tree.getRight());
    }
    //后序
    public static <T> void  postOrderTraverse(TreeNode<T> tree) {
        if(tree==null) return;
        preOrderTraverse(tree.getLeft());
        preOrderTraverse(tree.getRight());
        System.out.println(tree.getVal());
    }
       
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47