C#达成二叉树的遍历

发布时间：2021-11-15 11:16:23 所属栏目：PHP教程来源：互联网

导读：C#实现二叉树的前序、中序、后序遍历。 public class BinaryTreeNode { int value; BinaryTreeNode left; BinaryTreeNode right; /// summary /// 前序遍历 /// /summary /// param name=tree/param public static void PreOrder(BinaryTreeNode tree) { if

C#实现二叉树的前序、中序、后序遍历。

public class BinaryTreeNode
    {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;

        /// <summary>
        /// 前序遍历
        /// </summary>
        /// <param name="tree"></param>
        public static void PreOrder(BinaryTreeNode tree)
        {
            if (tree == null)
                return;

            System.Console.Write(tree.value + " ");
            PreOrder(tree.left);
            PreOrder(tree.right);
        }

        /// <summary>
        /// 前序遍历循环实现
        /// </summary>
        /// <param name="tree"></param>
        public static void PreOrderLoop(BinaryTreeNode tree)
        {
            if (tree == null)
                return;
            Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
            BinaryTreeNode node = tree;

            while(node != null || stack.Any()){
                if(node != null)
                {
                    stack.Push(node);
                    System.Console.Write(node.value + " ");
                    node = node.left;
                }
                else
                {
                    var item = stack.Pop();
                    node = item.right;
                }
            }
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        /// <param name="tree"></param>
        public static void InOrder(BinaryTreeNode tree)
        {
            if (tree == null)
                return;

            InOrder(tree.left);
            System.Console.Write(tree.value + " ");
            InOrder(tree.right);
        }

        /// <summary>
        /// 中序遍历循环实现
        /// </summary>
        /// <param name="tree"></param>
        public static void InOrderLoop(BinaryTreeNode tree)
        {
            if (tree == null)
                return;

            Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
            BinaryTreeNode node = tree;

            while (node != null || stack.Any())
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.left;
                }
                else
                {
                    var item = stack.Pop();
                    System.Console.Write(item.value + " ");
                    node = item.right;
                }
            }
        }

        /// <summary>
        /// 后序遍历
        /// </summary>
        /// <param name="tree"></param>
        public static void PostOrder(BinaryTreeNode tree)
        {
            if (tree == null)
                return;

            PostOrder(tree.left);
            PostOrder(tree.right);
            System.Console.Write(tree.value + " ");
        }

        /// <summary>
        /// 后序遍历循环实现1
        /// </summary>
        /// <param name="tree"></param>
        public static void PostOrderLoop(BinaryTreeNode tree)
        {
            if (tree == null)
                return;

            Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
            BinaryTreeNode node = tree;
            BinaryTreeNode pre = null;
            stack.Push(node);

            while (stack.Any())
            {
                node = stack.Peek();
                if ((node.left == null && node.right == null) ||
                    (pre != null && (pre == node.left || pre == node.right)))
                {
                    System.Console.Write(node.value + " ");
                    pre = node;
                    stack.Pop();
                }
                else
                {
                    if (node.right != null)
                        stack.Push(node.right);

                    if (node.left != null)
                        stack.Push(node.left);
                }
            }
        }

        /// <summary>
        /// 后续遍历循环实现2
        /// </summary>
        /// <param name="tree"></param>
        public static void PostOrderLoop2(BinaryTreeNode tree)
        {
            HashSet<BinaryTreeNode> visited = new HashSet<BinaryTreeNode>();
            Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
            BinaryTreeNode node = tree;

            while (node != null || stack.Any())
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.left;
                }
                else
                {
                    var item = stack.Peek();
                    if (item.right != null && !visited.Contains(item.right))
                    {
                        node = item.right;
                    }
                    else
                    {
                        System.Console.Write(item.value + " ");
                        visited.Add(item);
                        stack.Pop();
                    }
                }
            }
        }
    }

（编辑：应用网_丽江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

php读取大文件最好的实	php无限遍历文件夹示例
php中实现过滤UBB代码	Laravel模板引擎Blade