IBC编程社区设为首页收藏本站
开启辅助访问 切换到宽版
搜索

马上加入IBC程序猿 各种源码随意下,各种教程随便看! 注册 每日签到 加入编程讨论群

C#教程 ASP.NET教程 C#视频教程程序源码享受不尽 C#技术求助 ASP.NET技术求助

【源码下载】 社群合作 申请版主 程序开发 【远程协助】 每天乐一乐 每日签到 【承接外包项目】 面试-葵花宝典下载

官方一群：

官方二群：

IBC编程社区-C#论坛-C#教程,.NET教程-.NET源码»首页 › C#教程 › C#文章教程 › 二叉树遍历 C#

二叉树遍历 C#

[复制链接]
查看2894 | 回复0 | 2019-8-13 20:26:28 | 显示全部楼层 |阅读模式

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

203006sgma5as22mz1ppmr.png

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

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

2、二叉树的实现

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

二叉树节点类

203007a6sas0uy60uwuymv.gif
203007rvn3ja7n7jylh57o.gif
  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、二叉树类

203007guzukjx1dbrkfgro.gif
203007wegzqm9lzi3mep3b.gif
  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

203007sc3wsbbu9c1uzgew.png

深度遍历：（根节点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
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
回复

使用道具 举报

返回列表 发新帖
*滑块验证:
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

ibcadmin
回复楼主 返回列表