二叉树java_测试二叉树java

最近因为search方法学习二叉树，看到https://blog.csdn.net/strivenoend/article/details/78449816#commentBox
这个博客很全，但有些地方还是有点问题。在上面的基础上做了些改变。
具体如下：
BinaryTreeNode.java 加入display字段，方便后面delete方法。

public class BinaryTreeNode{
    private int mData;
    private BinaryTreeNode mLeftChild;
    private BinaryTreeNode mRightChild;
    private boolean display;

    public BinaryTreeNode(int data){
        this.mData = data;
        this.display = true;
        //this.mLeftChild = leftChild;
        //this.mRightChild = rightChild;
    }

    public int getData(){
        return mData;
    }
    public void setData(int data){
        this.mData = data;
    }

    public BinaryTreeNode getLeftChild(){
        return mLeftChild;
    }
    public void setLeftChild(BinaryTreeNode leftChild){
        this.mLeftChild = leftChild;
    }

    public BinaryTreeNode getRightChild(){
        return this.mRightChild;
    }
    public void setRightChild(BinaryTreeNode rightChild){
        this.mRightChild = rightChild;
    }

    //是否删除
    public boolean isDelete(){
        return !this.display;
    }
    
    //删除状态
    public void hidden(){
        this.display = false;
    }

    //设置为未删除状态
    public void display(){
        this.display = true;
    }
}
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

BinaryTree.java
insert 方法，由于有可能要插入的节点是之前删除过的所以要判断下。

    public void insertChild(BinaryTreeNode child){
        checkTreeEmpty();
        insertChild(mRoot,child);
    }
    private void insertChild(BinaryTreeNode subRoot,BinaryTreeNode child){
        if(subRoot.getData() < child.getData()){
            if(subRoot.getRightChild() != null)
                insertChild(subRoot.getRightChild(),child);
            else
                subRoot.setRightChild(child);
        }
        else if(subRoot.getData() > child.getData())
        {
            if(subRoot.getLeftChild() != null)
                insertChild(subRoot.getLeftChild(),child);
            else
                subRoot.setLeftChild(child);
        }
        else{
            try{
            if(subRoot.isDelete()){
                subRoot.display();
            }
            else{
                throw new IllegalStateException("已经存在这个节点，不能重复插入");
                }
            }catch(IllegalStateException e){
                System.out.println("尝试添加重复数据失败");
            }
        }
    }
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

BinaryTree.java
delete方法，只是把相应的节点display设置为false,而不是真的删除节点。

    //删除节点
    public void delNode(BinaryTreeNode node){
      try{ if(node == null)
        throw new IllegalStateException("不能删除空节点");
     if( delNode(mRoot,node))
        System.out.println("删除节点成功");
     else
        System.out.println("删除节点失败");
      }catch(IllegalStateException e){
        System.out.println("空节点不能删除");
      }
    }
    private boolean delNode(BinaryTreeNode subRoot,BinaryTreeNode node){
       if(subRoot == null)
            return false ;
       if(subRoot.getData() == node.getData()){
            subRoot.hidden();
            return true;
       }
       else{
       if( delNode(subRoot.getLeftChild(),node)||
        delNode(subRoot.getRightChild(),node))
            return true;
        else
            return false;
       }
    }
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

BinaryTree.java
由于原博客里面的遍历方法只有三种遍历节点方法，而我们要遍历的是树不是节点。使用中序使所遍历的节点是排好序的。没有一个给外部使用的api所以加入以下方法：

    //遍历所有节点
    public void showNode(){
        if(mRoot == null)
            return;
        iteraterMediumOrder(mRoot);
    }
1
2
3
4
5
6

到这里就可以编写一个测试用例了，如下。
Main.java

public class Main{
    public static void main(String args[]){
       BinaryTreeNode node = new BinaryTreeNode(99);
       BinaryTree nRoot = new BinaryTree(node);

       node = new BinaryTreeNode(88);
       nRoot.insertChild(node);
       node = new BinaryTreeNode(443);
       nRoot.insertChild(node);
       node = new BinaryTreeNode(33);
       nRoot.insertChild(node);
       node = new BinaryTreeNode(999);
       nRoot.insertChild(node);
       node = new BinaryTreeNode(1);
       nRoot.insertChild(node);
       node = new BinaryTreeNode(44);
       nRoot.insertChild(node);
       node = new BinaryTreeNode(50);
       nRoot.insertChild(node);
       node = new BinaryTreeNode(33);
       nRoot.insertChild(node);
       node = new BinaryTreeNode(35);
       nRoot.insertChild(node);

       nRoot.showNode();
       System.out.println();
       node = new BinaryTreeNode(44);
       nRoot.delNode(node);
       node = new BinaryTreeNode(53);
       nRoot.delNode(node);
       node = new BinaryTreeNode(99);
       nRoot.delNode(node);
       nRoot.showNode();
       node = new BinaryTreeNode(44);
       nRoot.insertChild(node);
       System.out.println();
       nRoot.showNode();
    }
}
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

最后测试结果如下。

java Main

Data:1
Data:33
Data:35
Data:44
Data:50
Data:88
Data:99
Data:443
Data:999

删除节点成功
删除节点失败
删除节点成功
Data:1
Data:33
Data:35
Data:50
Data:88
Data:443
Data:999

Data:1
Data:33
Data:35
Data:44
Data:50
Data:88
Data:443
Data:999

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

到这里就结束了。
采用加入display字段的方法可以减少delete 的方法难度，让二叉树真正实现，插入、删除、搜索都高效、便捷。