Java数据结构和算法：二叉树

傷城~ 2022-07-13 13:21 173阅读 0赞

## 二叉树的实现 ##

数组查询快，增删慢；链表增删快，查询慢；二叉树查询和增删都有很好的性能

package com.itheiam62;
    
    /** * @描述 中序遍历是有序的二叉树(不重复) * */
    public class MyTree { 
        private Node    root;   // 根节点
    
        private class Node { 
            Node    parrent;    // 父节点
            Node    left;       // 左儿子
            Node    right;      // 右儿子
            Object  data;
    
            public Node(Object data) {
                this.data = data;
            }
        }
    
        /** * @param data * 传递的数据 * @return 父节点的值 */
        private Node findParrent(Object data, Node currentNode) {
            // 从根节点找
            Node temp = currentNode;
            Node parrent = currentNode;
            // 循环找
            while (temp != null) {
                parrent = temp;
                // 比较
                if (compare(data, temp.data)) {
                    // data 大于 当前节点
                    temp = temp.right;
                } else {
                    // data 小于 当前节点
                    temp = temp.left;
                }
            }
    
            return parrent;
        }
    
        public void update(Object oldData,Object newData){
            remove(oldData);
            add(newData);
        }
    
        /** * 添加数据 * * @param data * 要添加的数据 */
        public void add(Object data) {
            // 判断该数据是否存在
            if (contains(data))
                return;
            // 1.把数据放到节点中
            Node node = new Node(data);
            // 2.把节点链接到二叉树中
            // 是否有根节点
            if (root == null) {
                root = node;// 保存到根节点中
            } else {
                // 找位置,找父节点,比较父节点的值，小左边 大右边
                Node parrent = findParrent(data, root);
                // 设置新增节点的父节点
                node.parrent = parrent;
                // 比较
                if (compare(data, parrent.data)) {
                    // 自己比父节点大
                    parrent.right = node;
                } else {
                    // 自己比父节点小
                    parrent.left = node;
                }
            }
        }
    
        /** * @param data * @return 是否包含该数据 */
        public boolean contains(Object data) {
    
            return null != find(data);
        }
    
        private Node find(Object data) {
            Node temp = root;// 从根节点找
            while (temp != null) {
                // 判断数据
                if (temp.data.equals(data)
                        && temp.data.hashCode() == data.hashCode()) {
                    // 找到数据
                    break;
                } else if (compare(data, temp.data)) {
                    // true data > temp
                    // 从右边找
                    temp = temp.right;
    
                } else {
                    // false data < temp
                    // 从坐标边找
                    temp = temp.left;
                }
            }
            return temp;
        }
    
        public void remove(Object data) {
            // 1. 查找数据是否存在
            Node temp = find(data);
    
            // 2. 存在：找到数据节点
            if (temp != null) {
                // 存在
                // 3. 删除节点
    
                // 1. 根节点
                if (temp == root) {
    
                    // 11 没有儿子
                    if (temp.left == null && temp.right == null) {
                        root = null;
                    } else if (temp.right == null) {
                        root = root.left;
                        root.parrent = null;
                        // 12 只有左儿子
                    } else if (temp.left == null) {
                        // 13 只有右儿子
                        root = root.right;
                        root.parrent = null;
                    } else {
                        // 14 两个儿子都有
                        // 保留左儿子
                        Node left = getLeft(temp);
                        // left成为新的根节点
                        root = left;
                        left.parrent = null;
                    }
    
                } else {
       // 2. 非根节点
    
                    if (temp.left == null && temp.right == null) {
                        // 21 没有儿子
                        if (compare(temp.data, temp.parrent.data)) {
                            //在父节点右边
                            temp.parrent.right = null;
                        } else {
                            //在父节点左边
                            temp.parrent.left = null;
                        }
                    } else if (temp.right == null) {
                        // 22 只有左儿子
                        if (compare(temp.data, temp.parrent.data)) {
                            //在父节点右边
                            temp.parrent.right = temp.left;
                            temp.left.parrent = temp.parrent;
                        } else {
                            //在父节点左边
                            temp.parrent.left = temp.left;
                            temp.left.parrent = temp.parrent;
                        }
                    } else if (temp.left == null) {
                        // 23 只有右儿子
                        if (compare(temp.data, temp.parrent.data)) {
                            //在父节点右边
                            temp.parrent.right = temp.right;
                            temp.right.parrent = temp.parrent;
                        } else {
                            //在父节点左边
                            temp.parrent.left = temp.right;
                            temp.right.parrent = temp.parrent;
                        }
                    } else {
                        // 24 两个儿子都有
                        Node left = getLeft(temp);
                        //上面还有父节点（爷爷）
                        if (compare(left.data, temp.parrent.data)) {
                            //比爷爷节点大
                            temp.parrent.right = left;
                            left.parrent = temp.parrent;
                        } else  {
                            //比爷爷节点小
                            temp.parrent.left = left;
                            left.parrent = temp.parrent;
                        }
                    }
    
                }
            }
    
        }
    
        /** * @param node * 要删除的节点 * @return 左儿子节点 */
        private Node getLeft(Node node) {
            // 保留左儿子
            Node left = node.left;
            // 处理右节点
            Node rightNewParrent = findParrent(node.right.data, left);
            rightNewParrent.right = node.right;// 把删除节点的右节点放到删除节点的左儿子最右边
            node.right.parrent = rightNewParrent;
            return left;
        }
    
        /** * @param o1 * 第一个值 * @param o2 * 第二个值 * @return 如果o1 大于 o2 返回true 否则false */
        public boolean compare(Object o1, Object o2) {
            boolean res = false;
    
            // 判断o1 有没有实现比较器
            if (o1 instanceof Comparable) {
                Comparable c1 = (Comparable) o1;
                Comparable c2 = (Comparable) o2;
                if (c1.compareTo(c2) > 0) {
                    res = true;
                } else {
                    // 默认值就是false
                }
            } else {
       // 传递的对象没有比较器
                res = o1.toString().compareTo(o2.toString()) > 0 ? true : false;
            }
            return res;
        }
    
        // 递归打印
        public void print() {
            print(root);
        }
    
        public void print(Node node) {
            if (node == null) {
                return;
            } else {
                // 遍历 中序
                print(node.left);
                System.out.println(node.data + ",");
                print(node.right);
            }
        }
    
    }

## 从currentNode节点开始查找data的父节点 ##

private Node findParrent(Object data, Node currentNode) {
            // 从根节点找
            Node temp = currentNode;
            Node parrent = currentNode;
            // 循环找
            while (temp != null) {
                parrent = temp;
                // 比较
                if (compare(data, temp.data)) {
                    // data 大于 当前节点
                    temp = temp.right;
                } else {
                    // data 小于 当前节点
                    temp = temp.left;
                }
            }
    
            return parrent;
        }

![二叉树][SouthEast]

## 删除节点，该节点有左右孩子 ##

可以把右孩子添加到左孩子的右边，或者把左孩子添加到右孩子的左边

//node 要删除的节点
    private Node getLeft(Node node) {
            // 保留左儿子
            Node left = node.left;
            // 处理右节点
            Node rightNewParrent = findParrent(node.right.data, left);
            rightNewParrent.right = node.right;// 把删除节点的右节点放到删除节点的左儿子最右边
            node.right.parrent = rightNewParrent;
            return left;
        }

![二叉树][SouthEast 1]

## 删除节点 ##

public void remove(Object data) {
            // 1. 查找数据是否存在
            Node temp = find(data);
    
            // 2. 存在：找到数据节点
            if (temp != null) {
                // 存在
                // 3. 删除节点
    
                // 1. 根节点
                if (temp == root) {
    
                    // 11 没有儿子
                    if (temp.left == null && temp.right == null) {
                        root = null;
                    } else if (temp.right == null) {
                        root = root.left;
                        root.parrent = null;
                        // 12 只有左儿子
                    } else if (temp.left == null) {
                        // 13 只有右儿子
                        root = root.right;
                        root.parrent = null;
                    } else {
                        // 14 两个儿子都有
                        // 保留左儿子
                        Node left = getLeft(temp);
                        // left成为新的根节点
                        root = left;
                        left.parrent = null;
                    }
    
                } else {
       // 2. 非根节点
    
                    if (temp.left == null && temp.right == null) {
                        // 21 没有儿子
                        if (compare(temp.data, temp.parrent.data)) {
                            //在父节点右边
                            temp.parrent.right = null;
                        } else {
                            //在父节点左边
                            temp.parrent.left = null;
                        }
                    } else if (temp.right == null) {
                        // 22 只有左儿子
                        if (compare(temp.data, temp.parrent.data)) {
                            //在父节点右边
                            temp.parrent.right = temp.left;
                            temp.left.parrent = temp.parrent;
                        } else {
                            //在父节点左边
                            temp.parrent.left = temp.left;
                            temp.left.parrent = temp.parrent;
                        }
                    } else if (temp.left == null) {
                        // 23 只有右儿子
                        if (compare(temp.data, temp.parrent.data)) {
                            //在父节点右边
                            temp.parrent.right = temp.right;
                            temp.right.parrent = temp.parrent;
                        } else {
                            //在父节点左边
                            temp.parrent.left = temp.right;
                            temp.right.parrent = temp.parrent;
                        }
                    } else {
                        // 24 两个儿子都有
                        Node left = getLeft(temp);
                        //上面还有父节点（爷爷）
                        if (compare(left.data, temp.parrent.data)) {
                            //比爷爷节点大
                            temp.parrent.right = left;
                            left.parrent = temp.parrent;
                        } else  {
                            //比爷爷节点小
                            temp.parrent.left = left;
                            left.parrent = temp.parrent;
                        }
                    }
                }
            }
        }

### 删除的节点非根节点，且右孩子为空 ###

else if (temp.right == null) {
        // 只有左儿子
        if (compare(temp.data, temp.parrent.data)) {
            //在父节点右边，下图中的23
            temp.parrent.right = temp.left;
            temp.left.parrent = temp.parrent;
        } else {
            //在父节点左边，下图中的50
            temp.parrent.left = temp.left;
            temp.left.parrent = temp.parrent;
        }
    }

![二叉树][SouthEast 2]

###  ###

else {
        // 两个儿子都有
        Node left = getLeft(temp);
        //上面还有父节点（爷爷）
        if (compare(left.data, temp.parrent.data)) {
            //比爷爷节点大，下图中的89
            temp.parrent.right = left;
            left.parrent = temp.parrent;
        } else  {
            //比爷爷节点小，下图中的45
            temp.parrent.left = left;
            left.parrent = temp.parrent;
        }
    }

![二叉树][SouthEast 3]

[SouthEast]: /images/20220713/118bc7fc41e74181a8c7d0207307e490.png
[SouthEast 1]: /images/20220713/5adba6a7004142b69c4aecdf562576ae.png
[SouthEast 2]: /images/20220713/b1fb070196f342278b2f43f64505681f.png
[SouthEast 3]: /images/20220713/ae34c93063a64012adf5484e9117a572.png