遍历的实现
上一篇记录了二叉树的四种遍历：先序，中序，后序，层序;
有递归实现，也有非递归,递归比较简单，主要探讨非递归做法使用C#语言实现相关算法
二叉树的数据节点定义：
/// <summary>
/// 二叉树节点
/// </summary>
/// <typeparam name="T"></typeparam>
public class TreeNode<T>
{
T data;//数据域
TreeNode<T> left; //左孩子
TreeNode<T> right;//右孩子
public T Data
{
get
{
return data;
}
set
{
data = value;
}
}
public TreeNode<T> Left
{
get
{
return left;
}
set
{
left = value;
}
}
public TreeNode<T> Right
{
get
{
return right;
}
set
{
right = value;
}
}
public TreeNode(T _data, TreeNode<T> _left, TreeNode<T> _right)
{
this.data = _data;
this.left = _left;
this.right = _right;
}
public TreeNode(T _data) : this(_data, null, null)
{
}
//设置 左右孩子
public void SetLRChild(TreeNode<T> _left, TreeNode<T> _right)
{
this.left = _left;
this.right = _right;
}
//设置 左孩子
public void SetLChild(TreeNode<T> _left)
{
this.left = _left;
}
//设置 右孩子
public void SetRChild(TreeNode<T> _right)
{
this.right = _right;
}
}
创建，四种遍历（非递归）操作：
public class BinTree<T>
{
private static string output;
private static void VisitNode(TreeNode<T> node)
{
output += node.Data.ToString() + " ";
}
public static void DisPlayOutPut()
{
Debug.Log(output);
output = string.Empty;
}//显示遍历结果
0、创建二叉树
将形如：
"{3,1,#,2,#,#,4}"的字符串 string转换为int类型的二叉树
/// <summary>
/// 创建二叉树 ；eg {3,1,#,2,#,#,4}
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static TreeNode<int> StringToBinaryTree (string s)
{
string[] tokens = s.TrimEnd('}').TrimStart('{').Split(new[] { ',' }, StringSplitOptions.RemoveEmptyEntries).ToArray();
if(tokens.Length==0)
{
return null;
}
TreeNode<int> rootNode;
rootNode = tokens[0] == "#" ? null : new TreeNode<int>(int.Parse(tokens[0]));
Queue<TreeNode<int>> q = new Queue<TreeNode<int>>();
q.Enqueue(rootNode);
int index = 1;
while(index<tokens.Length)
{
var t = q.Dequeue();
if(tokens[index]!="#")
{
t.Left = new TreeNode<int>(int.Parse(tokens[index]));
q.Enqueue(t.Left);
}
index++;
if (index < tokens.Length && tokens[index] != "#")
{
t.Right = new TreeNode<int>(int.Parse(tokens[index]));
q.Enqueue(t.Right);
}
index++;
}
return rootNode;
}
//非递归：
1、先序遍历（非递归）：
在第1次碰到节点，入栈
S.Push(node);前访问即可
/// <summary>
/// 先序遍历
/// </summary>
/// <param name="root"></param>
public static void PreOrderTraversal(TreeNode<T> rootNode)
{
TreeNode<T> node = rootNode;
LinkStack<TreeNode<T>> S = new LinkStack<TreeNode<T>>();//使用了自己定义的链栈
//Stack<TreeNode<T>> S = new Stack<TreeNode<T>>(); //系统提供的
while (node != null || !S.IsEmpty())
{
while (node != null)
{
VisitNode(node); //访问该节点
S.Push(node);
node = node.Left;
}
if (!S.IsEmpty())
{
node = S.Pop();
node = node.Right;
}
}
}
中序遍历（非递归）：
在第2次碰到节点，出栈
S.Pop(node);后访问即可
/// <summary>
/// 中序遍历
/// </summary>
/// <param name="rootNode"></param>
public static void InOrderTraversal(TreeNode<T> rootNode)
{
TreeNode<T> node = rootNode;
LinkStack<TreeNode<T>> S = new LinkStack<TreeNode<T>>();//使用了自己定义的链栈
while (node != null || !S.IsEmpty())
{
while (node != null)
{
S.Push(node);
node = node.Left;
}
if (!S.IsEmpty())
{
node = S.Pop();
VisitNode(node); //访问该节点
node = node.Right;
}
}
}
后序遍历（重点）（非递归）：
后序的非递归实现较难点，使用
双栈,其中一栈为 输出栈OutStack：专门在最后输出访问节点将节点
入两栈后，转向去访问右孩子 ：node = node.Right;将节点
出栈后，转向去访问左孩子：node = node.Left;上面两条与前中序的非递归有所不同
最后完全出完
OutStack栈，便得到后序遍历结果
/// <summary>
/// 后序遍历：（重点）
///
/// 使用 : 双栈法
/// </summary>
/// <param name="rootNode"></param>
public static void PostOrderTraversal(TreeNode<T> rootNode)
{
TreeNode<T> node = rootNode;
LinkStack<TreeNode<T>> S = new LinkStack<TreeNode<T>>();//使用了自己定义的链栈
//Stack<TreeNode<T>> S = new Stack<TreeNode<T>>(); //系统提供的
LinkStack<TreeNode<T>> OutStack = new LinkStack<TreeNode<T>>();//使用了自己定义的链栈
//Stack<TreeNode<T>> OutStack = new Stack<TreeNode<T>>();//系统提供的
while (node != null || !S.IsEmpty())
{
while (node != null)
{
S.Push(node); //入栈
OutStack.Push(node); //入输出栈
node = node.Right; //右孩子
}
if (!S.IsEmpty())
{
node = S.Pop();
node = node.Left; //左孩子
}
}
while (OutStack.Count > 0)
{
TreeNode<T> outNode = OutStack.Pop();
VisitNode(outNode); //访问该节点
}
}
层序遍历（重点）（非递归）:
利用 变量
deepth记录当前遍历的层次利用 变量
levelNodesCount当前遍历的层的节点总数
/// <summary>
/// 层序遍历：（重点）
/// 使用 ：队列
/// </summary>
/// <param name="rootNode"></param>
public static void LayerOrderTraversal(TreeNode<T> rootNode)
{
if (rootNode == null) return; //若是空树，直接返回
LinkQueue<TreeNode<T>> queue = new LinkQueue<TreeNode<T>>(); //创建队列，使用自定义的链队列
//Queue<TreeNode<T>> queue;//系统提供的
int deepth = 0;//记录当前遍历层次
int levelNodesCount = 0; //当前遍历的层的节点总数
TreeNode<T> outNode;
queue.Enqueue(rootNode);
while (!queue.IsEmpty())
{
++deepth; //（此题不使用）
levelNodesCount = queue.Count;
for (int i = 0; i < levelNodesCount; ++i)
{
outNode = queue.Dequeue(); //出队
VisitNode(outNode); //访问该节点
//若输出节点，左右孩子不空，依次入队
if (outNode.Left != null) queue.Enqueue(outNode.Left);
if (outNode.Right != null) queue.Enqueue(outNode.Right);
}
}
}
}//类结束括号
测试用例：
二叉树结构：
private string t = "{1,2,3,4,5,#,#,6,7}";
root = BinTree<int>.StringToBinaryTree(t);//创建二叉树VS
//创建二叉树
void CreatBinTree()
{//root = new TreeNode<int>(1);
//TreeNode<int> t2 = new TreeNode<int>(2);
//TreeNode<int> t3 = new TreeNode<int>(3);
//TreeNode<int> t4 = new TreeNode<int>(4);
//TreeNode<int> t5 = new TreeNode<int>(5);
//TreeNode<int> t6 = new TreeNode<int>(6);
//TreeNode<int> t7 = new TreeNode<int>(7);//root.SetLRChild(t2, t3);
//t2.SetLRChild(t4, t5);
//t4.SetLRChild(t6, t7);
}
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class _017_BinTree : MonoBehaviour
{
//二叉树结构:
private string tree = @"
1
/ \
2 3
/ \
4 5
/ \
6 7
";
private string t = "{1,2,3,4,5,#,#,6,7}";
TreeNode<int> root; //二叉树根节点
//创建二叉树
void CreatBinTree()
{
//root = new TreeNode<int>(1);
//TreeNode<int> t2 = new TreeNode<int>(2);
//TreeNode<int> t3 = new TreeNode<int>(3);
//TreeNode<int> t4 = new TreeNode<int>(4);
//TreeNode<int> t5 = new TreeNode<int>(5);
//TreeNode<int> t6 = new TreeNode<int>(6);
//TreeNode<int> t7 = new TreeNode<int>(7);
//root.SetLRChild(t2, t3);
//t2.SetLRChild(t4, t5);
//t4.SetLRChild(t6, t7);
}
void Start()
{
root = BinTree<int>.StringToBinaryTree(t);//创建二叉树
Debug.Log("二叉树结构：" + "\n" + tree);
//遍历：
Debug.Log("------------先序遍历（非递归）-------------");
BinTree<int>.PreOrderTraversal(root);
BinTree<int>.DisPlayOutPut();
Debug.Log("------------中序遍历（非递归）-------------");
BinTree<int>.InOrderTraversal(root);
BinTree<int>.DisPlayOutPut();
Debug.Log("------------后序遍历（非递归）-------------");
BinTree<int>.PostOrderTraversal(root);
BinTree<int>.DisPlayOutPut();
Debug.Log("------------层序遍历（非递归）-------------");
BinTree<int>.LayerOrderTraversal(root);
BinTree<int>.DisPlayOutPut();
}
}
测试结果：
注：
二叉树的遍历是很多应用的核心步骤。
