本文讲解C#实现二叉树非递归中序遍历程序
1、非递归中序遍历 /// /// 非递归中序遍历 /// /// static void InOrder2(BiTNode T) { SqStack S = new SqStack(); S.data = new BiTNode[MaxSize]; InitStack(ref S); BiTNode p = T; while (p!=null||!StackEmpty(S)) { if (p != null) { Push(ref S, p); p = p.lchild; } else { PoP(ref S, ref p); visit§; p = p.rchild; }
}
}
2、节点访问 /// /// 结点值的输出 /// static void visit(BiTNode T) { Console.Write(T.data+" "); } 3、栈结构的实现 /// /// 栈定义 /// public struct SqStack { public BiTNode[] data; public int top;//栈顶
}
///
/// 判断栈是否为空
///
///
///
static bool StackEmpty(SqStack S)
{
if (S.top == -1)
{
return true;
}
else
{
return false;
}
}
///
/// 栈初始化
///
///
static void InitStack(ref SqStack S)
{
S.top = -1;
}
///
/// 压栈
///
///
///
static bool Push(ref SqStack S, BiTNode e)
{
if (S.top >= MaxSize - 1)
{
return false;
}
S.top = S.top + 1;
S.data[S.top] = e;//先加1，再进栈
return true;
}
///
/// 出栈
///
///
///
///
static bool PoP(ref SqStack S, ref BiTNode e)
{
if (S.top == -1) { return false; }
e = S.data[S.top--];//出栈
return true;
}
///
///
///读取栈顶元素
///
///
///
///
bool GetTop(ref SqStack S, ref BiTNode e)
{
if (S.top == -1) { return false; }
e = S.data[S.top];//读取元素
return true;
}
5、main函数测试 public const int MaxSize = 50; static void Main(string[] args) { BiTNode T = new BiTNode() ; int x=0; //创建二叉树 T.data = 1; T.lchild= new BiTNode(); T.lchild.data = 2; T.rchild = new BiTNode(); T.rchild.data = 3; T.lchild.rchild=new BiTNode(); T.lchild.rchild.data = 4; T.lchild.rchild.lchild= new BiTNode(); T.lchild.rchild.lchild.data = 6; T.rchild.rchild = new BiTNode(); T.rchild.rchild.data = 5; Console.WriteLine(“先序遍历的值：”); PreOrder(T); Console.WriteLine(); Console.WriteLine(“中序遍历的值：”); InOrder(T); Console.WriteLine(); Console.WriteLine(“后序遍历的值：”); PostOrder(T); Console.WriteLine(); Console.WriteLine(“非递归中序遍历的值：”); InOrder2(T); Console.WriteLine(); Console.WriteLine(“层次遍历的值：”); LevelOrder(T); Console.ReadLine();
}
