下面简单介绍一下几种算法和思路
先序遍历
访问根结点
按先序遍历左子树;
按先序遍历右子树;
例如遍历已知二叉树结果为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 SystemLinq;
using SystemText;
namespace TreeNode_
{
// Binary Tree的结点类
class Node
{
public int Data { get; set; }
public Node LeftSubNode { get; set; }
public Node RightSubNode { get; set; }
// 结点为自己追加子结点（与向左/向右追加结合形成递归）
public void Append(Node subNode)
{
if (subNodeData <= thisData)
{
thisAppendLeft(subNode);
}
else
{
thisAppendRight(subNode);
}
}
// 向左追加
public void AppendLeft(Node subNode)
{
if (thisLeftSubNode == null)
{
thisLeftSubNode = subNode;
}
else
{
thisLeftSubNodeAppend(subNode);
}
}
// 向右追加
public void AppendRight(Node subNode)
{
if (thisRightSubNode == null)
{
thisRightSubNode = subNode;
}
else
{
thisRightSubNodeAppend(subNode);
}
}
// 结点显示自己的数据
public void ShowData()
{
ConsoleWriteLine(Data={} thisData);
}
}
// Binary Tree类
class Tree
{
// 根结点
public Node Root { get; set; }
// 以某结点为起点插入结点
public void Insert(Node newNode)
{
if (thisRoot == null)
{
thisRoot = newNode;
}
else
{
thisRootAppend(newNode);
}
}
// 重载默认以根结点为起点插入
public void MidTravel()
{
thisMidTravel(thisRoot);
}
// 中序遍历（递归）
public void MidTravel(Node node)
{
if (nodeLeftSubNode != null)
{
thisMidTravel(nodeLeftSubNode);
}
nodeShowData();
if (nodeRightSubNode != null)
{
thisMidTravel(nodeRightSubNode);
}
}
}
class Program
{
static void Main(string[] args)
{
Tree tree = new Tree();
treeInsert(new Node { Data = });
treeInsert(new Node { Data = });
treeInsert(new Node { Data = });
treeInsert(new Node { Data = });
treeInsert(new Node { Data = });
treeMidTravel();
ConsoleRead();
}
}
}
