前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >树(3)

树(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步没有成功删除节点,则应当向右子树递归删除

代码:

代码语言:javascript
复制
    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("空树无法删除!");
            }
        }
    }

调用:

代码语言:javascript
复制
        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();
        }
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-04-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 JusterZhu 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 二叉树-删除指定节点
    • 问题
      • 分析
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档