二叉树基础

发表于 | 分类于 |

二叉树入门

树的基本定义

树是我们计算机非常重要的一种数据结构，同时使用树这种结构，可以描述现世生活中的很多事物。

树是由$n(n>=1)$个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是跟朝上，而叶朝下的。

树具有以下特点：

  • 每个结点有零个或多个子节点；
  • 没有父结点的结点为根结点；
  • 每一个非根结点只有一个父结点；
  • 每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树；

树的相关术语

结点的度：

一个结点含有的子树的个数称为该结点的度；

叶结点：

度为0的结点称为叶节点，也可以叫做终端结点；

分支结点：

度不为0的结点称为分支结点，也可以叫做非终端结点；

结点的层次：

从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推；

结点的层序编号：

将树中的结点，按照从上层到下层，同层从左往右的次序排列成一个线性序列，把他们编成连续的自然数；

树的度：

树中所有结点的度的最大值；

树的深度(高度)：

树中结点的最大层次；

森林：

$m(m>=0)$个互不相交的树的集合，将一棵非空树的根结点删去，树就变成了一个森林；给森林增加一个统一的根结点，森林就会变成一棵树；

孩子结点：

一个结点的直接后继结点称为该结点的孩子结点；

双亲结点(父结点)：

一个结点的直接前驱称为该结点的双亲结点；

兄弟结点：

同一双亲结点的孩子结点间互称为兄弟结点；

二叉树的基本定义

二叉树就是度不超过2的树(每个结点最多有两个子结点)

满二叉树：

一个二叉树，如果每一层的结点树都到达最大值，则这个二叉树就是满二叉树。

完全二叉树：

叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

二叉查找树的创建

结点类的API设计：

类名 Node\
构造方法 Node(Key key, Value value, Node left, Node right)
成员变量 public Node left
public Node right
public Key key
public Value value

结点类的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
private class Node<Key,Value>{
    public Key key;
    public Value value;
    public Node left;
    public Node right;
    public Node(Key key, Value value, Node left, Node right){
        this.key = key;
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

二叉查找树的API设计：

类名 BinaryTree\, Value value>
构造方法 BinaryTree()
成员变量 private Node root
private int N
成员方法 public void put(Key key, Value value)
public Node put(Node x, Key key, Value val)
public Value get(Key key)
private Value get(Node x, Key key)
public void delete(Key key)
private Node delete(Node x, Key key)
public int size()

二叉查找树的代码实现：

  • 插入方法put实现思想：
    • 如果当前树中没有任何一个结点，则直接把新结点当做根结点使用
    • 如果当前树不为空，则从根结点开始：
      • 如果新结点的key小于当前结点的key，则继续找当前结点的左子结点；
      • 如果新结点的key大于当前结点的key，则继续找当前结点的右子结点；
      • 如果新结点的key等于当前结点的key，则树中已经存在这样的结点，替换该结点的value值即可。
  • 查询方法get实现思想：
    • 从根结点开始：
      • 如果要查询的key小于当前结点的key，则继续查找当前结点的左子结点；
      • 如果要查询的key大于当前结点的key，则继续查找当前结点的右子结点；
      • 如果要查询的key等于当前结点的key，则树中返回当前结点的value；
  • 删除方法delete实现思想：
    • 找到被删除结点；
    • 找到被删除结点右子树中的最小结点minNode；
    • 删除右子树中的最小结点；
    • 让被删除结点的左子树称为最小结点minNode的左子树，让被删除结点的右子树称为最小结点minNode的右子树；
    • 让被删除结点的父结点指向最小结点minNode。
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
public class BinaryTree<Key extends Comparable<Key>, Value>{
    private Node root;
    private int N;
    private class Node{
        public Key key;
        public Value value;
        public Node left;
        public Node right;
        public Node(Key key, Value value, Node left, Node right){
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    
    public int size(){
        return this.N;
    }
    
    public void put(Key key, Value value){
        root = put(root,key,value);
    }
    
    private Node put(Node x, Key key, Value value){
        //如果x子树为空
        if(x == null){
            N++;
            return new Node(key,value,null,null);
        }
        //子树不为空,比较x结点的键key的大小
        int cmp = key.compareTo(x.key);
        if(cmp > 0){
            x.right = put(x.right,key,value);
        }else if(cmp < 0){
            x.left = put(x.left,key,value);
        }else{
            x.value = value
        }
        N++;
        
        return x;
    }
    
    public Value get(Key key){
        return get(root,key);
    }
    
    private Value get(Node x, Key key){
        if(x == null){
            return null;
        }
        int cmp = key.compareTo(x.key);
        if(cmp > 0){
            return get(x.right,key);
        }else if(cmp < 0){
            return get(x.left,key);
        }else{
            return x.value;
        }
    }
    
    public void delete(Key key){
        return delete(root,key);
    }
    
    private Node delete(Node x, Key key){
        //x树为null
        if(x == null){
            return null;
        }
        //x树不为null
        int cmp = key.compareTo(x.key);
        if(cmp > 0){
            x.right = delete(x.right,key);
        }else if(cmp < 0){
            x.left = delete(x.left,key);
        }else{
            N--;
            //找到右子树中最小结点
            if(x.right == null){
                return x.left;
            }
            if(x.left == null){
                return x.right;
            }
            Node minNode = x.right;
            while(minNode.left != null){
                minNode = minNode.left;
            }
            //删除右子树中最小哦结点
            Node temp = x.right;
            while(temp.left != null){
                if(temp.left.left == null){
                    temp.left = null;
                }else{
                    temp = temp.left;
                }
            }
            //让x结点的左子树成为minNode的左子树
            minNode.left = x.left;
            //让x结点的右子树成为minNode的右子树
            minNode.right = x.right;
            //让x结点的父结点指向minNode
            x = minNode;
            
        }
        return x;
    }
}

二叉查找树其他便捷方法

查找二叉树中最小的键：

public Key min() 找出树中最小的键
private Node min(Node x) 找出指定树x中，最小键所在的结点 
1
2
3
4
5
6
7
8
9
10
11
public Key min(){
    return min(root).key;
}

private Node min(Node x){
    if(x.left != null){
        return min(x.left);
    }else{
        return x;
    }
}

查找二叉树中最大的键：

Public Key max() 找出树中最大的键
public Node max(Node x) 找出指定树x中，最大键所在的结点 
1
2
3
4
5
6
7
8
9
10
11
public Key max(){
    return max(root);
}

private Node max(Node x){
    if(x.right != null){
        return max(x.right);
    }else{
        return x;
    }
}

二叉树的基础遍历

很多情况下，我们可能需要像遍历数组一样，遍历树，从而拿出树中存储的每一个元素，由于树状结构和线性结构不一样，它没有办法从头开始依次向后遍历，所以存在如何遍历，也就是按照什么样的搜索路径进行遍历的问题。

二叉树的遍历分为以下三种方式：

  • 前序遍历：先访问根结点，然后再访问左子树，最后访问右子树
  • 中序遍历：先访问左子树，中间访问根结点，最后访问右子树
  • 后序遍历：先访问左子树，在访问右子树，最后访问根结点

前序遍历

public Queue\ preErgodic() 使用前序遍历，获取整个树中的所有键
private void preErgodic(Node x, Queue\ keys) 使用前序遍历，获取指定树x中的所有键

实现步骤：

  • 把当前结点的key放入到队列中；
  • 找到当前结点的左子树，如果不为空，递归遍历左子树；
  • 找到当前结点的右子树，如果不为空，递归调用遍历右子树。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public Queue<Key> preErgodic(){
    Queue<key> keys = new Queue<>();
    preErgodic(root,keys);
    return keys;
}

private void preErgodic(Node x, Queue<Key> keys){
    if(x == null){
        return;
    }
    //把x结点的key放入到keys中
    keys.enqueue(x.key);
    //递归遍历x结点的左子树
    if(x.left != null){
        preErgodic(x.left,keys);
    }
    //递归遍历x结点的右子树
    if(x.right != null){
        preErgodic(x.right,keys);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class BinaryTreeTest{
    public static void main(String[] args){
        //创建对象
        BinaryTree<String, String> tree = new BinaryTree<>();
        //在树中添加对象
        tree.put("E","5");
        tree.put("B","2");
        tree.put("G","7");
        tree.put("A","1");
        tree.put("D","4");
        tree.put("F","6");
        tree.put("H","8");
        tree.put("C","3");
        //遍历
        Queue<String> keys = tree.preErgodic();
        for(String key: keys){
            String value = tree.get(key);
            System.out.println(key + "---" + value);
        }
    }
}

中序遍历

public Queue\ midErgodic() 使用中序遍历，获取整个树的所有键
private void midErgodic(Node x, Queue\ keys) 使用中序遍历，获取指定树x中的所有键

实现步骤：

  • 找到当前结点的左子树，如果不为空，递归遍历左子树；
  • 把当前结点的key放入到队列中；
  • 找到当前结点的右子树，如果不为空，递归遍历右子树。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public Queue<Key> midErgodic(){
    Queue<Key> keys = new Queue<>();
    midErgodic(root,keys);
    return keys;
}

private void midErgodic(Node x, Queue<Key> keys){
    if(x == null){
        return;
    }
    //递归，把左子树中的键放入keys中
    if(x.left != null){
        midErgodic(x.left,keys);
    }
    //把当前结点x的键放入keys中
    keys.enqueue(x.key);
    //递归，把右子树中键放入到keys中
    if(x.right != null){
        midErgodic(x.right,keys);
    }
}

后序遍历

public Queue\ afterErgodic() 使用后序遍历，获取整个树中的所有键
private void afterErgodic(Node x, Queue\ keys) 使用后序遍历，获取指定树x的所有键

实现步骤：

  • 找到当前结点的左子树，如果不为空，递归遍历左子树；
  • 找到当前结点的右子树，如果不为空，递归遍历右子树；
  • 把当前结点的key放入到队列中。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public Queue<Key> afterErgodic(){
    Queue<Key> keys = new Queue<>();
    afterErgodic(root,keys);
    return keys;
}

private void afterErgodic(Node x, Queue<Key> keys){
    if(x == null){
        return;
    }
    if(x.left != null){
        return afterErgodic(x.left,keys);
    }
    if(x.right != null){
        return afterErgodic(x.right,keys);
    }
    keys.enqueue(x.key);
}

二叉树的层序遍历

所谓的层序遍历，就是从根结点开始，依次向下，获取每一层所有结点的值。

层序遍历的API：

public Queue\ layerErgodic() 使用层序遍历，获取整个树中的所有键

实现步骤：

  • 创建队列，存储每一层的结点；
  • 使用循环从队列中弹出一个结点：
    • 获取当前结点的key；
    • 如果当前结点的左子结点不为空，则把左子结点放入到队列中；
    • 如果当前结点的右子结点不为空，则把右子结点放入到队列中；

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public Queue<Key> layerErgodic(){
    //定义两个队列，分别存储树中的键和树中的结点
    Queue<Key> keys = new Queue<>();
    Queue<Node> nodes = new Queue<>();
    
    //默认，往队列中放入根结点
    nodes.enqueue(root);
    while(nodes.isEmpty()){
        //从队列中弹出节点，把key放入keys中
        Node temp = nodes.dequeue();
        keys.enqueue(temp.key);
        //判断当前结点还有没有左子结点，如果有，则放入到nodes中
        if(temp.left != null){
            nodes.enqueue(temp.left);
        }
        //判断当前结点还有没有右子结点，如果有，则放入等nodes中
        if(temp.right != null){
            nodes.enqueue(temp.right);
        }
    }
    return keys;
}

二叉树的最大深度问题

需求：

给定一棵树，请计算出树的最大深度。

最大深度的API：

public int maxDepth() 计算整个树的最大深度
private int maxDepth(Node x) 计算指定树x的最大深度

实现步骤：

  • 如果根结点为空，则最大深度为0；
  • 计算左子树的最大深度；
  • 计算右子树的最大深度；
  • 当前树的最大深度=左子树的最大深度和右子树的最大深度的较大者 + 1

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int maxDepth(){
    return maxDepth(root);
}

private int maxDepth(Node x){
    if(x == null){
        return 0;
    }
    int max = 0;
    int maxL = 0;
    int maxR = 0;
    //计算左子树的最大深度
    if(x.left != null){
        maxL = maxDepth(x.left);
    }
    //计算右子树的最大深度
    if(x.right != null){
        maxR = maxDepth(x.right);
    }
    //比较左子树最大深度和右子树最大深度，取较大值+1
    max = maxL > maxR ? (maxL+1) : (maxR+1);
    return max;
}

折纸问题

需求：

把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折一次，压出折痕后展开。此时，折痕是凹下去的，即折痕突起的方向指向纸条的背面，如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。

给定一个输入参数N，代表纸条从下边向上方对折N次，请从上到下打印所有折痕的方向；例如：N=1，打印：down；N=2，打印：donw，donw，up。

分析：

我们把对折后的纸张翻过来，这时把第一次对折产生的折痕看做是根结点，那第二次对折产生的下折痕就是该结点的左子结点，而第二次对折的上折痕就是该结点的右子结点，这样我们就可以使用树型数据结构来描述对折后产生的折痕。

这棵树有这样的特点：

  • 根结点为下折痕；
  • 每一个结点的左子结点为下折痕；
  • 每一个结点的右子结点为上折痕；

构建深度为N的折痕树：

  • 第一次对折，只有一条折痕，创建根结点；
  • 如果不是第一次对折，则使用队列保存根结点；
  • 循环遍历队列：
    • 从队列中拿出一个结点
    • 如果这个结点的左子结点不为空，则把这个左子结点添加到队列中
    • 如果这个结点的右子结点不为空，则把这个右子结点添加到队列中；
    • 判断当前结点的左子结点和右子结点都不为空，如果是，则需要为当前结点创建一个值为down的左子结点，一个值为up的右子结点。

代码的实现：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class PagerFoldingTest{
    public static void main(String[] args){
        
    }
    
    //通过模拟对折N次纸，产生树
    public static Node<String> createTree(int N){
        Node<String> root = null;
        for(int i = 0; i < N; i++){
            //当前是第一次对折
            if(i == 0){
                root = new Node<>("down",null,null);
                continue;
            }
            //当前不是第一次对折
            //定义一个辅助队列，通过层序遍历的思想，找到叶子结点
            Queue<Node> queue = new Queue<>();
            queue.enqueue(root);
            while(!queue.isEmpty()){
                //从队列中弹出一个节点
                Node<String> temp = queue.dequeue();
                //如果有左子结点，则把左子结点放入到队列中
                if(temp.left != null){
                    queue.enqueue(temp.left);
                }
                //如果有右子结点，则把右子结点放入队列中
                if(temp.right != null){
                    queue.enqueue(temp.right);
                }
                //同时没有左子结点和右子结点，则为叶子节点，只需要给该结点添加左子结点或右子结点
                if(temp.left == null && temp.right == null){
                    temp.left = new Node<String>("down",null,null);
                    temp.right = new Node<String>("up",null,null);
                }
            }
        }
        return root;
    }
    
    //遍历树
    public static void printTree(Node<String> root){
        //需要使用中序遍历
        if(root == null){
            return;
        }
        if(root.left != null){
            printTree(root.left);
        }
        System.out.println(root.item+" ");
        if(root.right != null){
            printTree(root.right);
        }
    }
    
    //结点类
    private static class Node<T>{
        public T item;
        public Node left;
        public Node right;
        
        public Node(T item, Node left, Node right){
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }
}
Donate comment here