C#非递归先序遍历二叉树实例

Aurora ·

更新时间:2024-09-21

· 592 次阅读

本文实例讲述了C#非递归先序遍历二叉树的方法。分享给大家供大家参考。具体如下：


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication5
{
 class Program
 {
  static void Main(string[] args)
  {
   Node treeRoot = CreateTree();
   scanTree(treeRoot);
  }
  private static void scanTree(Node treeRoot)
  {
   List<Node> list = new List<Node>();
   list.Add(treeRoot);
   Node point = treeRoot;
   Write(treeRoot);
   while (true)
   {
    if (!list.Contains(point))
    { //上一轮是移除的操作
     if (treeRoot.leftSon == point)
     {//移除的是左结点
      if (treeRoot.rightSon != null)
      {
       treeRoot = treeRoot.rightSon;
       list.Add(treeRoot);
       Write(treeRoot);
       point = treeRoot;
       continue;
      }
      list.Remove(treeRoot);
      if (list.Count == 0)
      {
       break;
      }
      point = treeRoot;
      treeRoot = list[list.Count - 1];
     }
     else
     {//移除的是右结点
      list.Remove(treeRoot);
      if (list.Count == 0)
      {
       break;
      }
      point = treeRoot;
      treeRoot = list[list.Count - 1];
     }
     continue;
    }
    if (treeRoot.leftSon != null)
    {
     treeRoot = treeRoot.leftSon;
     Write(treeRoot);
     list.Add(treeRoot);
     point = treeRoot;
     continue;
    }
    if (treeRoot.rightSon != null)
    {
     treeRoot = treeRoot.rightSon;
     Write(treeRoot);
     point = treeRoot;
     list.Add(treeRoot);
     continue;
    }
    if (treeRoot.leftSon == null && treeRoot.rightSon == null)
    {
     list.Remove(treeRoot);
     if (list.Count == 0)
     {
      break;
     }
     point = treeRoot;
     treeRoot = list[list.Count - 1];
    }
   }
  }
  public static void Write(Node node)
  {
   Console.WriteLine(node.Data);
  }
  private static Node CreateTree()
  {
   Node a = new Node("A");
   a.leftSon = new Node("B");
   a.rightSon = new Node("C");
   a.leftSon.leftSon = new Node("D");
   a.leftSon.rightSon = new Node("E");
   a.rightSon.leftSon = new Node("F");
   a.rightSon.rightSon = new Node("G");
   a.leftSon.leftSon.leftSon = new Node("H");
   a.leftSon.leftSon.rightSon = new Node("I");
   return a;
  }
 }
 class Node
 {
  public string Data { get; set; }
  public Node leftSon { get; set; }
  public Node rightSon { get; set; }
  public Node(string data)
  {
   Data = data;
  }
 }
}

希望本文所述对大家的C#程序设计有所帮助。

您可能感兴趣的文章:C++基于先序、中序遍历结果重建二叉树的方法C#使用前序遍历、中序遍历和后序遍历打印二叉树的方法二叉树先根（先序）遍历的改进探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)通过先序遍历和中序遍历后的序列还原二叉树(实现方法)

二叉树先序遍历 C# 遍历递归

1024 个赞