C++学习记录-数据结构-二叉树的遍历

二叉树的层次遍历（宽度优先遍历）

  • 利用队列的特性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void BFS()
{
	Node* arr[100];
    //创建一个队列数组存储节点的地址，可以使用STL里的队列
    
	arr[0] = root;
	int head = 0;
	int tail = 1;
    //存入根节点，定义头尾
    
	while (head != tail)//当头部不等于尾部的时候，即队列不为空时
	{
		cout << arr[head]->data << " ";
		if (arr[head]->left != NULL)
		{
			arr[tail] = arr[head]->left;
			tail++;
		}//左孩入队
        
		if (arr[head]->right != NULL)
		{
			arr[tail] = arr[head]->right;
			tail++;
		}//右孩入队
        
		head++;
        //已经遍历的节点出队
	}
	return;
}//二叉树的层次遍历（宽度优先）

二叉树的前序，中序，后序遍历

  • 利用递归实现
1
2
3
4
5
6
7
8
9
10
void DFSpre(Node* root)
{
	if (root == NULL) { return; }//如果节点为空，则返回
    
	cout << root->data << endl;
	DFSpre(root->left);
	DFSpre(root->right);
    //调整这三句的顺序即可实现前序，中序，后序遍历
    
}//二叉树的遍历（深度优先）