文章详情

Php文档 Php问答 行业资讯 Php论坛 Php手册 Php博客
  • 游戏榜单
  • 软件榜单
关闭导航
热搜榜
热门下载
热门标签
关闭搜索
php爱好者> php文档>C#二叉树遍历算法实现浅析

C#二叉树遍历算法实现浅析

时间：2010-09-19  来源：liuyang052

下面简单介绍一下几种算法和思路：

◆C#二叉树遍历算法之先序遍历：

1.访问根结点

2.按先序遍历左子树;

3.按先序遍历右子树；

4.例如：遍历已知二叉树结果为：A-﹥B-﹥D-﹥G-﹥H-﹥C-﹥E-﹥F

◆C#二叉树遍历算法之中序遍历：

1.按中序遍历左子树;

2.访问根结点；

3.按中序遍历右子树；

4.例如遍历已知二叉树的结果：B-﹥G-﹥D-﹥H-﹥A-﹥E-﹥C-﹥F

◆C#二叉树遍历算法之后序遍历：

1.按后序遍历左子树；

2.按后序遍历右子树；

3.访问根结点；

4.例如遍历已知二叉树的结果：G-﹥H-﹥D-﹥B-﹥E-﹥F-﹥C-﹥A

◆C#二叉树遍历算法之层次遍历：

1.从上到下，从左到右遍历二叉树的各个结点(实现时需要借辅助容器)；

2.例如遍历已知二叉树的结果：A-﹥B-﹥C-﹥D-﹥E-﹥F-﹥G-﹥H

以下是整个二叉遍历算法解决方案的代码：

  1. using System;  
  2. using System.Collections.Generic;  
  3. using System.Text;  
  4.  
  5. namespace structure  
  6. {  
  7.     class Program  
  8.     {  
  9.         #region 二叉树结点数据结构的定义   
  10.         //二叉树结点数据结构包括数据域，左右结点以及父结点成员；  
  11.       class nodes﹤T﹥  
  12.         {  
  13.             T data;  
  14.             nodes﹤T﹥ Lnode, Rnode, Pnode;  
  15.             public T Data  
  16.             {  
  17.                 set { data = value; }  
  18.                 get { return data; }  
  19.  
  20.             }  
  21.             public nodes﹤T﹥ LNode  
  22.             {  
  23.                 set { Lnode = value; }  
  24.                 get { return Lnode; }  
  25.             }  
  26.             public nodes﹤T﹥ RNode  
  27.             {  
  28.                 set { Rnode = value; }  
  29.                 get { return Rnode; }  
  30.  
  31.             }  
  32.  
  33.             public nodes﹤T﹥ PNode  
  34.             {  
  35.                 set { Pnode = value; }  
  36.                 get { return Pnode; }  
  37.  
  38.             }  
  39.           public nodes()  
  40.           { }  
  41.           public nodes(T data)  
  42.           {  
  43.               this.data = data;  
  44.           }  
  45.  
  46.         }   
  47.         #endregion  
  48.  
  49.         #region 先序编历二叉树  
  50.         static void PreOrder﹤T﹥(nodes﹤T﹥ rootNode)  
  51.         {  
  52.             if (rootNode != null)  
  53.             {  
  54.                 Console.WriteLine(rootNode.Data);  
  55.                 PreOrder﹤T﹥(rootNode.LNode);  
  56.                 PreOrder﹤T﹥(rootNode.RNode);  
  57.  
  58.             }  
  59.         }  
  60.           
  61.         #endregion  
  62.  
  63.         #region 构造一棵已知的二叉树  
  64.  
  65.         static nodes﹤string﹥ BinTree()  
  66.         {  
  67.             nodes﹤string﹥[] binTree = new nodes﹤string﹥[8];  
  68.             //创建结点  
  69.             binTree[0] = new nodes﹤string﹥("A");  
  70.             binTree[1] = new nodes﹤string﹥("B");  
  71.             binTree[2] = new nodes﹤string﹥("C");  
  72.             binTree[3] = new nodes﹤string﹥("D");  
  73.             binTree[4] = new nodes﹤string﹥("E");  
  74.             binTree[5] = new nodes﹤string﹥("F");  
  75.             binTree[6] = new nodes﹤string﹥("G");  
  76.             binTree[7] = new nodes﹤string﹥("H");  
  77.             //使用层次遍历二叉树的思想，构造一个已知的二叉树  
  78.  
  79.             binTree[0].LNode = binTree[1];  
  80.             binTree[0].RNode = binTree[2];  
  81.             binTree[1].RNode = binTree[3];  
  82.             binTree[2].LNode = binTree[4];  
  83.             binTree[2].RNode = binTree[5];  
  84.             binTree[3].LNode = binTree[6];  
  85.             binTree[3].RNode = binTree[7];  
  86.             //返回二叉树的根结点  
  87.             return binTree[0];  
  88.  
  89.         }  
  90.         #endregion  
  91.  
  92.         #region 中序遍历二叉树  
  93.         static void MidOrder﹤T﹥(nodes﹤T﹥ rootNode)  
  94.         {  
  95.             if (rootNode != null)  
  96.             {  
  97.                 MidOrder﹤T﹥(rootNode.LNode);  
  98.                 Console.WriteLine(rootNode.Data);  
  99.                 MidOrder﹤T﹥(rootNode.RNode);  
  100.             }  
  101.         }   
  102.         #endregion  
  103.         后序遍历二叉树#region 后序遍历二叉树  
  104.         static void AfterOrder﹤T﹥(nodes﹤T﹥ rootNode)  
  105.         {  
  106.             if (rootNode != null)  
  107.             {  
  108.                 AfterOrder﹤T﹥(rootNode.LNode);  
  109.                 AfterOrder﹤T﹥(rootNode.RNode);  
  110.                 Console.WriteLine(rootNode.Data);  
  111.             }  
  112.  
  113.         }   
  114.         #endregion  
  115.  
  116.        #region 层次遍历二叉树  
  117.         static void LayerOrder﹤T﹥(nodes﹤T﹥ rootNode)  
  118.         {  
  119.             nodes﹤T﹥[] Nodes = new nodes﹤T﹥[20];  
  120.             int front = -1;  
  121.             int rear = -1;  
  122.             if (rootNode != null)  
  123.             {  
  124.                 rear++;  
  125.                 Nodes[rear] = rootNode;  
  126.  
  127.             }  
  128.  
  129.             while (front != rear)  
  130.             {  
  131.                 front++;  
  132.                 rootNode = Nodes[front];  
  133.                 Console.WriteLine(rootNode.Data);  
  134.                 if (rootNode.LNode != null)  
  135.                 {  
  136.                     rear++;  
  137.                     Nodes[rear] = rootNode.LNode;  
  138.                 }  
  139.                 if (rootNode.RNode != null)  
  140.                 {  
  141.                     rear++;  
  142.                     Nodes[rear] = rootNode.RNode;  
  143.                 }  
  144.             }  
  145.         }  
  146.           
  147.         #endregion  
  148.  
  149.       #region 测试的主方法  
  150.         static void Main(string[] args)  
  151.         {  
  152.             nodes﹤string﹥ rootNode = BinTree();  
  153.  
  154.             Console.WriteLine("先序遍历方法遍历二叉树：");  
  155.             PreOrder﹤string﹥(rootNode);  
  156.              
  157.             Console.WriteLine("中序遍历方法遍历二叉树：");  
  158.             MidOrder﹤string﹥(rootNode);  
  159.               
  160.             Console.WriteLine("后序遍历方法遍历二叉树：");  
  161.             AfterOrder﹤string﹥(rootNode);  
  162.  
  163.  
  164.             Console.WriteLine("层次遍历方法遍历二叉树：");  
  165.             LayerOrder﹤string﹥(rootNode);  
  166.  
  167.  
  168.             Console.Read();  
  169.  
  170.         }   
  171.         #endregion  
  172.     }  
  173. } 
相关阅读 更多 +
排行榜 更多 +
辰域智控app

辰域智控app

系统工具 下载
网医联盟app

网医联盟app

运动健身 下载
汇丰汇选App

汇丰汇选App

金融理财 下载

Copyright 2006-2020 (phpxiu.com) All Rights Reserved.

本站为非盈利性网站，不接受任何广告。php爱好者