二叉树的遍历(二叉树的遍历)

二叉树的遍历
对于树与二叉树前面概念部分，请移步：
树与二叉树的那点事
什么是二叉树的遍历从二叉树的根节点出发，按照某种方式依次访问二叉树中的所有节点，使每个节点都能被访问一次且只能访问一次。以下有四种遍历方式：
访问顺序

举个栗子
对该完全二叉树(上图)使用不同遍历方式进行输出
顺序结构对于一个二叉树，使用顺序结构对存储时，其存储方式是按照数组形式存储的，如下图
class MyTree<T>
{
    //保存二叉树的数据
    private T[] data;
    //计数
    private int count = 0;
    public MyTree(int size)
    {
        data = new T[size];
    }
    //添加数据
    public bool Add(T item)
    {
        if (count >= data.Length) return false;
        data[count] = item;
        count++;
        return true;
    }
    public void FirstTravel(int startIndex=0){…}
    public void MiddleTravel(int startIndex=0){…}
    public void LastTravel(int startIndex=0){…}
    public void LayerTravel(int startIndex=0){…}
}
先序遍历/// <summary>
/// 先序遍历
/// </summary>
/// <param name=”startIndex”>开始遍历起点</param>
public void FirstTravel(int startIndex=0)
{
    //终止条件
    if (startIndex >= count) return;
    //startIndex是index
    //number是相当于编号
    int number = startIndex + 1;
    Console.Write(data[startIndex]+” “);

    int leftChild = number * 2;
    int rightChild = number*2 + 1;

    FirstTravel(leftChild – 1);
    FirstTravel(rightChild – 1);
}
中序遍历/// <summary>
/// 中序遍历
/// </summary>
/// <param name=”startIndex”>开始遍历起点</param>
public void MiddleTravel(int startIndex=0)
{
    //终止条件
    if (startIndex >= count) return;
    //startIndex是index
    //number是相当于编号
    int number = startIndex + 1;

    int leftChild = number * 2;
    int rightChild = leftChild + 1;

    MiddleTravel(leftChild-1);
    Console.Write(data[startIndex] + ” “);
    MiddleTravel(rightChild-1);
}
后续遍历/// <summary>
/// 后序遍历
/// </summary>
/// <param name=”startIndex”>开始遍历起点</param>
public void LastTravel(int startIndex=0)
{
    //终止条件
    if (startIndex >= count) return;
    //startIndex是index
    //number是相当于编号
    int number = startIndex + 1;
    int leftChild = number * 2;
    int rightChild = leftChild + 1;
    LastTravel(leftChild-1);
    LastTravel(rightChild-1);
    Console.Write(data[startIndex]+” “);
}
层序遍历/// <summary>
/// 层序遍历
/// </summary>
/// <param name=”startIndex”>开始遍历起点</param>
public void LayerTravel(int startIndex = 0)
{
    for (int i = 0; i < count; i++)
    {
        Console.Write(data[i] + ” “);
    }
}
看下遍历结果result链式结构对于链式结构的先序，中序，后续遍历，过于简单，只需访问根节点的左孩子，右孩子即可，最近刷力扣时遇到链式结构的层序遍历，与顺序结构的有所不同，记录下：
层序遍历思想：
通过使用队列（当然也可以使用列表模拟先进后出的特性），如果根节点不为空，则将根节点入队；从队列中取出一个节点(Temp);如果Temp的左孩子不为空，则将Temp的左子节点入队；如果Temp的右孩子不为空，则将Temp的右子节点入队；如果队列不为空就重复执行2-5步，直到队列为空；主要代码如下：
/// <summary>
/// 将二叉树层序遍历然后保存到列表中返回
/// </summary>
static public int[] LevelOrder(TreeNode root)
{
    Queue<TreeNode> queue = new Queue<TreeNode>();
    List<int> result = new List<int>();
    if (root != null)
    {
        queue.Enqueue(root);
    }

    while(queue.Count>0)
    {
        TreeNode node = queue.Dequeue();
        if(node.left!=null)
        {
            queue.Enqueue(node.left);
        }
        if(node.right!=null)
        {
            queue.Enqueue(node.right);
        }
        result.Add(node.val);
    }
    return result.ToArray();
}

扫码关注       关注组织，一块学做游戏吧>>阅读原文最下方留言哟<<

二叉树的遍历相关文章