数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时装研究
法律研究C++ 中的二叉树层次遍历
假设我们有一棵二叉树。我们必须使用层次遍历方案遍历这棵树。因此，如果这棵树类似于
遍历序列将类似于 - [10, 5, 16, 8, 15, 20, 23]
为了解决这个问题，我们将按以下步骤进行操作 -
- 定义队列 que 来存储节点
- 将根节点插入 que 中。
- 在 que 不为空时，执行以下操作
- item := 队列的头部位置处的 item
- 打印 item 的值
- 如果 item 的左节点不为空，那么将 item 的左节点插入 que
- 如果 item 的右节点不为空，那么将 item 的右节点插入 que
- 从 que 中删除头部元素
示例 (C++)
让我们看看下面的实现以更好地理解 -
#include<iostream>
#include<queue>
using namespace std;
class node{
public:
int h_left, h_right, bf, value;
node *left, *right;
};
class tree{
private:
node *get_node(int key);
public:
node *root;
tree(){
root = NULL; //set root as NULL at the beginning
}
void levelorder_traversal(node *r);
node *insert_node(node *root, int key);
};
node *tree::get_node(int key){
node *new_node;
new_node = new node; //create a new node dynamically
new_node->h_left = 0; new_node->h_right = 0;
new_node->bf = 0;
new_node->value = key; //store the value from given key
new_node->left = NULL; new_node->right = NULL;
return new_node;
}
void tree::levelorder_traversal(node *root){
queue <node*> que;
node *item;
que.push(root); //insert the root at first
while(!que.empty()){
item = que.front(); //get the element from the front end
cout << item->value << " ";
if(item->left != NULL) //When left child is present, insert into queue
que.push(item->left);
if(item->right != NULL) //When right child is present, insert into queue
que.push(item->right);
que.pop(); //remove the item from queue
}
}
node *tree::insert_node(node *root, int key){
if(root == NULL){
return (get_node(key)); //when tree is empty, create a node as root
}
if(key < root->value){ //when key is smaller than root value, go to the left
root->left = insert_node(root->left, key);
}
else if(key > root->value){ //when key is greater than root value, go to the right
root->right = insert_node(root->right, key);
}
return root; //when key is already present, do not insert it again
}
main(){
node *root;
tree my_tree;
//Insert some keys into the tree.
my_tree.root = my_tree.insert_node(my_tree.root, 10);
my_tree.root = my_tree.insert_node(my_tree.root, 5);
my_tree.root = my_tree.insert_node(my_tree.root, 16);
my_tree.root = my_tree.insert_node(my_tree.root, 20);
my_tree.root = my_tree.insert_node(my_tree.root, 15);
my_tree.root = my_tree.insert_node(my_tree.root, 8);
my_tree.root = my_tree.insert_node(my_tree.root, 23);
cout << "Level-Order Traversal: ";
my_tree.levelorder_traversal(my_tree.root);
}输入
[10,5,16,null,8,15,20,null,null,null,null,null,null,null,23]
输出
Level-Order Traversal: 10 5 16 8 15 20 23
更新日期：2020-04-28
3K+ 浏览量
广告