二叉树 层序遍历建树 c++
时间: 2023-08-29 09:11:11 浏览: 69
根据提供的引用内容,可以通过层序遍历的方式来建立二叉树。具体的实现过程如下:
首先,需要定义一个二叉树的数据结构和一个队列的数据结构。二叉树的定义可以包括节点的数据和左右子节点的指针。队列可以使用数组或链表实现,用来存储节点指针。
接下来,可以借助一个辅助队列来进行层序遍历建树。首先,将二叉树的根节点入队。然后,循环执行以下操作:出队一个节点,访问该节点;如果该节点有左子树,则将左子树的根节点入队;如果该节点有右子树,则将右子树的根节点入队。直到队列为空时,建树的过程结束。
下面是一个示例的实现过程:
```c++
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
Node* createNode(int data) {
Node* newNode = new Node();
if (!newNode) {
cout << "Memory error\n";
return NULL;
}
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insertNode(Node* root, int data) {
// If the tree is empty, assign a new node address to the root
if (root == NULL) {
root = createNode(data);
return root;
}
// Else, do level order traversal until we find an empty
// position, i.e. either left child or right child of some
// node is pointing to NULL.
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
if (temp->left != NULL)
q.push(temp->left);
else {
temp->left = createNode(data);
return root;
}
if (temp->right != NULL)
q.push(temp->right);
else {
temp->right = createNode(data);
return root;
}
}
return root;
}
void levelOrderTraversal(Node* root) {
if (root == NULL)
return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
cout << temp->data << " ";
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
}
int main() {
Node* root = NULL;
int data;
// Insert nodes in level order
root = insertNode(root, 1);
root = insertNode(root, 2);
root = insertNode(root, 3);
root = insertNode(root, 4);
root = insertNode(root, 5);
// Level order traversal of the tree
cout << "Level Order Traversal: ";
levelOrderTraversal(root);
return 0;
}
```
这段代码实现了二叉树的层序遍历建树过程,并对建立好的二叉树进行层序遍历输出。你可以根据自己的需求进行修改和扩展。希望对你有帮助!<span class="em">1</span><span class="em">2</span>
#### 引用[.reference_title]
- *1* *2* [二叉树的层序遍历(c++)](https://blog.csdn.net/qq_45519325/article/details/129207375)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]