程序代码:
/** * @文件名: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 请按任意键继续. . .