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;
}
一、输出树的叶子节点
1、非递归：
在利用先序遍历（非递归）方法，访问节点之前，判断是否该节点左右孩子都空
if ( node.Left == null && node.Right == null )
/// <summary>
/// 输出树的叶子结点：非递归---利用先序非递归实现
/// </summary>
/// <param name="rootNode"></param>
public static void PreOderPrintLeaves(TreeNode<T> rootNode)
{
TreeNode<T> node = rootNode;
LinkStack<TreeNode<T>> S = new LinkStack<TreeNode<T>>();//使用了自己定义的链栈
while (node != null || !S.IsEmpty())
{
while (node != null)
{
if (node.Left == null && node.Right == null)//判断是否是叶节点
{
VisitNode(node); //访问该节点
}
S.Push(node);
node = node.Left;
}
if (!S.IsEmpty())
{
node = S.Pop();
node = node.Right;
}
}
}
2、递归式：
与先序递归遍历类似，同样的加一个判断即可：
if ( BT.Left == null && BT.Right == null )
/// <summary>
/// 输出树的叶子结点：递归式
/// </summary>
/// <param name="rootNode"></param>
public static void PrintLeaves(TreeNode<T> rootNode)
{
TreeNode<T> BT = rootNode;
if (BT != null)
{
if (BT.Left == null && BT.Right == null)
{
VisitNode(BT); //访问该节点
}
PrintLeaves(BT.Left);
PrintLeaves(BT.Right);
}
}
二、输出树的高度
1、非递归：
利用层次遍历的非递归，增加
deepth变量,记录下遍历的层次，最后的层次即树的高度
/// <summary>
/// 输出树的高度：非递归---利用层序非递归实现
/// </summary>
/// <param name="rootNode"></param>
/// <returns></returns>
public static int LayerOderBinTreeHigh(TreeNode<T> rootNode)
{
if (rootNode == null) return 0;
int deepth = 0; //记录遍历层次
LinkQueue<TreeNode<T>> queue= new LinkQueue<TreeNode<T>>(); //创建队列,使用自定义的链队列
TreeNode<T> outNode;
queue.Enqueue(rootNode);
while (!queue.IsEmpty())
{
++deepth;//当前遍历的层次
int levelNodesCount = queue.Count;
for (int i = 0; i < levelNodesCount; ++i)
{
outNode = queue.Dequeue();
if (outNode.Left != null) queue.Enqueue(outNode.Left);
if (outNode.Right != null) queue.Enqueue(outNode.Right);
}
}
return deepth; //最终的层次：树的高度
}
2、递归式：
利用公式
max(LH,RH)+1: 即左右子树的最大的加1 为树高度
/// <summary>
/// 输出树的高度:递归式---利用公式：max(LH,RH)+1
/// </summary>
/// <param name="rootNode"></param>
/// <returns></returns>
public static int BinTreeHigh(TreeNode<T> rootNode)
{
int LH, RH;
TreeNode<T> BT = rootNode;
if (BT == null)
{
return 0;
}
else
{
LH = BinTreeHigh(BT.Left);
RH = BinTreeHigh(BT.Right);
return LH > RH ? LH + 1 : RH + 1;
}
}
三、输出某层的所有节点(也可以输出多个层的)
1、非递归:
利用层序遍历的非递归，在访问时，判断是否
deepth==level(输出多层，即
minLevel<=deepth<=maxLevel)
/// <summary>
/// 输出某层的所有节点（层序遍历：非递归）
/// </summary>
/// <param name="rootNode"></param>
/// <param name="level"></param>
public static void LayerOderPrintLevelNodes(TreeNode<T> rootNode, int level)
{
if (rootNode == null) return;
int deepth = 0;//记录遍历层次
LinkQueue<TreeNode<T>> queue = new LinkQueue<TreeNode<T>>(); //创建队列，使用自定义的链队列
TreeNode<T> outNode;
queue.Enqueue(rootNode);
while (!queue.IsEmpty())
{
++deepth;
int levelNodesCount = queue.Count;
for (int i = 0; i < levelNodesCount; ++i)
{
outNode = queue.Dequeue();
if (deepth == level) //判断是否是要访问的层的节点
{
VisitNode(outNode);//访问节点
}
if (outNode.Left != null) queue.Enqueue(outNode.Left);
if (outNode.Right != null) queue.Enqueue(outNode.Right);
}
}
}
2、递归式:
通过判断
level==1,来确定是否到达要访问的层的节点
/// <summary>
/// 输出某层的所有节点（递归式）
/// </summary>
/// <param name="rootNode"></param>
/// <param name="level"></param>
public static void PrintLevelNodes(TreeNode<T> rootNode, int level)
{
if (rootNode == null) return;
TreeNode<T> BT = rootNode;
if (level == 1)
{
VisitNode(BT);
}
else
{
PrintLevelNodes(BT.Left, level - 1);
PrintLevelNodes(BT.Right, level - 1);
}
}
测试用例：
public class _017_BinTree : MonoBehaviour
{
//二叉树结构:
private string tree = @"
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()
{
CreatBinTree();//创建二叉树
Debug.Log("二叉树结构：" + "\n" + tree);
//遍历应用：
Debug.Log("输出树的叶子节点：");
Debug.Log("---------非递归----利用先序非递归实现-----");
BinTree<int>.PreOderPrintLeaves(root);
BinTree<int>.DisPlayOutPut();
Debug.Log("---------递归式----利用先序递归实现-------");
BinTree<int>.PrintLeaves(root);
BinTree<int>.DisPlayOutPut();
Debug.Log("输出树的高度：");
Debug.Log("---------非递归----利用层序非递归实现------");
int high1= BinTree<int>.LayerOderBinTreeHigh(root);
Debug.Log("树的高度: " + high1);
Debug.Log("---------递归式----利用公式：max(LH,RH)+1 ");
int high2 = BinTree<int>.BinTreeHigh(root);
Debug.Log("树的高度: " + high2);
Debug.Log("输出第4层的所有节点：");
Debug.Log("---------非递归----判断 deepth==level-----");
BinTree<int>.LayerOderPrintLevelNodes(root,4);
BinTree<int>.DisPlayOutPut();
Debug.Log("---------递归式----判断 Leve==1-----------");
BinTree<int>.PrintLevelNodes(root, 4);
BinTree<int>.DisPlayOutPut();
}
}
测试结果：
其他应用：
四、 二元运算表达式树及其遍历
1、先序遍历得到前缀表达式：+ + a * b c * + * d e f g
2、中序遍历得到中缀表达式：a + b * c +
d * e + f * g(中缀表达式会受到运算符优先级的影响 :需要在遍历时加括号）3、后序遍历得到后缀表达式：a b c * + d e * f + g * +
五、两种遍历序列确定二叉树
已知三种遍历中的任意两种遍历序列， 能否唯一确定一棵二叉树呢？
答案：
必须要有中序遍历才行例子：先序和中序遍历序列来确定一棵二叉树
- 根据
先序遍历序列第一个结点确定根结点；- 根据
根结点在中序遍历序列中分割出左右两个子序列- 对
左子树和右子树分别递归使用相同的方法继续分解
