C non recursive preorder traversal binary tree instance
- 2021-07-13 06:07:39
- OfStack
In this paper, an example is given to describe the method of traversing 2-tree in C # non-recursive precedence. Share it for your reference. The details are as follows:
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))
{ // Upper 1 Wheel is the operation of removing
if (treeRoot.leftSon == point)
{// The left node is removed
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
{// The right node is removed
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;
}
}
}
I hope this article is helpful to everyone's C # programming.