遍歷的實現(xiàn)
上一篇記錄了二叉樹的四種遍歷：先序乌昔，中序，后序壤追，層序;
有遞歸實現(xiàn)玫荣，也有非遞歸,遞歸比較簡單，主要探討非遞歸做法使用C#語言實現(xiàn)相關(guān)算法
二叉樹的數(shù)據(jù)節(jié)點定義：
/// <summary>
/// 二叉樹節(jié)點
/// </summary>
/// <typeparam name="T"></typeparam>
public class TreeNode<T>
{
T data;//數(shù)據(jù)域
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)
{
}
//設(shè)置 左右孩子
public void SetLRChild(TreeNode<T> _left, TreeNode<T> _right)
{
this.left = _left;
this.right = _right;
}
//設(shè)置 左孩子
public void SetLChild(TreeNode<T> _left)
{
this.left = _left;
}
//設(shè)置 右孩子
public void SetRChild(TreeNode<T> _right)
{
this.right = _right;
}
}
創(chuàng)建大诸，四種遍歷（非遞歸）操作：
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;
}//顯示遍歷結(jié)果
0捅厂、創(chuàng)建二叉樹
將形如：
"{3,1,#,2,#,#,4}"的字符串 string轉(zhuǎn)換為int類型的二叉樹
/// <summary>
/// 創(chuàng)建二叉樹 ；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次碰到節(jié)點焙贷，入棧
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>>(); //系統(tǒng)提供的
while (node != null || !S.IsEmpty())
{
while (node != null)
{
VisitNode(node); //訪問該節(jié)點
S.Push(node);
node = node.Left;
}
if (!S.IsEmpty())
{
node = S.Pop();
node = node.Right;
}
}
}
中序遍歷（非遞歸）：
在第2次碰到節(jié)點，出棧
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); //訪問該節(jié)點
node = node.Right;
}
}
}
后序遍歷（重點）（非遞歸）：
后序的非遞歸實現(xiàn)較難點贿堰，使用
雙棧,其中一棧為 輸出棧OutStack：專門在最后輸出訪問節(jié)點將節(jié)點
入兩棧后辙芍，轉(zhuǎn)向去訪問右孩子 ：node = node.Right;將節(jié)點
出棧后，轉(zhuǎn)向去訪問左孩子：node = node.Left;上面兩條與前中序的非遞歸有所不同
最后完全出完
OutStack棧羹与，便得到后序遍歷結(jié)果
/// <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>>(); //系統(tǒng)提供的
LinkStack<TreeNode<T>> OutStack = new LinkStack<TreeNode<T>>();//使用了自己定義的鏈棧
//Stack<TreeNode<T>> OutStack = new Stack<TreeNode<T>>();//系統(tǒng)提供的
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); //訪問該節(jié)點
}
}
層序遍歷（重點）（非遞歸）:
利用 變量
deepth記錄當(dāng)前遍歷的層次利用 變量
levelNodesCount當(dāng)前遍歷的層的節(jié)點總數(shù)
/// <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>>(); //創(chuàng)建隊列，使用自定義的鏈隊列
//Queue<TreeNode<T>> queue;//系統(tǒng)提供的
int deepth = 0;//記錄當(dāng)前遍歷層次
int levelNodesCount = 0; //當(dāng)前遍歷的層的節(jié)點總數(shù)
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); //訪問該節(jié)點
//若輸出節(jié)點纵搁，左右孩子不空吃衅，依次入隊
if (outNode.Left != null) queue.Enqueue(outNode.Left);
if (outNode.Right != null) queue.Enqueue(outNode.Right);
}
}
}
}//類結(jié)束括號
測試用例：
二叉樹結(jié)構(gòu)：
private string t = "{1,2,3,4,5,#,#,6,7}";
root = BinTree<int>.StringToBinaryTree(t);//創(chuàng)建二叉樹VS
//創(chuàng)建二叉樹
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
{
//二叉樹結(jié)構(gòu):
private string tree = @"
1
/ \
2 3
/ \
4 5
/ \
6 7
";
private string t = "{1,2,3,4,5,#,#,6,7}";
TreeNode<int> root; //二叉樹根節(jié)點
//創(chuàng)建二叉樹
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);//創(chuàng)建二叉樹
Debug.Log("二叉樹結(jié)構(gòu)：" + "\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();
}
}
測試結(jié)果：
注：
二叉樹的遍歷是很多應(yīng)用的核心步驟。
