熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> .NET編程 >> 正文

二叉樹遍歷算法C#實現

2013-11-13 09:57:07  來源: .NET編程 

  用C#實現了二叉樹的定義怎麼構造一顆已知的二叉樹用幾種常規的算法(先序中序後序層次)遍歷二叉樹希望能給有需要人帶來幫助也希望能得到大家的指點有關C#數據結構的書在書店裡找到網上也是極少如果你有好的學習資源別忘了告訴我先謝了數據結構對一個程序員來說現在是太重要了數據結構學得好的人邏輯思維一定很強在程序設計的時候就不會覺得太費勁了而且是在設計多層應用程序的時候真是讓人絞盡腦汁啊趁自己還年輕趕緊練練腦子哈哈咱們盡快進入主題吧

  本程序中將用到一棵已知的二叉樹如圖(二叉樹圖)所示

  

  下面簡單介紹一下幾種算法和思路

  先序遍歷

   訪問根結點

   按先序遍歷左子樹;

   按先序遍歷右子樹

   例如遍歷已知二叉樹結果為A>B>D>G>H>C>E>F

  中序遍歷

   按中序遍歷左子樹;

   訪問根結點

   按中序遍歷右子樹

   例如遍歷已知二叉樹的結果B>G>D>H>A>E>C>F

  後序遍歷

   按後序遍歷左子樹

   按後序遍歷右子樹

   訪問根結點

   例如遍歷已知二叉樹的結果G>H>D>B>E>F>C>A

  層次遍歷

   從上到下從左到右遍歷二叉樹的各個結點(實現時需要借輔助容器)

   例如遍歷已知二叉樹的結果A>B>C>D>E>F>G>H

  附加整個解決方案代碼

  二叉遍歷算法解決方案

  using System;

  using SystemCollectionsGeneric;

  using SystemText;

  namespace structure

  {

  class Program

  {

  二叉樹結點數據結構的定義#region 二叉樹結點數據結構的定義

  //二叉樹結點數據結構包括數據域左右結點以及父結點成員

  class nodes<T>

  {

  T data;

  nodes<T> Lnode Rnode Pnode;

  public T Data

  {

  set { data = value; }

  get { return data; }

  }

  public nodes<T> LNode

  {

  set { Lnode = value; }

  get { return Lnode; }

  }

  public nodes<T> RNode

  {

  set { Rnode = value; }

  get { return Rnode; }

  }

  public nodes<T> PNode

  {

  set { Pnode = value; }

  get { return Pnode; }

  }

  public nodes()

  { }

  public nodes(T data)

  {

  thisdata = data;

  }

  }

  #endregion

  先序編歷二叉樹#region 先序編歷二叉樹

  static void PreOrder<T>(nodes<T> rootNode)

  {

  if (rootNode != null)

  {

  ConsoleWriteLine(rootNodeData);

  PreOrder<T>(rootNodeLNode);

  PreOrder<T>(rootNodeRNode);

  }

  }

  #endregion

  構造一棵已知的二叉樹#region 構造一棵已知的二叉樹

  static nodes<string> BinTree()

  {

  nodes<string>[] binTree = new nodes<string>[];

  //創建結點

  binTree[] = new nodes<string>(A);

  binTree[] = new nodes<string>(B);

  binTree[] = new nodes<string>(C);

  binTree[] = new nodes<string>(D);

  binTree[] = new nodes<string>(E);

  binTree[] = new nodes<string>(F);

  binTree[] = new nodes<string>(G);

  binTree[] = new nodes<string>(H);

  //使用層次遍歷二叉樹的思想構造一個已知的二叉樹

  binTree[]LNode = binTree[];

  binTree[]RNode = binTree[];

  binTree[]RNode = binTree[];

  binTree[]LNode = binTree[];

  binTree[]RNode = binTree[];

  binTree[]LNode = binTree[];

  binTree[]RNode = binTree[];

  //返回二叉樹的根結點

  return binTree[];

  }

  #endregion

  中序遍歷二叉樹#region 中序遍歷二叉樹

  static void MidOrder<T>(nodes<T> rootNode)

  {

  if (rootNode != null)

  {

  MidOrder<T>(rootNodeLNode);

  ConsoleWriteLine(rootNodeData);

  MidOrder<T>(rootNodeRNode);

  }

  }

  #endregion

  後序遍歷二叉樹#region 後序遍歷二叉樹

  static void AfterOrder<T>(nodes<T> rootNode)

  {

  if (rootNode != null)

  {

  AfterOrder<T>(rootNodeLNode);

  AfterOrder<T>(rootNodeRNode);

  ConsoleWriteLine(rootNodeData);

  }

  }

  #endregion

  層次遍歷二叉樹#region 層次遍歷二叉樹

  static void LayerOrder<T>(nodes<T> rootNode)

  {

  nodes<T>[] Nodes = new nodes<T>[];

  int front = ;

  int rear = ;

  if (rootNode != null)

  {

  rear++;

  Nodes[rear] = rootNode;

  }

  while (front != rear)

  {

  front++;

  rootNode = Nodes[front];

  ConsoleWriteLine(rootNodeData);

  if (rootNodeLNode != null)

  {

  rear++;

  Nodes[rear] = rootNodeLNode;

  }

  if (rootNodeRNode != null)

  {

  rear++;

  Nodes[rear] = rootNodeRNode;

  }

  }

  }

  #endregion

  測試的主方法#region 測試的主方法

  static void Main(string[] args)

  {

  nodes<string> rootNode = BinTree();

  ConsoleWriteLine(先序遍歷方法遍歷二叉樹);

  PreOrder<string>(rootNode);

  ConsoleWriteLine(中序遍歷方法遍歷二叉樹);

  MidOrder<string>(rootNode);

  ConsoleWriteLine(後序遍歷方法遍歷二叉樹);

  AfterOrder<string>(rootNode);

  ConsoleWriteLine(層次遍歷方法遍歷二叉樹);

  LayerOrder<string>(rootNode);

  ConsoleRead();

  }

  #endregion

  }

  }


From:http://tw.wingwit.com/Article/program/net/201311/12089.html
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.