二叉查找树 java代码实现_二叉查找树代码java

代码实现

节点实现类

package csdn.dreamzuora.tree;

/**
 * Title:
 * Description:
 *
 * @version 1.0
 * @author: weijie
 * @date: 2020/10/19 13:30
 */
public interface Node {
}

1
2
3
4
5
6
7
8
9
10
11
12
13

package csdn.dreamzuora.tree;

import java.io.Serializable;

/**
 * Title:
 * Description:
 *
 * @version 1.0
 * @author: weijie
 * @date: 2020/10/19 13:27
 */
public abstract class AbstractNode<T, E> implements Node, Serializable {

    private static final long serialVersionUID = -2321782309212147194L;

    /**
     * 数据域
     */
    T data;
    /**
     * 左孩子
     */
    E left;
    /**
     * 右孩子
     */
    E right;



    public AbstractNode() {
    }

    public AbstractNode(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public E getLeft() {
        return left;
    }

    public void setLeft(E left) {
        this.left = left;
    }

    public E getRight() {
        return right;
    }

    public void setRight(E right) {
        this.right = right;
    }
}

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

package csdn.dreamzuora.tree;
/**
 * Title: 二叉树节点
 * Description:
 *
 * @version 1.0
 * @author: weijie
 * @date: 2020/10/19 13:27
 */
public class BinaryNode extends AbstractNode<Integer, BinaryNode>{

    public BinaryNode(Integer data) {
        super(data);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二叉树实现

package csdn.dreamzuora.tree;

import java.util.List;

/**
 * Title: 树接口
 * Description:
 *
 * @version 1.0
 * @author: weijie
 * @date: 2020/10/16 14:56
 */
public interface Tree<T,E> {

    /**
     * 构建树
     * @param dataList
     */
     void createTree(List<T> dataList);

    /**
     * 添加节点
     * @param data
     */
    E addNode(E tree, T data);

    /**
     * 删除节点
     * @param tree
     * @param node
     */
    void deleteNode(E tree, E node);

    /**
     * 前序遍历:根节点->左节点->右节点
     */
    void preOrder(List<T> list, E node);

    /**
     * 中序遍历：左节点->根节点->右节点
     * @return
     */
    void inOrder(List<T> list, E node);

    /**
     * 后序遍历：左节点->右节点->根节点
     */
    void laOrder(List<T> list, E node);

    /**
     * 广度优先遍历：层序遍历
     * @param list
     * @param node
     */
    void bfs(List<T> list, E node);

}

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

package csdn.dreamzuora.tree;

import java.io.Serializable;
import java.util.List;

/**
 * Title: 二叉树抽象类
 * Description:
 *
 * @version 1.0
 * @author: weijie
 * @date: 2020/10/16 14:57
 */
public abstract class AbstractTree<T, E> implements Tree<T, E>, Serializable {

    private static final long serialVersionUID = -8046156919125106629L;

    /**
     * 根节点
     */
    E root;

    @Override
    public void createTree(List<T> dataList) {
        for (T data : dataList){
            root = addNode(root, data);
        }
    }


}

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

package csdn.dreamzuora.tree;

import java.util.LinkedList;
import java.util.List;

/**
 * Title: 二叉树查找树
 * Description:
 *
 * @version 1.0
 * @author: weijie
 * @date: 2020/10/16 14:54
 */
public class BinaryTree extends AbstractTree<Integer, BinaryNode>{


    @Override
    public BinaryNode addNode(BinaryNode node, Integer data) {
        if (node == null){
             return new BinaryNode(data);
        }

        if (node.data > data){
            node.left = addNode(node.left, data);
        }else if (node.data < data){
            node.right = addNode(node.right, data);
        }else {
            node.data = data;
        }

        return node;
    }

    @Override
    public void deleteNode(BinaryNode tree, BinaryNode node) {

    }

    @Override
    public void preOrder(List<Integer> list, BinaryNode node) {
        if (node == null){
            return;
        }
        list.add(node.data);
        preOrder(list, node.left);
        preOrder(list, node.right);

    }

    @Override
    public void inOrder(List<Integer> list, BinaryNode node) {
        if (node == null){
            return;
        }
        inOrder(list, node.left);
        list.add(node.data);
        inOrder(list, node.right);
    }

    @Override
    public void laOrder(List<Integer> list, BinaryNode node) {
        if (node == null){
            return;
        }
        laOrder(list, node.left);
        laOrder(list, node.right);
        list.add(node.data);
    }

    @Override
    public void bfs(List<Integer> list, BinaryNode node) {
        if (node == null){
            return;
        }
        LinkedList<BinaryNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()){
            BinaryNode child = queue.poll();
            list.add(child.data);
            if (child.left != null){
                queue.offer(child.left);
            }
            if (child.right != null){
                queue.offer(child.right);
            }
        }

    }
}


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

单元测试

package csdn.dreamzuora.tree;

import org.junit.Before;
import org.junit.Test;
import org.junit.jupiter.api.Assertions;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import static org.junit.Assert.*;

/**
 * Title:
 * Description:
 *
 * @version 1.0
 * @author: weijie
 * @date: 2020/10/19 14:47
 */
public class BinaryTreeTest {

    BinaryTree binaryTree = new BinaryTree();

    @Before
    public void createTree(){
        List<Integer> list = Arrays.asList(5, 4, 7, 2, 3, 6, 8);
        binaryTree.createTree(list);
    }

    @Test
    public void preOrder() {
        List<Integer> showList = new ArrayList<>();
        binaryTree.preOrder(showList, binaryTree.root);

        List<Integer> predictList = Arrays.asList(5, 4, 2, 3, 7, 6, 8);

        Assertions.assertEquals(predictList.toString(), showList.toString());
    }

    @Test
    public void inOrder() {
        List<Integer> showList = new ArrayList<>();
        binaryTree.inOrder(showList, binaryTree.root);

        List<Integer> predictList = Arrays.asList(2, 3, 4, 5, 6, 7, 8);

        Assertions.assertEquals(predictList.toString(), showList.toString());
    }

    @Test
    public void laOrder(){
        List<Integer> showList = new ArrayList<>();
        binaryTree.laOrder(showList, binaryTree.root);

        List<Integer> predictList = Arrays.asList(3, 2, 4, 6, 8, 7, 5);
        Assertions.assertEquals(predictList.toString(), showList.toString());
    }

    @Test
    public void bfs(){
        List<Integer> showList = new ArrayList<>();
        binaryTree.bfs(showList, binaryTree.root);

        List<Integer> predictList = Arrays.asList(5, 4, 7, 2, 6, 8, 3);
        Assertions.assertEquals(predictList.toString(), showList.toString());
    }
}
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