关于平衡二叉树的构建

清疚 2022-02-19 09:39 210阅读 0赞

## 构建平衡二叉树 ##

最近在玩数据结构搞到平衡二叉树部分觉得平衡二叉树的构建，分享一下自己的二叉树构建：

**首先是树的节点的构建：**
    
    public class BalanceNode {
    
        private int value;
    
        BalanceNode leftBalanceNode;
    
        BalanceNode rightBalanceNode;
    
        public BalanceNode(int value) {
    
            this.value = value;
    
        }
    
        public int getValue() {
            return value;
        }
    
        public void setValue(int value) {
            this.value = value;
        }
    
    
        public void add(BalanceNode balanceNode) {
    
            if (balanceNode == null) {
    
                return;
    
            }
            //如果添加的节点在左边
            if (balanceNode.value < this.value) {
    
    
                if (this.leftBalanceNode == null) {
    
                    this.leftBalanceNode = balanceNode;
    
                } else {
    
                    this.leftBalanceNode.add(balanceNode);
    
                }
                //添加的节点在右边
            } else {
    
                if (this.rightBalanceNode == null) {
    
                    this.rightBalanceNode = balanceNode;
    
                } else {
    
                    this.rightBalanceNode.add(balanceNode);
    
                }
    
            }
    
            //判断是否平衡把树搞成平衡二叉树
            //首先是左边的比右边的高 搞成右旋转
            System.out.println(leftHeight()+"---------"+rightHeight());
    
            if (leftHeight() - rightHeight() >= 2) {
    
                //如果出现左子树的右子树比左子树的左子树要高 双旋转
    
                if (leftBalanceNode != null && leftBalanceNode.leftHeight() < leftBalanceNode.rightHeight()) {
    
                    //先让小左子树左旋转  然后让大左子树右旋转
    
                    leftBalanceNode.leftRoate();
    
                    rightRoate();
    
    
                } else {
    
                    rightRoate();
                }
    
            }
    
            if (rightHeight() - leftHeight() >= 2) {
    
    
                if (rightBalanceNode != null && rightBalanceNode.leftHeight() > rightBalanceNode.rightHeight()) {
    
                    //先让小左子树左旋转  然后让大左子树右旋转
    
                    rightBalanceNode.rightRoate();
    
                    leftRoate();
    
    
                } else {
    
                    leftRoate();
                }
    
    
            }
    
    
        }
    
        //左旋转方法
        private void leftRoate() {
    
            BalanceNode node = new BalanceNode(this.value);
    
            node.leftBalanceNode = this.leftBalanceNode;
    
            node.rightBalanceNode = this.rightBalanceNode.leftBalanceNode;
    
            this.value = this.rightBalanceNode.value;
    
            this.rightBalanceNode = this.rightBalanceNode.rightBalanceNode;
    
            this.leftBalanceNode = node;
    
    
        }
    
        //右旋转方法
        private void rightRoate() {
    
    
            BalanceNode node = new BalanceNode(this.value);
    
            node.rightBalanceNode = this.rightBalanceNode;
    
            node.leftBalanceNode = this.leftBalanceNode.rightBalanceNode;
    
            this.value = this.leftBalanceNode.value;
    
            this.leftBalanceNode = this.leftBalanceNode.leftBalanceNode;
    
            this.rightBalanceNode = node;
    
        }
    
        //定义一个取树的高度的方法
    
        public int height() {
    
    
            return Math.max(leftBalanceNode == null ? 0 : leftBalanceNode.height(), rightBalanceNode == null ? 0 : rightBalanceNode.height())+ 1;
    
        }
    
        //获取左子树的高度
        public int leftHeight() {
    
            if (leftBalanceNode == null) {
    
                return 0;
            }
    
            return leftBalanceNode.height();
    
        }
        //获取右子树的高度
    
        public int rightHeight() {
    
            if (rightBalanceNode == null) {
    
                return 0;
            }
    
            return rightBalanceNode.height();
    
    
        }
    
    
        public void midlShow() {
    
    
            if (this.leftBalanceNode != null) {
                this.leftBalanceNode.midlShow();
            }
    
            System.out.println(this.value);
    
            if (this.rightBalanceNode != null) {
    
                this.rightBalanceNode.midlShow();
    
            }
    
        }
    
        public BalanceNode search(int value) {
    
            if (this.value == value) {
    
                return this;
    
            } else {
    
                if (this.value > value) {
    
                    //对左右为空进行判断
                    if (this.leftBalanceNode == null) {
    
                        return null;
                    }
    
                    return this.leftBalanceNode.search(value);
    
                } else {
    
                    if (this.rightBalanceNode == null) {
    
    
                        return null;
    
                    }
    
                    return this.rightBalanceNode.search(value);
    
                }
    
            }
    
        }
    
    **接下来是树的创建：**
    
    public class BalanceBinaryTree {
    
        private BalanceNode root;
    
    
        public void add(BalanceNode balanceNode) {
    
            if (root == null) {
    
                root = balanceNode;
            } else {
    
                root.add(balanceNode);
    
            }
    
        }
    
    
        public void midlShow() {
    
            if (root != null) {
                root.midlShow();
            }
    
        }
    
        public BalanceNode search(int value) {
    
            if (root == null) {
    
                return null;
    
            } else {
    
                return root.search(value);
            }
    
    
        }
    
        public void delete(int value) {
    
    
            if (root == null) {
    
                return;
            } else {
    
                BalanceNode t = search(value);
    
                if (t == null) {
    
    
                    return;
    
                } else {
    
                    BalanceNode target = searchParent(value);
    
                    // System.out.println(target.getValue());
    
                    if (target == null) {
    
                        return;
    
                    } else {
                        //判断如果被删除的节点为叶子节点
                        if (t.leftBalanceNode == null && t.rightBalanceNode == null) {
    
                            //如果被删除的节点为左节点
                            if (target.leftBalanceNode.getValue() == t.getValue()) {
    
                                target.leftBalanceNode = null;
                                //被删除的节点为右节点
                            } else {
    
                                target.rightBalanceNode = null;
    
                            }
    
                            //被删除节点有两个子树
    
                        } else if (t.leftBalanceNode != null && t.rightBalanceNode != null) {
    
    
                            int i = delmin(t.rightBalanceNode);
    
                            t.setValue(i);
    
    
                            //被删除节点有一个子树
                        } else {
                            //如果有一颗左子树
                            if (t.leftBalanceNode == target) {
    
                                //如果被删除的节点为左节点
                                if (target.leftBalanceNode.getValue() == t.getValue()) {
    
                                    target.leftBalanceNode = null;
                                    //被删除的节点为右节点
                                } else {
    
                                    target.rightBalanceNode = null;
    
                                }
    
                                //有一棵右子树
                            } else {
    
                                //如果被删除的节点为左节点
                                if (target.leftBalanceNode.getValue() == t.getValue()) {
    
                                    target.leftBalanceNode = null;
                                    //被删除的节点为右节点
                                } else {
    
                                    target.rightBalanceNode = null;
    
                                }
    
    
                            }
    
    
                        }
    
    
                    }
    
    
                }
    
            }
    
    
        }
    
        public BalanceNode searchParent(int value) {
    
            if (root == null) {
    
                return null;
    
            } else {
    
                return root.searchParent(value);
    
            }
    
        }
    
        private int delmin(BalanceNode balanceNode) {
    
            BalanceNode target = balanceNode;
    
            while (target.leftBalanceNode != null) {
    
                target = target.leftBalanceNode;
    
            }
    
            //递归调用删除方法
            delete(target.getValue());
    
            return target.getValue();
    
    
        }
    
    
        public int height() {
            return root.height();
        }
    
    
    这样就创建了一棵平衡二叉树，具体的测试方法就不展示了，可以自行造假数据然后测试。