Fork me on GitHub

树

发表于 | 更新于 | 分类于

介绍

树 是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。

树里的每一个节点有一个根植和一个包含所有子节点的列表。从图的观点来看，树也可视为一个拥有N 个节点和N-1 条边的一个有向无环图。

二叉树是一种更为典型的树树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

先上二叉树的数据结构：

1
2
3
4
5
6
7
class Node{
    int value;
    //左孩子
    TreeNode left;
    //右孩子
    TreeNode right;
}

二叉树的遍历

前序遍历

首先访问根节点，然后遍历左子树，最后遍历右子树。

1
2
3
4
5
6
7
8
public static void preOrderRecur(Node head) {
       if (head == null) {
           return;
       }
       System.out.print(head.value + " ");
       preOrderRecur(head.left);
       preOrderRecur(head.right);
   }

中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。

1
2
3
4
5
6
7
8
public static void inOrderRecur(Node head) {
    if (head == null) {
        return;
    }
    inOrderRecur(head.left);
    System.out.print(head.value + " ");
    inOrderRecur(head.right);
}

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

1
2
3
4
5
6
7
8
public static void posOrderRecur(Node head) {
    if (head == null) {
        return;
    }
    posOrderRecur(head.left);
    posOrderRecur(head.right);
    System.out.print(head.value + " ");
}

层序遍历

层序遍历就是逐层遍历树结构。

广度优先搜索是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。

当我们在树中进行广度优先搜索时，我们访问的节点的顺序是按照层序遍历顺序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//层次遍历
    public void theLeverTraversal(Node root) {
        if (root == null) {
            return;
        }
        //新建一个队列，LinkedList实现了Quene接口，可以直接当作队列来用
        LinkedList<Node> queue = new LinkedList<Node>();

        Node current;  //当前节点
        queue.offer(root);//根节点入队列

        while (!queue.isEmpty()) {
            current = queue.poll();  //取出队列的头节点
            System.out.print(current.value + " ");//输出队列的头节点的值
            if (current.left != null) {
                queue.offer(current.left);  //如果当前节点的左节点不为空，则左节点入队列
            }
            if (current.right != null) {
                queue.offer(current.right); //如果当前节点的右节点不为空，则右节点入队列
            }
        }
    }