menu 首页 标签 归档 视频 关于
数据结构-二叉树的遍历(二)

一言加载中...

对于树与二叉树前面概念部分,请移步:数据结构-树与二叉树再回顾(一)

什么是二叉树的遍历:

从二叉树的根节点出发,按照某种方式依次访问二叉树中的所有节点,使每个节点都能被访问一次且只能访问一次。以下有四种遍历方式:

访问顺序

遍历方式 遍历顺序
先序遍历 1. 访问根节点
2. 先序遍历左子节点
3. 先序遍历右子节点
中序遍历 1. 中序遍历左子节点
2. 访问根节点
3. 中序遍历右子节点
后序遍历 1. 后序遍历左子节点
2. 后序遍历右子节点
3. 访问根节点
层序遍历 逐层从左到右依次遍历

举个栗子:

对该完全二叉树(上图)使用不同遍历方式进行输出

顺序结构

对于一个二叉树,使用顺序结构对存储时,其存储方式是按照数组形式存储的,如下图

class MyTree<T>
&#123;
    //保存二叉树的数据
    private T[] data;
    //计数
    private int count = 0;
    public MyTree(int size)
    &#123;
        data = new T[size];
    &#125;
    //添加数据
    public bool Add(T item)
    &#123;
        if (count >= data.Length) return false;
        data[count] = item;
        count++;
        return true;
    &#125;
    public void FirstTravel(int startIndex=0)&#123;...&#125;
    public void MiddleTravel(int startIndex=0)&#123;...&#125;
    public void LastTravel(int startIndex=0)&#123;...&#125;
    public void LayerTravel(int startIndex=0)&#123;...&#125;
&#125;

先序遍历

/// <summary>
/// 先序遍历
/// </summary>
/// <param name="startIndex">开始遍历起点</param>
public void FirstTravel(int startIndex=0)
&#123;
    //终止条件
    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);
&#125;

中序遍历

/// <summary>
/// 中序遍历
/// </summary>
/// <param name="startIndex">开始遍历起点</param>
public void MiddleTravel(int startIndex=0)
&#123;
    //终止条件
    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);
&#125;

后续遍历

/// <summary>
/// 后序遍历
/// </summary>
/// <param name="startIndex">开始遍历起点</param>
public void LastTravel(int startIndex=0)
&#123;
    //终止条件
    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]+" ");
&#125;

层序遍历

/// <summary>
/// 层序遍历
/// </summary>
/// <param name="startIndex">开始遍历起点</param>
public void LayerTravel(int startIndex = 0)
&#123;
    for (int i = 0; i < count; i++)
    &#123;
        Console.Write(data[i] + " ");
    &#125;
&#125;

看下遍历结果

result

链式结构

对于链式结构的先序,中序,后续遍历,过于简单,只需访问根节点的左孩子,右孩子即可,最近刷力扣时遇到链式结构的层序遍历,与顺序结构的有所不同,记录下:

层序遍历

思想:

  1. 通过使用队列(当然也可以使用列表模拟先进后出的特性),如果根节点不为空,则将根节点入队;
  2. 从队列中取出一个节点(Temp);
  3. 如果Temp的左孩子不为空,则将Temp的左子节点入队;
  4. 如果Temp的右孩子不为空,则将Temp的右子节点入队;
  5. 如果队列不为空就重复执行2-5步,直到队列为空;

主要代码如下:

/// <summary>
/// 将二叉树层序遍历然后保存到列表中返回
/// </summary>
static public int[] LevelOrder(TreeNode root)
&#123;
    Queue<TreeNode> queue = new Queue<TreeNode>();
    List<int> result = new List<int>();
    if (root != null)
    &#123;
        queue.Enqueue(root);
    &#125;

    while(queue.Count>0)
    &#123;
        TreeNode node = queue.Dequeue();
        if(node.left!=null)
        &#123;
            queue.Enqueue(node.left);
        &#125;
        if(node.right!=null)
        &#123;
            queue.Enqueue(node.right);
        &#125;
        result.Add(node.val);
    &#125;
    return result.ToArray();
&#125;
TonyChenn
2018.10.18
写博客不易,请我喝杯咖啡?

评论

arrow_upward