二叉树遍历明

二叉树遍历

摘要：二叉树深度优先(先序、中序、后序)遍历，包括递归、非递归，和广度优先遍历。

1.定义二叉树

View Code

 1 using System;
 2 using System.Collections.Generic;
 3 
 4 namespace BiTreeTraverse
 5 {
 6     public class BiTNode<T>
 7     {
 8         //节点数据
 9         private T _data;
10         //左子节点
11         private BiTNode<T> _lBiTNode;
12         //右子节点
13         private BiTNode<T> _rBiTNode;
14 
15         public T Data
16         {
17             get { return _data; }
18             set { _data = value; }
19         }
20         public BiTNode<T> LBiTNode
21         {
22             get { return _lBiTNode; }
23             set { _lBiTNode = value; }
24         }
25         public BiTNode<T> RBiTNode
26         {
27             get { return _rBiTNode; }
28             set { _rBiTNode = value; }
29         }
30 
31         public BiTNode()
32         {
33             _lBiTNode = null;
34             _rBiTNode = null;
35         }
36 
37         public BiTNode(T data)
38             : this()
39         {
40             _data = data;
41         }
42     }
43 
44     public class BiTree<T>
45     {
46         private BiTNode<T> _head;
47 
48         public BiTNode<T> Head
49         {
50             get { return _head; }
51             set { _head = value; }
52         }
53 
54         public void AddLinkToLeftChild(BiTNode<T> biTNode, BiTNode<T> biTChild)
55         {
56             biTNode.LBiTNode = biTChild;
57 
58         }
59 
60         public void AddLinkToRightChild(BiTNode<T> biTNode, BiTNode<T> biTChild)
61         {
62             biTNode.RBiTNode = biTChild;
63 
64         }
65     }
66 }

2.遍历

View Code

  1 using System;
  2 using System.Collections.Generic;
  3 
  4 namespace BiTreeTraverse
  5 {
  6     class Program
  7     {
  8         static void Main(string[] args)
  9         {
 10             //先初始化二叉树（要遍历它，当然要先对它进行初始化了~~）
 11               //先初始化A/B/C/D/E/F/G/H这些节点
 12             BiTNode<string> biTNodeA = new BiTNode<string>("A");
 13             BiTNode<string> biTNodeB = new BiTNode<string>("B");
 14             BiTNode<string> biTNodeC = new BiTNode<string>("C");
 15             BiTNode<string> biTNodeD = new BiTNode<string>("D");
 16             BiTNode<string> biTNodeE = new BiTNode<string>("E");
 17             BiTNode<string> biTNodeF = new BiTNode<string>("F");
 18             BiTNode<string> biTNodeG = new BiTNode<string>("G");
 19             BiTNode<string> biTNodeH = new BiTNode<string>("H");
 20 
 21             //再将这些节点建立关系，让其形成一棵名符其实的二叉树  
 22             BiTree<string> biTree = new BiTree<string>();
 23             biTree.Head = biTNodeA;
 24             biTree.AddLinkToLeftChild(biTNodeA, biTNodeB);
 25             biTree.AddLinkToRightChild(biTNodeA, biTNodeC);
 26             biTree.AddLinkToRightChild(biTNodeB, biTNodeD);
 27             biTree.AddLinkToLeftChild(biTNodeC, biTNodeE);
 28             biTree.AddLinkToRightChild(biTNodeC, biTNodeF);
 29             biTree.AddLinkToLeftChild(biTNodeD, biTNodeG);
 30             biTree.AddLinkToRightChild(biTNodeD, biTNodeH);
 31 
 32             ///               A
 33             ///             /   \
 34             ///           B       C
 35             ///            \     /  \
 36             ///            D    E    F
 37             ///           /  \
 38             ///          G    H 
 39 
 40             while (true)
 41             {
 42                 Console.WriteLine();
 43                 Console.WriteLine("1、先序遍历");
 44                 Console.WriteLine("2、中序遍历");
 45                 Console.WriteLine("3、后序遍历");
 46                 Console.WriteLine("4、广度遍历");
 47                 Console.Write("input num：");
 48 
 49                 string num = Console.ReadLine();
 50                 switch (num)
 51                 {
 52                     case "1":
 53                         {
 54                             Console.WriteLine("Correct Sequence should be: \r\nA  B  D  G  H  C  E  F");
 55                             Console.WriteLine("递归先序");
 56                             RootFirst<string>(biTree.Head);                            
 57                             Console.WriteLine("\r\n非递归先序");
 58                             RootFirstNonRec<string>(biTree.Head);
 59                             break;
 60                         }
 61                     case "2":
 62                         {
 63                             Console.WriteLine("Correct Sequence should be: \r\nB  G  D  H  A  E  C  F");
 64                             Console.WriteLine("递归中序");
 65                             RootSecond<string>(biTree.Head);
 66                             Console.WriteLine("\r\n非递归中序");
 67                             RootSecondNonRec<string>(biTree.Head);
 68                             break;
 69                         }
 70                     case "3":
 71                         {
 72                             Console.WriteLine("Correct Sequence should be: \r\nG  H  D  B  E  F  C  A");
 73                             Console.WriteLine("递归后序");
 74                             RootLast<string>(biTree.Head);
 75                             Console.WriteLine("\r\n非递后中序");
 76                             RootLastNonRec<string>(biTree.Head);
 77                             break;
 78                         }
 79                     case "4":
 80                         {
 81                             Console.WriteLine("Correct Sequence should be: \r\nA  B  C  D  E  F  G  H");
 82                             Console.WriteLine("广度遍历");
 83                             BFSTraverse<string>(biTree.Head);                            
 84                             break;
 85                         }
 86                     default: break;
 87                 }
 88             }
 89         }
 90        
 91         //先序遍历
 92         protected static void RootFirst<T>(BiTNode<T> root)
 93         {
 94             if (root != null)
 95             {
 96                 Console.Write(root.Data+"  ");
 97                 RootFirst<T>(root.LBiTNode);
 98                 RootFirst<T>(root.RBiTNode);
 99             }
100         }
101 
102         //非递归先序遍历
103         protected static void RootFirstNonRec<T>(BiTNode<T> root)
104         {
105             Stack<BiTNode<T>> s= new Stack<BiTNode<T>>();
106             BiTNode<T> p = root;
107             while (p != null || s.Count!= 0)
108             {
109                 while (p != null)
110                 {
111                     Console.Write(p.Data+"  ");
112                     s.Push(p);
113                     p = p.LBiTNode;
114                 }
115                 if (s.Count != 0)
116                 {
117                     p = s.Pop();
118                     p = p.RBiTNode;
119                 }
120             }
121         }
122 
123         //中序遍历
124         protected static void RootSecond<T>(BiTNode<T> root)
125         {
126             if (root != null)
127             {
128                 RootSecond<T>(root.LBiTNode);
129                 Console.Write(root.Data + "  ");
130                 RootSecond<T>(root.RBiTNode);
131             }
132         }
133 
134         //非递归中序遍历
135         protected static void RootSecondNonRec<T>(BiTNode<T> root)
136         {
137             Stack<BiTNode<T>> s = new Stack<BiTNode<T>>();
138             BiTNode<T> p = root;
139             while (p != null || s.Count != 0)
140             {
141                 while (p != null)
142                 {                    
143                     s.Push(p);
144                     p = p.LBiTNode;
145                 }
146                 if (s.Count != 0)
147                 {
148                     p = s.Pop();
149                     Console.Write(p.Data + "  ");
150                     p = p.RBiTNode;
151                 }
152             }
153         }
154 
155         //后序遍历
156         protected static void RootLast<T>(BiTNode<T> root)
157         {
158             if (root != null)
159             {
160                 RootLast<T>(root.LBiTNode);
161                 RootLast<T>(root.RBiTNode);
162                 Console.Write(root.Data + "  ");
163             }
164         }
165 
166         //非递归后序遍历
167         protected static void RootLastNonRec<T>(BiTNode<T> root)
168         {
169             Stack<StBiTNode<T>> s = new Stack<StBiTNode<T>>();
170             StBiTNode<T> stBiTNode;            
171             BiTNode<T> p = root;
172             do
173             {
174                 while (p != null)
175                 {
176                     stBiTNode.BiTNode = p;
177                     stBiTNode.BiTNodeType = BiTNodeType.Left;
178                     s.Push(stBiTNode);
179                     p = p.LBiTNode;
180                 }
181                 //左右子树都访问过了
182                 while (s.Count != 0 && s.Peek().BiTNodeType == BiTNodeType.Right)
183                 {
184                     stBiTNode = s.Pop();
185                     Console.Write(stBiTNode.BiTNode.Data + "  ");
186                 }
187                 if (s.Count != 0)
188                 {
189                     stBiTNode = s.Pop();
190                     stBiTNode.BiTNodeType = BiTNodeType.Right;
191                     s.Push(stBiTNode);
192                     p = stBiTNode.BiTNode.RBiTNode;
193                 }
194                 
195             }
196             while (s.Count != 0);
197         }        
198         public enum BiTNodeType { Left, Right };
199         public struct StBiTNode<T>
200         {
201             public BiTNode<T> BiTNode;
202             public BiTNodeType BiTNodeType;
203         }
204 
205         //广度遍历
206         protected static void BFSTraverse<T>(BiTNode<T> root)
207         {
208             Queue<BiTNode<T>> q = new Queue<BiTNode<T>>();
209             BiTNode<T> p;
210             q.Enqueue(root);
211             while (q.Count != 0)
212             {
213                 p = q.Dequeue();
214                 Console.Write(p.Data + "  ");
215                 if (p.LBiTNode != null) q.Enqueue(p.LBiTNode);
216                 if (p.RBiTNode != null) q.Enqueue(p.RBiTNode);
217             }
218         }
219 
220     }
221 }

3.应用

    //Java递归删除一个目录下文件和文件夹
    private static void deleteDir(File dir) {
        if (dir.isDirectory()) {
            String[] children = dir.list();
            // 递归删除目录中的子目录下
            for (int i=0; i<children.length; i++) {
               deleteDir(new File(dir, children[i]));               
            }
        }
        dir.delete();
    }

二叉树遍历 明

二叉树遍历

二叉树遍历明