树（3）

JusterZhu

发布于 2022-12-07 20:18:17

1650

发布于 2022-12-07 20:18:17

文章被收录于专栏：JusterZhu

二叉树-删除指定节点

以上一篇为基础来看看树中的删除。

问题

（1）如果删除的节点是叶子节点，则删除该节点。

（2）如果删除的节点是非叶子节点，则删除该子树。

（3）测试，删除5号叶子节点和3号子树。

分析

首先先处理，如果树是空树，如果只有一个节点，则等价于将二叉树置空。

1.因为我们的二叉树是单向的，所以我们是判断当前节点的子节点是否需要删除节点，而不能去判断当前这个结点是不是需要删除节点。

2.如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将this.Left = null; 并且就返回（结束递归删除）

3.如果当前节点的右子节点不为空，且左子节点就是要删除的节点，就将this.Right = null; 并且就返回（结束递归删除）

4.如果第2步和第3步都没有删除掉节点，那么就需要向左子树递归删除。

5.如果第4步没有成功删除节点，则应当向右子树递归删除

代码：

    public class TreeNode 
    {
        public int Id { get; set; }

        public string Name { get; set; }

        public TreeNode Left { get; set; }

        public TreeNode Right { get; set; }

        public TreeNode(int id,string name) 
        {
            this.Id = id;
            this.Name = name;
        }

        public override string ToString()
        {
            return $"TreeNode [id = { Id } , name ={ Name }]";
        }

        /// <summary>
        /// 前序遍历
        /// </summary>
        public void PreOrder()
        {
            Console.WriteLine(this);
            //递归向左子树前序遍历
            if (this.Left != null) 
            {
                this.Left.PreOrder();
            }
            //递归向右子树前序遍历
            if (this.Right != null)
            {
                this.Right.PreOrder();
            }
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        public void InfixOrder() 
        {
            //递归向左子树中序遍历
            if (this.Left != null)
            {
                this.Left.InfixOrder();
            }

            //输出父节点
            Console.WriteLine(this);

            //递归向右子树中序遍历

            if (this.Right != null)
            {
                this.Right.InfixOrder();
            }
        }

        /// <summary>
        /// 后续遍历
        /// </summary>
        public void PostOrder() 
        {
            if (this.Left != null)
            {
                this.Left.PreOrder();
            }

            if (this.Right != null)
            {
                this.Right.PreOrder();
            }

            Console.WriteLine(this);
        }

        /// <summary>
        /// 前序遍历查找
        /// </summary>
        /// <param name="id">根据id查找节点</param>
        /// <returns></returns>
        public TreeNode PreOrderSearch(int id)
        {
            Console.WriteLine("前序遍历查找" + DateTime.Now);
            //比较当前节点是不是
            if (this.Id == id)
            {
                return this;
            }
            //1.则判断当前节点的左子节点是否为空，如果不为空，则递归前序查找
            //2.如果左递归前序查找，找到节点，则返回
            TreeNode resNode = null;
            if (this.Left != null)
            {
                resNode = this.Left.PreOrderSearch(id);
            }

            //说明我们左子树找到
            if (resNode != null)
            {
                return resNode;
            }
            //左递归前序查找，找到站点，则返回，否则继续判断
            //当前的节点的右子节点是否为空，如果不为空，则继续向右递归前序查找。
            if (this.Right != null)
            {
                resNode = this.Right.PreOrderSearch(id);
            }
            return resNode;
        }

        //中序遍历查找
        public TreeNode InfixOrderSearch(int id) 
        {
            TreeNode resNode = null;
            if (this.Left != null)
            {
                resNode = this.Left.InfixOrderSearch(id);
            }

            if (resNode != null)
            {
                return resNode;
            }
            Console.WriteLine("中序遍历查找" + DateTime.Now);
            if (this.Id == id) 
            {
                return this;
            }

            if (this.Right != null)
            {
                resNode = this.Right.InfixOrderSearch(id);
            }

            return resNode;
        }

        //后序遍历查找
        public TreeNode PostOrderSearch(int id) 
        {
            TreeNode resNode = null;
            if (this.Left != null)
            {
                resNode = this.Left.PostOrderSearch(id);
            }

            if (resNode != null)
            {
                return resNode;
            }

            if (this.Right != null)
            {
                resNode = this.Right.PostOrderSearch(id);
            }

            if (resNode != null)
            {
                return resNode;
            }
            Console.WriteLine("后序遍历查找" + DateTime.Now);
            if (this.Id == id)
            {
                return this;
            }
            return resNode;
        }

        /// <summary>
        /// 根据id删除指定节点
        /// </summary>
        /// <param name="id"></param>
        public void DeleteNode(int id) 
        {
            if (this.Left != null && this.Left.Id == id) 
            {
                this.Left = null;
                return;
            }

            if (this.Right != null && this.Right.Id == id)
            {
                this.Right = null;
                return;
            }

            if (this.Left != null)
            {
                this.Left.DeleteNode(id);
            }

            if (this.Right != null)
            {
                this.Right.DeleteNode(id);
            }
        }
    }

    public class BinaryTree
    {
        private TreeNode root;

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

        //前序遍历
        public void PreOrder() 
        {
            if (this.root != null)
            {
                this.root.PreOrder();
            }
            else 
            {
                Console.WriteLine("二叉树为空，无法遍历！");
            }
        }

        //中序遍历
        public void InfixOrder() 
        {
            if (this.root != null)
            {
                this.root.InfixOrder();
            }
            else
            {
                Console.WriteLine("二叉树为空，无法遍历！");
            }
        }

        //后续遍历
        public void PostOrder() 
        {
            if (this.root != null)
            {
                this.root.PostOrder();
            }
            else
            {
                Console.WriteLine("二叉树为空，无法遍历！");
            }
        }

        /// <summary>
        /// 前序遍历查找
        /// </summary>
        /// <param name="id">根据id查找节点</param>
        /// <returns></returns>
        public TreeNode PreOrderSearch(int id)
        {
            if (root != null) 
            {
                return root.PreOrderSearch(id);
            }
            else
            {
                return null;
            }
        }

        //中序遍历查找
        public TreeNode InfixOrderSearch(int id)
        {
            if (root != null)
            {
                return root.InfixOrderSearch(id);
            }
            else
            {
                return null;
            }
        }

        //后序遍历查找
        public TreeNode PostOrderSearch(int id)
        {
            if (root != null)
            {
                return root.PostOrderSearch(id);
            }
            else
            {
                return null;
            }
        }

        public void DeleteNode(int id) 
        {
            if (root != null)
            {
                if (root.Id == id)
                {
                    root = null;
                }
                else
                {
                    root.DeleteNode(id);
                }
            }
            else
            {
                Console.WriteLine("空树无法删除！");
            }
        }
    }

调用：

        static void Main(string[] args)
        {
            //创建树
            var tree = new BinaryTree();

            //创建需要的节点
            TreeNode root = new TreeNode(1,"名册");
            TreeNode node2 = new TreeNode(2, "张三");
            TreeNode node3 = new TreeNode(3,"李四");
            TreeNode node4 = new TreeNode(4,"王五");
            TreeNode node5 = new TreeNode(5, "赵六");


            //手动创建二叉树
            root.Left = node2;
            root.Right = node3;
            node3.Left = node5;
            node3.Right = node4;
            tree.SetRoot(root);

            Console.WriteLine("删除前，前序遍历");
            tree.PreOrder();
            tree.DeleteNode(5);
            Console.WriteLine("删除后，前序遍历");
            tree.PreOrder();
            tree.DeleteNode(3);
            Console.WriteLine("删除后，前序遍历");
            tree.PreOrder();
            Console.Read();
        }