menu Home Tags Archives Video About
数据结构-二叉树的遍历(二)

一言加载中...

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

什么是二叉树的遍历:

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

访问顺序

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

举个栗子:

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

顺序结构

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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){...}
}

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/// <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);
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/// <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);
}

后续遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/// <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]+" ");
}

层序遍历

1
2
3
4
5
6
7
8
9
10
11
/// <summary>
/// 层序遍历
/// </summary>
/// <param name="startIndex">开始遍历起点</param>
public void LayerTravel(int startIndex = 0)
{
for (int i = 0; i < count; i++)
{
Console.Write(data[i] + " ");
}
}

看下遍历结果

result

TonyChenn
2018.10.18

评论