二叉排序树的插入和删除

比眉伴天荒 2022-08-04 05:18 173阅读 0赞

# 插入 #

递归的寻找插入的位置。

public static TreeNode Insert(int x, TreeNode t) {
    
            if (t == null) {
                TreeNode n = new TreeNode(x);
                n.left = null;
                n.right = null;
                t = n;
            }
    
            else if (x < t.val)
                t.left = Insert(x, t.left);
            else if (x > t.val)
                t.right = Insert(x, t.right);
            // 如果x已经在tree中了，则什么也不做；
    
            return t;
        }

# 删除 #

*  节点是一个叶节点，直接删除；
 *  节点有一个儿子，可以在其父节点调整指针绕过该节点被删除；
 *  节点有两个儿子，用其右子树中的最小数据代替该节点的数据并递归的删除这个节点。

public static TreeNode Delete(int x, TreeNode t) {
    
            if (t == null) {
                System.out.println("element is null");
            }
    
            else if (x < t.val)
                t.left = Delete(x, t.left);
            else if (x > t.val)
                t.right = Delete(x, t.right);
    
            //找到节点并有左右两个子树
            else if (t.left != null && t.right != null) {
                TreeNode temp = FindMin(t.right);
                t.val = temp.val;
                t.right = Delete(t.val, t.right);
            } 
    
            //有0个或1个子树的时候
            else {
                TreeNode temp = t;
                if (t.left == null)   //同时处理0个子树和只有右子树的情形；
                    t = t.right;
                else if (t.right == null)
                    t = t.left;
            }
            return t;
        }
    
        public static TreeNode FindMin(TreeNode t) {
            if (t.left != null)
                return FindMin(t.left);
            else
                return t;
        }

# 例子 #

class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode(int x) {
            val = x;
        }
    }
    public class BinaryTree {
    
        public static void main(String[] args) {
    
            TreeNode tree = CreateTree();
            dfs(tree);
    
    // 插入
             TreeNode t = Insert(5, tree);
             dfs(t);
    // 删除
            t = Delete(2, tree);
            dfs(t);
    
        }
    
        public static TreeNode Delete(int x, TreeNode t) {
    
            if (t == null) {
                System.out.println("element is null");
            }
    
            else if (x < t.val)
                t.left = Delete(x, t.left);
            else if (x > t.val)
                t.right = Delete(x, t.right);
    
            //找到节点并有左右两个子树
            else if (t.left != null && t.right != null) {
                TreeNode temp = FindMin(t.right);
                t.val = temp.val;
                t.right = Delete(t.val, t.right);
            } 
    
            //有0个或1个子树的时候
            else {
                TreeNode temp = t;
                if (t.left == null)   //同时处理0个子树和只有右子树的情形；
                    t = t.right;
                else if (t.right == null)
                    t = t.left;
            }
            return t;
        }
    
        public static TreeNode FindMin(TreeNode t) {
            if (t.left != null)
                return FindMin(t.left);
            else
                return t;
    
        }
    
    
        public static TreeNode Insert(int x, TreeNode t) {
    
            if (t == null) {
                TreeNode n = new TreeNode(x);
                n.left = null;
                n.right = null;
                t = n;
            }
    
            else if (x < t.val)
                t.left = Insert(x, t.left);
            else if (x > t.val)
                t.right = Insert(x, t.right);
            // 如果x已经在tree中了，则什么也不做；
    
            return t;
        }
    
        public static TreeNode CreateTree() {
    
            TreeNode t1 = new TreeNode(6);
            TreeNode t2 = new TreeNode(2);
            TreeNode t3 = new TreeNode(8);
            TreeNode t4 = new TreeNode(1);
            TreeNode t5 = new TreeNode(4);
            TreeNode t6 = new TreeNode(3);
    
            t1.left = t2;
            t1.right = t3;
            t2.left = t4;
            t2.right = t5;
            t5.left = t6;
    
            return t1;
        }
    
        // 深度优先遍历
        public static void dfs(TreeNode root) {
            if (root == null) {
                return;
            }
    
            System.out.println(root.val);
    
            dfs(root.left);
            dfs(root.right);
        }
    }

![这里写图片描述][20150818210317226]

[20150818210317226]: /images/20220731/6595874eff4e4a219c181bcb16fcb0c1.png