二叉排序树

当二叉树有一定顺序的时候它就是二叉排序树。

特点：

    • 若左子树不为空，则左子树上的所有节点的值均小于它的根节点的值、
    • 若右子树不为空，则右子树上的所有节点的值均大于它的根节点的值
    • 左右子树也分别为二叉排序树
    • 没有键值相等的节点

代码实现

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
package com.ss.study.tree.binary;

import lombok.Data;

import javax.validation.constraints.NotNull;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Optional;

/**
 * 二叉排序树
 * @author xia17
 * @date 2019/12/19 11:02
 */
public class BinarySortTree {

    private SortNode root ;

    public void push(int key){
        if (root == null){
            root = new SortNode(key);
        }else {
            push(root,key);
        }
    }

    private void push(@NotNull SortNode node , int key){
        if (key > node.getKey()){
            //大于则加到右子树
            if (node.getRight() == null){
                node.setRight(new SortNode(key));
            }else {
                push(node.getRight(),key);
            }
        }else if (key < node.getKey()){
            if (node.getLeft() == null){
                node.setLeft(new SortNode(key));
            }else {
                push(node.getLeft(),key);
            }
        }else {
            throw new RuntimeException("树中已经有了该键值");
        }
    }

    /**
     * 查找
     * @param key 兼职
     * @return 节点
     */
    public Optional<SortNode> find(int key){
        if (root == null){
            return Optional.empty();
        }else {
            return find(root,key);
        }
    }

    /**
     * 查找的递归方法
     * @param node 查找子树的根节点
     * @param key 值
     * @return 节点
     */
    private Optional<SortNode> find(@NotNull SortNode node , int key){
        if (key > node.getKey()){
            //大于则加到右子树
            if (node.getRight() == null){
                return Optional.empty();
            }else {
                return find(node.getRight() , key);
            }
        }else if (key < node.getKey()){
            if (node.getLeft() == null){
                return Optional.empty();
            }else {
                return find(node.getLeft() , key);
            }
        }
        return Optional.of(node);
    }

    /**
     * 前序遍历 先访问根节点，再访问左子树，最后访问右子树
     *  ----------- 这里采用的方法时顺序加入到list中 ， 这里感觉应该用数组效率会好一点， 因为这里的数据其实是固定大小的
     * @return 迭代器
     */
    public Iterator<SortNode> frontIterator(){
        ArrayList<SortNode> nodes = new ArrayList<>();
        if (this.root != null){
            addToFrontNodeList(nodes,this.root);
        }
        return nodes.iterator();
    }

    /**
     * 前序遍历 的 递归方法
     * @param nodes 结果
     * @param node 节点
     */
    private void addToFrontNodeList(List<SortNode> nodes,SortNode node){
        nodes.add(node);
        if (node.getLeft()!=null){
            addToFrontNodeList(nodes,node.getLeft());
        }
        if (node.getRight()!=null){
            addToFrontNodeList(nodes,node.getRight());
        }
    }


    /**
     * 后序遍历 先左子树，再右子树，最后根节点
     *  ----------- 这里采用的方法时顺序加入到list中 ， 这里感觉应该用数组效率会好一点， 因为这里的数据其实是固定大小的
     * @return 迭代器
     */
    public Iterator<SortNode> backIterator(){
        ArrayList<SortNode> nodes = new ArrayList<>();
        if (this.root != null){
            addToBackNodeList(nodes,this.root);
        }
        return nodes.iterator();
    }

    /**
     * 后续遍历的递归方法
     * @param nodes 结果
     * @param node 节点
     */
    private void addToBackNodeList(List<SortNode> nodes, SortNode node){
        if (node.getLeft()!=null){
            addToBackNodeList(nodes,node.getLeft());
        }
        if (node.getRight()!=null){
            addToBackNodeList(nodes,node.getRight());
        }
        nodes.add(node);
    }


    public static void main(String[] args) {
        BalancedBinaryTree tree = new BalancedBinaryTree();
        tree.push(3);
        tree.push(2);
        tree.push(1);
        tree.push(4);
        tree.push(5);
        System.out.println();
    }

}

@Data
class SortNode{

    SortNode(int key){
        this.key = key;
    }

    private int key;
    private SortNode left ;
    private SortNode right;

}