二叉树遍历 C#
<p>1、在盘算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。（百度百科）</p><p><div align="center"></div></p>
<p>广度优先搜索(Breadth First Search),又叫宽度优先搜索或横向优先搜索，是从根结点开始沿着树的宽度搜索遍历，上面二叉树的遍历顺序为：ABCDEFG.</p>
<p>深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。以上面二叉树为例，深度优先搜索的顺序为：ABDECFG。</p>
<p>2、二叉树的实现</p>
<p>二叉树的结点包含data，left，right，通过一些结点之间的关系就可以构造二叉树；</p>
<p>二叉树节点类</p>
<div align="center"></div><div align="center"></div>
class Node<T>
{
T data;
Node<T> left;
Node<T> right;
public Node(T value)
{
data = value;
left = null;
right = null;
}
public Node()
{
data = default(T);
left = null;
right = null;
}
public Node(T value,Node<T> lChild,Node<T> rChild)
{
data = value;
left = lChild;
right = rChild;
}
public T Data
{
get { return data; }
set { data = value; }
}
public Node<T> Left
{
get { return left; }
set { left = value; }
}
public Node<T> Right
{
get { return right; }
set { right = value; }
}
}
View Code
<p>3、二叉树类</p>
<div align="center"></div><div align="center"></div>
class LinkBinaryTree<T>
{
private Node<T> root;//根结点
public Node<T> Root
{
get { return root; }
}
public LinkBinaryTree()
{
root = null;
}
public LinkBinaryTree(T value)
{
Node<T> p = new Node<T>(value);
root = p;
}
//三种深度遍历
//中序遍历
public void InOrder(Node<T> node)
{
if (root == null)
return;
if(node!=null)
{
InOrder(node.Left);
Console.Write(node.Data);
InOrder(node.Right);
}
}
//先序遍历
public void PreOrder(Node<T> node)
{
if (root == null)
return;
if (node != null)
{
Console.Write(node.Data);
PreOrder(node.Left);
PreOrder(node.Right);
}
}
//后序遍历
public void PostOrder(Node<T> node)
{
if (root == null)
return;
if (node != null)
{
PostOrder(node.Left);
PostOrder(node.Right);
Console.Write(node.Data);
}
}
//-------广度遍历----------使用队列又称为先辈先出
public void BFS(Node<T> root)
{
if (root == null)
return;
Queue<Node<T>> queue = new Queue<Node<T>>();
queue.Enqueue(root);
while (queue.Count>0)
{
Node<T> node = queue.Dequeue();
Console.WriteLine(node.Data);
if (node.Left != null)
queue.Enqueue(node.Left);
if (node.Right != null)
queue.Enqueue(node.Right);
}
}
}
View Code
<p><div align="center"></div></p>
<p>深度遍历：（根节点A的位置）</p>
<p> 先序输出：A BDGHECKFIJ </p>
<p> 中序输出：GDHB EAKCIJF</p>
<p> 后序输出：GHDE BKJI F CA</p>
<p>广度遍历：</p>
<p> A BCDEKFGHIJ</p>
<p> </p>
<p> </p>
<p>面试遇到的，于是在网上学习，自己总结一下。小菜瓜，第一次发。有什么问题望多多提，一起学习。往后我会把自己总结的Unity lua等都会一一发出来共享。独乐乐不如众乐乐嘛，一起进步。------一点都不v5的小菜瓜。</p><br>来源：<a href="https://www.cnblogs.com/yuanwenqiang/p/11347886.html" target="_blank">https://www.cnblogs.com/yuanwenqiang/p/11347886.html</a><br>免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]