二叉树遍历 C#

1、在盘算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。（百度百科）

广度优先搜索(Breadth First Search),又叫宽度优先搜索或横向优先搜索，是从根结点开始沿着树的宽度搜索遍历，上面二叉树的遍历顺序为：ABCDEFG.

深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。以上面二叉树为例，深度优先搜索的顺序为：ABDECFG。

2、二叉树的实现

二叉树的结点包含data，left，right，通过一些结点之间的关系就可以构造二叉树；

二叉树节点类

1. class Node<T>
3. {
5. T data;
7. Node<T> left;
9. Node<T> right;
11. public Node(T value)
13. {
15. data = value;
17. left = null;
19. right = null;
21. }
23. public Node()
25. {
27. data = default(T);
29. left = null;
31. right = null;
33. }
35. public Node(T value,Node<T> lChild,Node<T> rChild)
37. {
39. data = value;
41. left = lChild;
43. right = rChild;
45. }
47. public T Data
49. {
51. get { return data; }
53. set { data = value; }
55. }
57. public Node<T> Left
59. {
61. get { return left; }
63. set { left = value; }
65. }
67. public Node<T> Right
69. {
71. get { return right; }
73. set { right = value; }
75. }
77. }

复制代码

View Code

3、二叉树类

1. class LinkBinaryTree<T>
3. {
5. private Node<T> root;//根结点
7. public Node<T> Root
9. {
11. get { return root; }
13. }
15. public LinkBinaryTree()
17. {
19. root = null;
21. }
23. public LinkBinaryTree(T value)
25. {
27. Node<T> p = new Node<T>(value);
29. root = p;
31. }
33. //三种深度遍历
35. //中序遍历
37. public void InOrder(Node<T> node)
39. {
41. if (root == null)
43. return;
45. if(node!=null)
47. {
49. InOrder(node.Left);
51. Console.Write(node.Data);
53. InOrder(node.Right);
55. }
57. }
59. //先序遍历
61. public void PreOrder(Node<T> node)
63. {
65. if (root == null)
67. return;
69. if (node != null)
71. {
73. Console.Write(node.Data);
75. PreOrder(node.Left);
77. PreOrder(node.Right);
79. }
81. }
83. //后序遍历
85. public void PostOrder(Node<T> node)
87. {
89. if (root == null)
91. return;
93. if (node != null)
95. {
97. PostOrder(node.Left);
99. PostOrder(node.Right);
101. Console.Write(node.Data);
103. }
105. }
107. //-------广度遍历----------使用队列又称为先辈先出
109. public void BFS(Node<T> root)
111. {
113. if (root == null)
115. return;
117. Queue<Node<T>> queue = new Queue<Node<T>>();
119. queue.Enqueue(root);
121. while (queue.Count>0)
123. {
125. Node<T> node = queue.Dequeue();
127. Console.WriteLine(node.Data);
129. if (node.Left != null)
131. queue.Enqueue(node.Left);
133. if (node.Right != null)
135. queue.Enqueue(node.Right);
137. }
139. }
141. }

复制代码

View Code

深度遍历：（根节点A的位置）

　　先序输出：A B D G H E C K F I J

　　中序输出：G D H B E A K C I J F

　　后序输出：G H D E B K J I F C A

广度遍历：

　　A B C D E K F G H I J

面试遇到的，于是在网上学习，自己总结一下。小菜瓜，第一次发。有什么问题望多多提，一起学习。往后我会把自己总结的Unity lua等都会一一发出来共享。独乐乐不如众乐乐嘛，一起进步。------一点都不v5的小菜瓜。

来源：https://www.cnblogs.com/yuanwenqiang/p/11347886.html
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！