二叉树遍历——深度优先(DFS)与广度优先(BFS)
二叉树的深度优先遍历(DFS)与广度优先遍历(BFS)
深度优先遍历:从根节点出发,沿着左子树方向进行纵向遍历,直到找到叶子节点为止。然后回溯到前一个节点,进行右子树节点的遍历,直到遍历完所有可达节点为止。
广度优先遍历:从根节点出发,在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。
DFS实现:
数据结构:栈
父节点入栈,父节点出栈,先右子节点入栈,后左子节点入栈。递归遍历全部节点即可
BFS实现:
数据结构:队列
父节点入队,父节点出队列,先左子节点入队,后右子节点入队。递归遍历全部节点即可
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
#include <Stack>
#include <Queue>
using namespace std;
typedef struct Node {
char data;
struct Node *lchild;
struct Node *rchild;
} *Tree;
//Tree 是一个node指针的类型定义
int index = 0; //全局索引变量
//二叉树构造器,按先序遍历顺序构造二叉树
//无左子树或右子树用'#'表示
void treeNodeConstructor(Tree &root, char data[]){
char e = data[index++];
if(e == '#'){
root = NULL;
}else{
root = (Node *)malloc(sizeof(Node));
root->data = e;
treeNodeConstructor(root->lchild, data); //递归构建左子树
treeNodeConstructor(root->rchild, data); //递归构建右子树
}
}
//深度优先遍历
void depthFirstSearch(Tree root){
stack<Node *> nodeStack; //使用C++的STL标准模板库
nodeStack.push(root);
Node *node;
while(!nodeStack.empty()){
node = nodeStack.top();
cout<<node->data;//遍历根结点
nodeStack.pop();
if(node->rchild){
nodeStack.push(node->rchild); //先将右子树压栈
}
if(node->lchild){
nodeStack.push(node->lchild); //再将左子树压栈
}
}
}
//广度优先遍历
void breadthFirstSearch(Tree root){
queue<Node *> nodeQueue; //使用C++的STL标准模板库
nodeQueue.push(root);
Node *node;
while(!nodeQueue.empty()){
node = nodeQueue.front();
nodeQueue.pop();
cout<<node->data;//遍历根结点
if(node->lchild){
nodeQueue.push(node->lchild); //先将左子树入队
}
if(node->rchild){
nodeQueue.push(node->rchild); //再将右子树入队
}
}
}
int main() {
//上图所示的二叉树先序遍历序列,其中用'#'表示结点无左子树或无右子树
char data[15] = {'A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F','#', '#', 'G', '#', '#'};
Tree tree;
treeNodeConstructor(tree, data);
printf("深度优先遍历二叉树结果: ");
depthFirstSearch(tree);
printf("\n\n广度优先遍历二叉树结果: ");
breadthFirstSearch(tree);
return 0;
}
深度优先搜索习题
Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.(求给定二叉树的最小深度)
思路:深度优先搜索
递归,若为空树返回0;
若左子树为空,则返回右子树的最小深度+1;(加1是因为要加上根这一层,下同)
若右子树为空,则返回左子树的最小深度+1;
若左右子树均不为空,则取左、右子树最小深度的较小值,+1;
虽然没有用到栈的数据结构,但本质上思想就是深度优先搜索。
参考代码:
class Solution {
public:
int run(TreeNode *root)
{
if(root == nullptr) return 0;
if(root->left == nullptr) // 若左子树为空,则返回右子树的最小深度+1
{
return run(root->right)+1;
}
if(root->right == nullptr) // 若右子树为空,则返回左子树的最小深度+1
{
return run(root->left)+1;
}
// 左右子树都不为空时,取较小值
int leftDepth = run(root->left);
int rightDepth = run(root->right);
return min(leftDepth+1,rightDepth+1);
}
};
#
广度优先搜索习题
从上往下打印出二叉树的每个节点,同层节点从左至右打印。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> res;
if(root==NULL)
return res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
res.push_back(q.front()->val);
if(q.front()->left!=NULL)
q.push(q.front()->left);
if(q.front()->right!=NULL)
q.push(q.front()->right);
q.pop();
}
return res;
}
};
还没有评论,来说两句吧...