程序代码：
/**
* @文件名：Program.cs
* @作 者：寒风中的细雨
* @时 间：2012/5/16/
* @概 述：栈的基本操作, 队列的基本操作
*/
using System;
public interface IStack<T>
{
int GetLength();//求栈的长度
bool IsEmpty();//判断栈是否为空
void Clear();//清空栈操作
void Push(T nItem);//入栈
void Pop();//出栈
T GetTop();//取栈顶元素
}
public interface IQueue<T>
{
int GetLength();//求队列的长度
bool IsEmpty();//判断队列是否为空
void Clear();//清空队列
void In(T nItem);//入队
void Out();//出队
T GetFront();//取对头元素
}
//结点
class Node<T>
{
private T m_Data;
private Node<T> m_Next;
//m_Next属性
public Node<T> Next
{
get { return m_Next; }
set { m_Next = value; }
}
//m_Data属性
public T Data
{
get { return m_Data; }
set { m_Data = value; }
}
//构造函数
public Node(T nData, Node<T> nNext)
{
m_Data = nData;
m_Next = nNext;
}
public Node()
{
m_Data = default(T);
m_Next = null;
}
}
//链栈
public class LinkStack<T>:IStack<T>
{
private Node<T> m_Top;
private int m_Length;
//构造器
public LinkStack()
{
m_Length = 0;
m_Top = null;
}
//求栈的长度
public int GetLength()
{
return m_Length;
}
//判断栈是否为空
public bool IsEmpty()
{
return (null == m_Top);
}
//清空栈操作
public void Clear()
{
m_Top = null;
}
//进栈
public void Push(T nItem)
{
if (IsEmpty())
{
m_Top = new Node<T>(nItem, null);
++m_Length;
return;
}
m_Top = new Node<T>(nItem, m_Top);
++m_Length;
}
//出栈
public void Pop()
{
if (IsEmpty())
{
Console.WriteLine("出栈失败，栈空...");
return;
}
m_Top = m_Top.Next;
--m_Length;
}
//取栈顶元素
public T GetTop()
{
return m_Top.Data;
}
}
//队列
public class LinkQueue<T>:IQueue<T>
{
private Node<T> m_Rear;//队尾
private Node<T> m_Front;//对头
private int m_Length;//队长度
//构造函数
public LinkQueue()
{
m_Length = 0;
m_Front = m_Rear = null;
}
//求队列的长度
public int GetLength()
{
return m_Length;
}
//判断队列是否为空
public bool IsEmpty()
{
return 0 == m_Length;
}
//清空队列
public void Clear()
{
m_Length = 0;
m_Front = m_Rear = null;
}
//入队
public void In(T nItem)
{
if (this.IsEmpty())
{
m_Front = m_Rear = new Node<T>(nItem, null);
}
else
{
m_Rear.Next = new Node<T>(nItem, null);
m_Rear = m_Rear.Next;
}
++m_Length;
}
//出队
public void Out()
{
if (this.IsEmpty())
{
Console.WriteLine("队列为空...");
return;
}
if (m_Length > 1)
{
m_Front = m_Front.Next;
}
else
{
m_Front = m_Rear = null;
}
--m_Length;
}
//取对头元素
public T GetFront()
{
return m_Front.Data;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* @文件名：App.cs
* @作 者：寒风中的细雨
* @时 间：2012/5/16/
* @概 述：树的基本操作 模拟递归实现
*/
using System;
//二叉数的结点结构
class BinaryTreeNode<T>
{
private int m_Num;//后序遍历时候使用
private T m_Data;
private BinaryTreeNode<T> m_Lchild;
private BinaryTreeNode<T> m_Rchild;
//构造函数
public BinaryTreeNode(T nData, BinaryTreeNode<T> nLchild,
BinaryTreeNode<T> nRchild)
{
m_Data = nData;
m_Lchild = nLchild;
m_Rchild = nRchild;
m_Num = 0;
}
//属性域
public T Data
{
get { return m_Data; }
set { m_Data = value; }
}
public BinaryTreeNode<T> Lchild
{
get { return m_Lchild; }
set { m_Lchild = value; }
}
public BinaryTreeNode<T> Rchild
{
get { return m_Rchild; }
set { m_Rchild = value; }
}
public int Num
{
get { return m_Num; }
set { m_Num = value; }
}
}
//二叉树类
class BinaryTree
{
private BinaryTreeNode<char> m_Head;
//属性域
public BinaryTreeNode<char> Head
{
get { return m_Head; }
set { m_Head = value; }
}
//构造函数
public BinaryTree()
{
m_Head = null;
}
//建树 利用字符串ABC@@D@@E@F@@ 先序字符串
public void CreatTreeByString(string nStr)
{
LinkStack<BinaryTreeNode<char>> stack = new LinkStack<BinaryTreeNode<char>>();
int i = 0;
BinaryTreeNode<char> tmp = null;
do
{
while (nStr[i] != '@')
{//左孩子
if (m_Head == null)
{
m_Head = new BinaryTreeNode<char>(nStr[i], null, null);
stack.Push(m_Head);
}
else
{
tmp = new BinaryTreeNode<char>(nStr[i], null, null);
stack.GetTop().Lchild = tmp;
stack.Push(tmp);
}
++i;
}
stack.GetTop().Lchild = null;
tmp = stack.GetTop();
stack.Pop();
++i;
if (nStr[i] == '@')
{//第二个 进行出栈
tmp.Rchild = null;
if (stack.IsEmpty())
{
break;
}
tmp = stack.GetTop();
stack.Pop();
++i;
if (nStr[i] == '@')
{
tmp.Rchild = null;
++i;
continue;
}
}
BinaryTreeNode<char> tmp1 = null;
tmp1 = new BinaryTreeNode<char>(nStr[i], null, null);
tmp.Rchild = tmp1;
stack.Push(tmp1);
++i;
} while (!stack.IsEmpty());
}
//先序遍历
public void PreOrderTraverse()
{
LinkStack<BinaryTreeNode<char>> stack = new LinkStack<BinaryTreeNode<char>>();
if (m_Head == null)
{
Console.WriteLine("为空树...");
return;
}
BinaryTreeNode<char> tmp = m_Head;
do
{
while (tmp != null)
{
Console.Write("{0} ", tmp.Data);
stack.Push(tmp);
tmp = tmp.Lchild;
}
tmp = stack.GetTop();
stack.Pop();
tmp = tmp.Rchild;
} while (!stack.IsEmpty() || null !=tmp);
Console.WriteLine();
}
//中序遍历
public void InOrderTraverse()
{
LinkStack<BinaryTreeNode<char>> stack = new LinkStack<BinaryTreeNode<char>>();
if (m_Head == null)
{
Console.WriteLine("为空树...");
return;
}
BinaryTreeNode<char> tmp = m_Head;
do
{
while (tmp != null)
{
stack.Push(tmp);
tmp = tmp.Lchild;
}
tmp = stack.GetTop();
Console.Write("{0} ", tmp.Data);
stack.Pop();
tmp = tmp.Rchild;
} while (!stack.IsEmpty() || null != tmp);
Console.WriteLine();
}
//后序遍历
public void PostOrderTraverse()
{
LinkStack<BinaryTreeNode<char>> stack = new LinkStack<BinaryTreeNode<char>>();
if (m_Head == null)
{
Console.WriteLine("为空树...");
return;
}
BinaryTreeNode<char> tmp = m_Head;
do
{
while (tmp != null)
{
stack.Push(tmp);
tmp = tmp.Lchild;
}
tmp = stack.GetTop();
tmp.Num += 1;
while (!stack.IsEmpty() && stack.GetTop().Num == 2)
{
Console.Write("{0} ", stack.GetTop().Data);
stack.Pop();
if (!stack.IsEmpty())
{
stack.GetTop().Num += 1;
}
}
if (!stack.IsEmpty())
{
tmp = stack.GetTop().Rchild;
}
} while (!stack.IsEmpty());
Console.WriteLine();
}
//层序遍历
public void LevelOrderTraverse()
{
LinkQueue<BinaryTreeNode<char>> queue = new LinkQueue<BinaryTreeNode<char>>();
if (m_Head == null)
{
Console.WriteLine("为空树...");
return;
}
BinaryTreeNode<char> tmp = m_Head;
queue.In(tmp);
do
{
tmp = queue.GetFront();
Console.Write("{0} ", tmp.Data);
queue.Out();
if (tmp.Lchild != null)
{
queue.In(tmp.Lchild);
}
if (tmp.Rchild != null)
{
queue.In(tmp.Rchild);
}
} while (!queue.IsEmpty());
Console.WriteLine();
}
}
class App
{
static void Main(string[] args)
{
BinaryTree Tree = new BinaryTree();
Tree.CreatTreeByString("AB@D@@EF@@@");
Console.WriteLine("先序遍历");
Tree.PreOrderTraverse();
Console.WriteLine("中序遍历");
Tree.InOrderTraverse();
Console.WriteLine("后序遍历");
Tree.PostOrderTraverse();
Console.WriteLine("层序遍历");
Tree.LevelOrderTraverse();
Console.WriteLine();
BinaryTree tree = new BinaryTree();
tree.CreatTreeByString("ABC@@D@@E@F@@");
Console.WriteLine("先序遍历");
tree.PreOrderTraverse();
Console.WriteLine("中序遍历");
tree.InOrderTraverse();
Console.WriteLine("后序遍历");
tree.PostOrderTraverse();
Console.WriteLine("层序遍历");
tree.LevelOrderTraverse();
}
}
先序遍历
A B D E F
中序遍历
B D A F E
后序遍历
D B F E A
层序遍历
A B E D F
先序遍历
A B C D E F
中序遍历
C B D A E F
后序遍历
C D B F E A
层序遍历
A B E C D F
请按任意键继续. . .
