手动实现 基础二叉树的 增删查 功能

1定义模型类 需要实现比较方法

    static class Mode implements Comparable {

        int id;

        String info;

        public Mode(int id) {
            this.id = id;
            info = id + ":" + System.currentTimeMillis();
        }

        public int getId() {
            return id;
        }

        public void setId(int id) {
            this.id = id;
        }

        public String getInfo() {
            return info;
        }

        public void setInfo(String info) {
            this.info = info;
        }

        @Override
        public int compareTo(Mode o) {

            return id - o.id;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Mode mode = (Mode) o;
            return id == mode.id;
        }

        @Override
        public int hashCode() {
            return Objects.hash(id);
        }

        @Override
        public String toString() {
            return "Mode{" +
                    "id=" + id +
                    ", info='" + info + ''' +
                    '}';
        }
    }

2 核心二叉树增删查逻辑实现 修改操作 这个可以复用 删除和新增的方法 

    static class Tree> {
        public Tree(T data) {
            this.data = data;
        }

        // 当前节点数据
        T data;

        public T getData() {
            return data;
        }

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

        public Tree getLeftData() {
            return leftData;
        }

        public void setLeftData(Tree leftData) {
            this.leftData = leftData;
        }

        public Tree getRightData() {
            return rightData;
        }

        public void setRightData(Tree rightData) {
            this.rightData = rightData;
        }

        // 父节点指针
        Tree parentData;

        // 左子节点指针
        Tree leftData;

        // 右子节点指针
        Tree rightData;


        void add(Tree mode) {
            if (mode == null) {
                throw new NullPointerException();
            }

            if (mode.data.compareTo(data) > 0) {
                if (rightData == null) {
                    rightData = mode;
                    rightData.parentData = this;
                } else {
                    rightData.add(mode);
                }
            } else {
                if (leftData == null) {
                    leftData = mode;
                    leftData.parentData = this;
                } else {
                    leftData.add(mode);
                }
            }
        }

        @Override
        public String toString() {
            return "Mode{" +
                    "data=" + data.toString() +
                    ", leftData=" + (leftData == null ? "null" : leftData.toString()) +
                    ", rightData=" + (rightData == null ? "null" : rightData.toString()) +
                    '}';
        }

        private static int find;

        public Tree find(Tree mode) {
            if (mode == null) {
                throw new NullPointerException();
            }
            find++;
            if (mode.data.equals(data)) {
                System.out.println("寻找了 " + find + "层");
                find = 0;
                return this;
            }
            if (mode.data.compareTo(data) > 0) {
                if (rightData != null) {
                    return rightData.find(mode);
                }
            } else {
                if (leftData != null) {
                    return leftData.find(mode);
                }
            }
            throw new NullPointerException();
        }

        
        public void del(Tree delTree) {

            Tree findTree = find(delTree);

            //没有子节点
            if (findTree.leftData == null && findTree.rightData == null) {
                if (findTree.parentData.leftData == findTree) {
                    findTree.parentData.leftData = null;
                }
                if (findTree.parentData.rightData == findTree) {
                    findTree.parentData.rightData = null;
                }
            }

            //只有一个子节点
            if (findTree.leftData != null && findTree.rightData == null) {
                //总是相反的节点
//                if (findTree.parentData.rightData == findTree)
                findTree.parentData.rightData = findTree.leftData;
//                if (findTree.parentData.leftData == findTree)
//                    findTree.parentData.leftData = findTree.leftData;
            }
            if (findTree.leftData == null && findTree.rightData != null) {
//                if (findTree.parentData.rightData == findTree)
//                    findTree.parentData.rightData = findTree.rightData;
//                if (findTree.parentData.leftData == findTree)
                findTree.parentData.leftData = findTree.rightData;
            }

            // 有两个子节点
            if (findTree.leftData != null && findTree.rightData != null) {
                // 左节点的 最右最子节点  或者相反方向 这里可优化成动态平衡树
                Tree temp = findTree.leftData;
                while (temp.rightData != null) {
                    temp = temp.rightData;
                }
                // 如果是根节点
                if (findTree.parentData == null) {
                    findTree.data = temp.data;
                } else {
                    if (findTree.parentData.rightData == findTree)
                        findTree.parentData.rightData.data = temp.data;
                    if (findTree.parentData.leftData == findTree)
                        findTree.parentData.leftData.data = temp.data;
                }
                //删除节点
                temp.parentData.rightData = null;

            }

        }


    }

3 测试

    public static void main(String[] args) {
        Tree mode = new Tree<>(new Mode(5));

        mode.add(new Tree<>(new Mode(1)));
        mode.add(new Tree<>(new Mode(10)));
        mode.add(new Tree<>(new Mode(2)));
        mode.add(new Tree<>(new Mode(9)));

        System.out.println(JSONObject.toJSONString(mode));
        try {
            mode.del(new Tree<>(new Mode(5)));
        } catch (NullPointerException nullPointerException) {
            System.out.println("null");
        }
        System.out.println(JSONObject.toJSONString(mode));


    }

4 结果

{
  "data": {
    "id": 2,
    "info": "2:1650525530080"
  },
  "leftData": {
    "data": {
      "id": 1,
      "info": "1:1650525530080"
    }
  },
  "rightData": {
    "data": {
      "id": 10,
      "info": "10:1650525530080"
    },
    "leftData": {
      "data": {
        "id": 9,
        "info": "9:1650525530080"
      }
    }
  }
}

{
  "data": {
    "id": 5,
    "info": "5:1650524279169"
  },
  "leftData": {
    "data": {
      "id": 1,
      "info": "1:1650524279179"
    },
    "rightData": {
      "data": {
        "id": 2,
        "info": "2:1650524279179"
      }
    }
  },
  "rightData": {
    "data": {
      "id": 10,
      "info": "10:1650524279179"
    },
    "leftData": {
      "data": {
        "id": 9,
        "info": "9:1650524279179"
      }
    }
  }
}