有序二叉树的增删改查（源代码讲解）

有序二叉树的相关实体类

TreeNode类

二叉树结点类，包含三个属性：value，leftChild，rightChild

有序二叉树类就包括这样一个根节点

剩下的getter和setter方法，有参无参构造，toString方法都是老生长谈，在这里略过不表

public class TreeNode {

    private int value;

    private TreeNode LeftChild;

    private TreeNode rightChild;

    public TreeNode(int value, TreeNode leftChild, TreeNode rightChild) {
        this.value = value;
        LeftChild = leftChild;
        this.rightChild = rightChild;
    }

    public TreeNode() {

    }


    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "value=" + value +
                ", LeftChild=" + LeftChild +
                ", rightChild=" + rightChild +
                '}';
    }

    public TreeNode getLeftChild() {
        return LeftChild;
    }

    public void setLeftChild(TreeNode leftChild) {
        LeftChild = leftChild;
    }

    public TreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(TreeNode rightChild) {
        this.rightChild = rightChild;
    }
}

有序二叉树类

有序二叉树只有一个属性：TreeNode root

public class BinarySearchTree {

    private TreeNode root;

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }
    
}

现在我们开始有序二叉树的CURD讲解

insert：有序二叉树的结点插入

比结点value值大，放右边；反之，放左边

注意结点的遍历，循环的终止条件

这个方法要放到BinarySearchTree实体类当中，作为成员方法

    // 插入
    public void insert(int value) {
    	// 创建新结点
        TreeNode newNode = new TreeNode();
        newNode.setValue(value);
        // 若根节点为null，则新插入的结点就是根节点
        if (root == null) {
            root = newNode;
            return;
        }
        // 根节点不为null
        // index拷贝root，作为查询指针
        TreeNode index = root;
        // pre作为index的parent存在
        TreeNode pre = null;
        while (index != null) {
            if (value > index.getValue()) {
                pre = index;
                index = index.getRightChild();
            } else {
                pre = index;
                index = index.getLeftChild();
            }
        }
        // 此时pre指针指向的位置就是应该插入的位置，比较大小
        if (value > pre.getValue()) {
            pre.setRightChild(newNode);
        } else {
            pre.setLeftChild(newNode);
        }
    }

demo

public class TreeTest {

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setRoot(new TreeNode(14, null, null));
        tree.insert(5);
        tree.insert(20);
        tree.insert(4);
        tree.insert(8);
        tree.insert(7);
        tree.insert(9);
        tree.insert(17);
        tree.insert(22);
        tree.insert(15);
        tree.insert(19);
        System.out.println(tree.getRoot());
    }
}

输出结果：

query：有序二叉树的查询

遍历查询

时间复杂度O(n)，其实就是全部结点都访问一遍来查询

二叉树的遍历

根据遍历方式优先级的不同，可以分为深度优先遍历（DFS）和广度优先遍历（BFS）

深度优先遍历

先序遍历（根左右，DLR），中序遍历（左根右，LDR）和后序遍历（左右根，LRD）

以上三种遍历，是深度优先遍历的三种形式，他们都是深度优先的

这里的D是data的意思，理解成父节点即可

这三种遍历基本都是使用递归完成，代码清晰而且很好理解，使用非递归的方式（循环+栈）也可以，在这里不做展示

先序遍历

    public void beforeSearch(TreeNode treeNode) { // DLR
        // 根左右

        // 先访问根节点，打印
        if (treeNode == null) {
            return;
        }
        // 打印根节点
        System.out.println(treeNode.getValue());
        // 再访问到最深的左结点，不打印
        beforeSearch(treeNode.getLeftChild());
        // 最后访问到最深的右结点，不打印
        beforeSearch(treeNode.getRightChild());

    }

demo

public class TreeTest {

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setRoot(new TreeNode(14, null, null));
        tree.insert(5);
        tree.insert(20);
        tree.insert(4);
        tree.insert(8);
        tree.insert(7);
        tree.insert(9);
        tree.insert(17);
        tree.insert(22);
        tree.insert(15);
        tree.insert(19);
        System.out.println("=============");
        tree.beforeSearch(tree.getRoot());
    }
}

运行结果

中序遍历

    public void middleSearch(TreeNode treeNode) {// LDR

        // 左根右
        if (treeNode == null) {
            return;
        }
        // 只有碰到左结点才会打印
        middleSearch(treeNode.getLeftChild());
        System.out.println(treeNode.getValue());
        middleSearch(treeNode.getRightChild());

    }

demo

public class TreeTest {
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setRoot(new TreeNode(14, null, null));
        tree.insert(5);
        tree.insert(20);
        tree.insert(4);
        tree.insert(8);
        tree.insert(7);
        tree.insert(9);
        tree.insert(17);
        tree.insert(22);
        tree.insert(15);
        tree.insert(19);
        System.out.println("=============");
        tree.middleSearch(tree.getRoot());
     }
}

运行结果

我们可以发现，有序二叉树中序遍历的结果，实际上就是有序二叉树从小到大排列的结果

后序遍历

    public void afterSearch(TreeNode treeNode) {// LRD
        //左右根
        if (treeNode == null) {
            return;
        }
        afterSearch(treeNode.getLeftChild());
        afterSearch(treeNode.getRightChild());
        System.out.println(treeNode.getValue());
    }

demo

public class TreeTest {

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setRoot(new TreeNode(14, null, null));
        tree.insert(5);
        tree.insert(20);
        tree.insert(4);
        tree.insert(8);
        tree.insert(7);
        tree.insert(9);
        tree.insert(17);
        tree.insert(22);
        tree.insert(15);
        tree.insert(19);
        System.out.println("=============");
        tree.afterSearch(tree.getRoot());
   }
}

广度优秀遍历（BFS）

BFS，BreadthFirstSearch,广度优先遍历, 需要队列来辅助实现

队列的存取特点与栈相反，先进先出FIFO

public void bfs(TreeNode treeNode) {
		// 定义队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 树为空直接返回
        if (treeNode == null) {
            return;
        }
        // 首先将根节点放入队列
        queue.add(treeNode);
        while (!queue.isEmpty()) {
            // 队列末尾节点出列
            treeNode = queue.pop();
            System.out.println(treeNode.getValue());
            // 左右结点放入队列
            if (treeNode.getLeftChild() != null) {
                queue.add(treeNode.getLeftChild());
            }
            if (treeNode.getRightChild() != null) {
                queue.add(treeNode.getRightChild());
            }
        }
    }

运行结果：

二分查询

时间复杂度最好O(logn)，前提是二叉树有序，而且相对平衡（否则会退化成单链表）

没什么可说的，比当前结点值大就向右遍历，反之则向左遍历

 // 二分查找
    public TreeNode binarySearch(TreeNode treeNode, int val) {
		// 复制根节点指针    		
        TreeNode index = treeNode;
        while (index != null) {
            if (val == index.getValue()) {
                System.out.println(val + "找到了");
                return index;	
            } else if (val > index.getValue()) {
                index = index.getRightChild();
            } else if (val < index.getValue()) {
                index = index.getLeftChild();
            }
        }
        return null;
    }

demo

public class TreeTest {

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setRoot(new TreeNode(14, null, null));
        tree.insert(5);
        tree.insert(20);
        tree.insert(4);
        tree.insert(8);
        tree.insert(7);
        tree.insert(9);
        tree.insert(17);
        tree.insert(22);
        tree.insert(15);
        tree.insert(19);
//         二分查找
        System.out.println(tree.binarySearch(tree.getRoot(), 15));
    }
}

运行结果

update：有序二叉树的编辑

有序二叉树无法直接编辑，因为编辑前后要保证有序二叉树的性质不变

所以编辑变成了删除+插入

delete：有序二叉树的删除

有序二叉树的删除操做很复杂，我们不是直接删除找到的结点，而是将其与叶子结点交换，然后删除交换后的叶子结点

如果是根节点，不允许删除；
如果是叶子结点，直接删除；
如果是中间的结点，就需要交换+删除；

这里的交换也是大有讲究

如图所示

假设要删除结点8，我们需要找一个结点与结点8交换，然后将交换后的结点删除，要找哪个结点呢？

我们需要明白结点8的性质：比5大，比14小，我们需要重新找到一个这样的结点来替换结点8

比14小好说，只要从根节点的左子树部分找即可

比5大要怎么满足？

显然，要从结点8的右子树去寻找，右子树的每一个结点都比8大，所以肯定也比5大

但是具体是哪一个呢？

我们发现，这样的结点交换之后，依然需要满足有序二叉树的性质，如果交换的不是叶子结点，那么后续还需要新的交换

如果交换叶子节点，那么交换就会变得非常简单

结论

要删除的结点是父节点的左孩子时，就要去左孩子所在的左子树中寻找最右叶子结点去替换要删除结点；如果左子树不存在右孩子（比如只有左孩子），则直接将祖孙连接
要删除的结点是父节点的右孩子时，就要去右孩子所在的右子树中寻找最左叶子结点去替换要删除结点；如果右子树不存在左孩子（比如只有右孩子），则直接将祖孙连接

代码

// 删除: 根节点不是叶子结点的情况下不允许删除/删除叶子结点/其他结点的删除
    // 1. 先遍历找到结点位置，
    // 2. 然后判断是否存在父节点
    // 3. 确定要删除的结点是左子树还是右子树
    // 4. 根据第三步的情况删除（左子树则parent.setLeftChild(null);右子树则parent.setRightChild(null)）
    public void delete(TreeNode treeNode, int val) {
    	// 为空直接返回
        if (treeNode == null) {
            return;
        }
        // 指针拷贝
        TreeNode index = treeNode;
        TreeNode parent = null;
        // 查询要删除的结点
        while (index != null) {
            if (val == index.getValue()) {
                System.out.println(val + "找到了");
                break;
            } else if (val > index.getValue()) {
                parent = index;
                index = index.getRightChild();
            } else if (val < index.getValue()) {
                parent = index;
                index = index.getLeftChild();
            }
        }
        // 找不到要删除的结点，直接返回
        if (index == null) {
            System.out.println("有序二叉树中无值为" + val + "的结点");
            return;
        }
        // 要删除的结点是根节点，直接返回
        if (parent == null) {
            System.out.println("根节点不允许删除");
            return;
        }

        // 如果index是parent的左子树，那么就去index子树当中搜索最右结点（最大结点）；若index是parent的右子树，就去找index子树中最左结点（最小结点）
		
        // 跳出循环后，index指向要删除的结点，parent指向删除结点的父节点
        // 分情况讨论
        // 情况1：index是叶子结点，直接删除
        if (index.getRightChild() == null && index.getLeftChild() == null) {
            parent.setLeftChild(null);
            return;
        }
        // 判断要删除结点的类型：左孩子还是右孩子        
        if (index.getValue() < parent.getValue()) {
            // 情况2：index不是叶子节点，但是右子树为空，祖孙连接
            if (index.getRightChild() == null) {
                parent.setLeftChild(index.getLeftChild());
                return;
            }
            // 情况3：index不是叶子节点,右子树不为空，遍历查询最右结点
   			// 指针拷贝，标记叶子节点和叶子结点的父节点
        	TreeNode query = index;
        	TreeNode queryParent = parent;
            while (query.getRightChild() != null) {
                // 查询最右结点
                queryParent = query;
                query = query.getRightChild();
            }
            // 数值交换,删除叶子节点
            index.setValue(query.getValue());
            queryParent.setRightChild(null);
        } else {
           	// 情况2：index不是叶子节点，但是左子树为空，祖孙连接
            if (index.getLeftChild() == null) {
                parent.setRightChild(index.getRightChild());
            }
            // 情况3：index不是叶子节点,且左子树不为空，遍历查询最左结点
            // 指针拷贝，标记叶子节点和叶子结点的父节点
            TreeNode query = index;
            TreeNode queryParent = parent;
            while (query.getLeftChild() != null) {
                // 查询最左结点
                queryParent = query;
                query = query.getLeftChild();
            }
            // 数值交换,删除叶子节点
            index.setValue(query.getValue());
            queryParent.setLeftChild(null);
        }
    }

demo

public class TreeTest {

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setRoot(new TreeNode(14, null, null));
        tree.insert(5);
        tree.insert(20);
        tree.insert(4);
        tree.insert(8);
        tree.insert(7);
        tree.insert(9);
        tree.insert(17);
        tree.insert(22);
        tree.insert(15);
        tree.insert(19);


        tree.delete(tree.getRoot(), 14);
        tree.delete(tree.getRoot(), 100);

        tree.delete(tree.getRoot(), 5);
        System.out.println(tree.getRoot());

    }
}

运行结果：