普通树的遍历明

2013-01-21

摘要：普通树的深度（先根、后根）遍历，和广度遍历。

1. 定义树（这里树节点多出一个visited状态变量）

View Code

 1 using System;
 2 using System.Collections.Generic;
 3 
 4 namespace TreeTraverse
 5 {
 6     public class TreeNode<T>
 7     {
 8         //节点数据
 9         private T _data;
10         //左子节点
11         private List<TreeNode<T>> _children;
12 
13         private bool _visited;
14 
15         public bool Visited
16         {
17             get { return _visited; }
18             set { _visited = value; }
19         }
20 
21         public List<TreeNode<T>> Children
22         {
23             get { return _children; }
24             set { _children = value; }
25         }
26 
27         public T Data
28         {
29             get { return _data; }
30             set { _data = value; }
31         }
32 
33         public TreeNode()
34         {
35             _children = new List<TreeNode<T>>();
36             _visited = false;
37         }
38 
39         public TreeNode(T data)
40             : this()
41         {
42             _data = data;
43         }
44         
45     } 
46 
47     class Tree<T>
48     {
49         private TreeNode<T> _head;
50 
51         public TreeNode<T> Head
52         {
53             get { return _head; }
54             set { _head = value; }
55         }
56 
57         public static TreeNode<T> GetUnVisitedChild(TreeNode<T> tNode)
58         {
59             foreach (TreeNode<T> node in tNode.Children)
60             {
61                 if (node.Visited == false)
62                     return node;
63             }
64             return null;
65         }
66 
67         public void AddLinkToChild(TreeNode<T> tNode, TreeNode<T> tChild)
68         {
69             tNode.Children.Add(tChild);
70         }
71     }
72 }

2. 遍历树

View Code

  1 using System;
  2 using System.Collections.Generic;
  3 
  4 namespace TreeTraverse
  5 {
  6     class Program
  7     {
  8         static void Main(string[] args)
  9         {
 10             //先初始化二叉树（要遍历它，当然要先对它进行初始化了~~）
 11             //先初始化A/B/C/D/E/F/G/H这些节点
 12             TreeNode<string> nodeA = new TreeNode<string>("A");
 13             TreeNode<string> nodeB = new TreeNode<string>("B");
 14             TreeNode<string> nodeC = new TreeNode<string>("C");
 15             TreeNode<string> nodeD = new TreeNode<string>("D");
 16             TreeNode<string> nodeE = new TreeNode<string>("E");
 17             TreeNode<string> nodeF = new TreeNode<string>("F");
 18             TreeNode<string> nodeG = new TreeNode<string>("G");
 19             TreeNode<string> nodeH = new TreeNode<string>("H");
 20             TreeNode<string> nodeI = new TreeNode<string>("I");
 21 
 22             //再将这些节点建立关系，让其形成一棵名符其实的二叉树  
 23             Tree<string> tree=new Tree<string>();
 24             tree.Head = nodeA;
 25             tree.AddLinkToChild(nodeA, nodeB);
 26             tree.AddLinkToChild(nodeA, nodeI);
 27             tree.AddLinkToChild(nodeA, nodeC);
 28             tree.AddLinkToChild(nodeB, nodeD);
 29             tree.AddLinkToChild(nodeC, nodeE);
 30             tree.AddLinkToChild(nodeC, nodeF);
 31             tree.AddLinkToChild(nodeD, nodeG);
 32             tree.AddLinkToChild(nodeD, nodeH);
 33 
 34             ///               A
 35             ///             / |  \
 36             ///           B   I   C
 37             ///            \     /  \
 38             ///            D    E    F
 39             ///           /  \
 40             ///          G    H 
 41            
 42             while (true)
 43             {
 44                 Console.WriteLine();
 45                 Console.WriteLine("1、先根深度优先");
 46                 Console.WriteLine("2、后根深度优先");
 47                 Console.WriteLine("3、广度优先");
 48                 Console.Write("input num：");
 49 
 50                 string num = Console.ReadLine();
 51                 switch (num)
 52                 {
 53                     case "1":
 54                         {
 55                             Console.WriteLine("Correct Sequence should be: \r\nA  B  D  G  H  I  C  E  F");
 56                             Console.WriteLine("先根深度递归优先");
 57                             ClearStatus<string>(tree.Head);
 58                             RootFirst<string>(tree.Head);
 59                             Console.WriteLine("\r\n先根深度非递归优先");
 60                             ClearStatus<string>(tree.Head);
 61                             RootFirstNonRec<string>(tree.Head);
 62                             break;
 63                         }
 64                     
 65                     case "2":
 66                         {
 67                             Console.WriteLine("Correct Sequence should be: \r\nG  H  D  B  I  E  F  C  A");
 68                             Console.WriteLine("后根深度非递归优先");
 69                             ClearStatus<string>(tree.Head);
 70                             RootLast<string>(tree.Head);
 71                             Console.WriteLine("\r\n后根深度非递归优先");
 72                             ClearStatus<string>(tree.Head);
 73                             RootLastNonRec<string>(tree.Head);
 74                             break;
 75                         }
 76                     case "3":
 77                         {
 78                             Console.WriteLine("广度优先");
 79                             BFSTraverse<string>(tree.Head);
 80                             break;
 81                         }
 82                     default: break;
 83                 }
 84             }
 85         }
 86 
 87         //先根深度优先
 88         protected static void RootFirst<T>(TreeNode<T> root)
 89         {
 90             if (root != null)
 91             {
 92                 Console.Write(root.Data + "  ");
 93                 foreach (TreeNode<T> node in root.Children)
 94                     RootFirst(node);
 95             }
 96         }
 97 
 98         //先根深度优先非递归
 99         protected static void RootFirstNonRec<T>(TreeNode<T> root)  
100         {
101             TreeNode<T> p = root;
102             Stack<TreeNode<T>> s = new Stack<TreeNode<T>>();
103             while (p != null || s.Count != 0)
104             {
105                 while (p != null)
106                 {
107                     Console.Write(p.Data + "  ");
108                     p.Visited = true;
109                     s.Push(p);
110                     p = Tree<T>.GetUnVisitedChild(p);
111                 }
112                 s.Pop();
113                 if (s.Count != 0)
114                 {   
115                     p = s.Peek();
116                     p = Tree<T>.GetUnVisitedChild(p);
117                 }
118             }
119         }
120 
121         //后根深度优先
122         protected static void RootLast<T>(TreeNode<T> root)
123         {
124             if (root != null)
125             {
126                 foreach (TreeNode<T> node in root.Children)
127                     RootLast(node);
128                 Console.Write(root.Data + "  ");
129             }
130         }
131 
132         //后根深度优先非递归
133         protected static void RootLastNonRec<T>(TreeNode<T> root)
134         {
135             TreeNode<T> p = root;
136             Stack<TreeNode<T>> s = new Stack<TreeNode<T>>();
137             while (p != null || s.Count != 0)
138             {
139                 while (p != null)
140                 {                    
141                     p.Visited = true;
142                     s.Push(p);
143                     p = Tree<T>.GetUnVisitedChild(p);
144                 }                
145                 Console.Write(s.Pop().Data+ "  ");                   
146                 if (s.Count != 0)
147                 {
148                     p = s.Peek();
149                     p = Tree<T>.GetUnVisitedChild(p);
150                 }
151             }
152         }
153 
154         //Breadth-First Traverse 广度优先
155         protected static void BFSTraverse<T>(TreeNode<T> root)
156         {
157             TreeNode<T> p = root;
158             Queue<TreeNode<T>> q = new Queue<TreeNode<T>>();
159             q.Enqueue(p);
160             while (q.Count != 0)
161             {
162                 p = q.Dequeue();
163                 Console.Write(p.Data + "  ");
164                 foreach (TreeNode<T> tNode in p.Children)
165                 {
166                     q.Enqueue(tNode);
167                 }
168             }
169         }
170 
171         //清除状态
172         protected static void ClearStatus<T>(TreeNode<T> root)
173         {
174             TreeNode<T> p = root;
175             Queue<TreeNode<T>> q = new Queue<TreeNode<T>>();
176             q.Enqueue(p);
177             while (q.Count != 0)
178             {
179                 p = q.Dequeue();
180                 p.Visited = false;
181                 foreach (TreeNode<T> tNode in p.Children)
182                 {
183                     q.Enqueue(tNode);
184                 }
185             }
186         }
187     }
188 }

普通树的遍历 明

普通树的遍历明