首页 > 代码库 > IT公司100题-16-层遍历二元树
IT公司100题-16-层遍历二元树
问题描述：
层遍历二叉树，同一层从左往右打印。
定义二元查找树的结点为：
typedef struct BSTreeNode { int data; BSTreeNode *left; BSTreeNode *right;} Node;
例如输入二叉树：
6
/ \
4 12
/ \ / \
2 5 8 16
/ \
4 12
/ \ / \
2 5 8 16
输出：6 4 12 2 5 8 16。
分析：
二叉树的广度优先遍历。
代码实现：
1 // 16.cc 2 #include <deque> 3 #include <iostream> 4 using namespace std; 5 6 typedef struct BSTreeNode { 7 int data; 8 BSTreeNode *left; 9 BSTreeNode *right;10 } Node;11 12 // 创建二元查找树13 void add_BSTree_node(Node* &p_current, int data) {14 if (NULL == p_current) {15 Node *node = new Node();16 node->left = NULL;17 node->right = NULL;18 node->data =http://www.mamicode.com/ data;19 p_current = node;20 } else {21 if (p_current->data > data)22 add_BSTree_node(p_current->left, data);23 else if (p_current->data < data)24 add_BSTree_node(p_current->right, data);25 else26 cout << "The data has already in the Node.";27 }28 }29 30 // 层遍历31 void level_order(Node* root) {32 deque<Node*> s;33 s.push_back(root);34 Node* p;35 36 while (!s.empty()) {37 p = s.front();38 s.pop_front();39 cout << p->data << " ";40 41 if (p->left != NULL)42 s.push_back(p->left);43 if (p->right != NULL)44 s.push_back(p->right);45 }46 cout << endl;47 }48 49 int main() {50 Node *root = NULL;51 add_BSTree_node(root, 6);52 add_BSTree_node(root, 4);53 add_BSTree_node(root, 12);54 add_BSTree_node(root, 2);55 add_BSTree_node(root, 5);56 add_BSTree_node(root, 8);57 add_BSTree_node(root, 16);58 59 level_order(root);60 return 0;61 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。