• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

二叉树遍历 C#

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

二叉树遍历 C#

什么是二叉树

  二叉树是每个节点最多有两个子树的树结构
  (1)完全二叉树——若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二 叉树。
  (2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
  (3)平衡二叉树——平衡二叉树又被称为AVL树,它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

  二叉数遍历 有 前序遍历、中序遍历、后续遍历,层次遍历、Z型遍历

前期准备工作

  1.定义树的结构

    public class Tree
    {
        public string Value;
        public Tree Left;
        public Tree Right;
    }

   2.创建一颗二叉树

        public static Tree CreatTree()
        {
            Tree tree = new Tree() { Value = "A" };
            tree.Left = new Tree()
            {
                Value = "B",
                Left = new Tree() { Value = "D" },
                Right = new Tree() { Value = "E", Right = new Tree() { Value = "H" } }
            };
            tree.Right = new Tree() { Value = "C", Left = new Tree() { Value = "F" }, Right=new Tree() { Value="G"} };
            return tree;
        }

   树的效果图如下

前序遍历

  前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树
  前序遍历结果 A->B->D->E->H->C->F->G
  C#实现二叉树的前序遍历

        public static void PreOrder(Tree tree)
        {
            Console.Write(tree.Value + "  ");
            if (tree.Left != null)
            {
                PreOrder(tree.Left);
            }
            if (tree.Right != null)
            {
                PreOrder(tree.Right);
            }
        }

中序遍历

  中序遍历也叫做中根遍历、中序周游,遍历方式是先左后根再右

  中序遍历结果 D->B->E->H->A->F->C->G

  看代码

       public static void InOrder(Tree tree)
        {
            if (tree.Left != null)
            {
                InOrder(tree.Left);
            }
            Console.Write(tree.Value + "  ");
            if (tree.Right != null)
            {
                InOrder(tree.Right);
            }
        }  

后序遍历

  后序遍历也叫做后根遍历、后序周游,可记做左右根。先左后右再根。巧记:左右根。
  后序遍历首先遍历左子树,然后遍历右子树,最后访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点
  后序遍历结果 D->H->E->B->F->G->C->A
  看代码

        public static void InOrder(Tree tree)
        {
            if (tree.Left != null)
            {
                InOrder(tree.Left);
            }
            Console.Write(tree.Value + "  ");
            if (tree.Right != null)
            {
                InOrder(tree.Right);
            }
        }

层次遍历

  层次遍历就是按照树的层次从上到下进行输出,层次遍历我们可以借助队列的先进先出

  层次遍历结果A->B->C->D->E->F->G->H
  看代码

       public static void LevelOrder(Tree tree)
        {
            var queue = new Queue<Tree>();
            queue.Enqueue(tree);
            while (queue.Any())
            {
                var item = queue.Dequeue();
                Console.Write(item.Value);
                if (item.Left != null)
                {
                    queue.Enqueue(item.Left);
                }
                if (item.Right != null)
                {
                    queue.Enqueue(item.Right);
                }
            }
        }

Z型层次遍历

  Z型层次遍历即按照奇数层由左到右的遍历方式、偶数层按照由右到左的遍历方式

  Z型遍历输出结果A->C->B->D->E->F->G->H

  针对Z行遍历我们可以使用2个栈,来记录奇数层的输出和偶数层的输出,由于栈是先进后出,需要注意入栈的顺序

  看代码

        public static void ZOrder(Tree tree)
        {
            Stack<Tree> stack1 = new Stack<Tree>();
            Stack<Tree> stack2 = new Stack<Tree>();
            stack1.Push(tree);
            while (stack1.Any() || stack2.Any())
            {
                while (stack1.Any())
                {
                    var item = stack1.Pop();
                    Console.Write(item.Value + "  ");
                    if (item.Left != null)
                    {
                        stack2.Push(item.Left);
                    }
                    if (item.Right != null)
                    {
                        stack2.Push(item.Right);
                    }
                }
                while (stack2.Any())
                {
                    var item = stack2.Pop();
                    Console.Write(item.Value + "  ");
                    if (item.Right != null)
                    {
                        stack1.Push(item.Right);
                    }
                    if (item.Left != null)
                    {
                        stack1.Push(item.Left);
                    }
                }
            }
        }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
黄聪:C# 日期格式发布时间:2022-07-13
下一篇:
在图像上增加文字 C#发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap