如何非递归创建二叉树
时间: 2024-01-23 14:11:43 浏览: 23
非递归创建二叉树的方法可以使用栈来实现。具体步骤如下:
1. 创建一个空栈,并将根节点压入栈中。
2. 当栈不为空时,执行以下步骤:
3. 弹出栈顶节点为当前节点。
4. 输入当前节点的值。
5. 询问用户是否有左子节点。如果有,创建左子节点并将其压入栈中。
6. 询问用户是否有右子节点。如果有,创建右子节点并将其压入栈中。
7. 当栈为空时,表示所有节点已遍历完毕,二叉树创建完成。
相关问题
非递归创建二叉树c语言
以下是C语言实现非递归创建二叉树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct tree{
int data;
struct tree * left;
struct tree * right;
}Bitree, *pBitree;
pBitree CreateTree(){
pBitree root = NULL, p = NULL;
int data;
scanf("%d", &data);
while (data != -1){
p = root;
pBitree node = (pBitree)malloc(sizeof(Bitree));
node->data = data;
node->left = NULL;
node->right = NULL;
if (root == NULL){
root = node;
}
else{
while (1){
if (data < p->data){
if (p->left == NULL){
p->left = node;
break;
}
else{
p = p->left;
}
}
else{
if (p->right == NULL){
p->right = node;
break;
}
else{
p = p->right;
}
}
}
}
scanf("%d", &data);
}
return root;
}
void Preorder(pBitree root){
if (root){
printf("%d\n", root->data);
Preorder(root->left);
Preorder(root->right);
}
else{
return;
}
}
int main(){
pBitree root = CreateTree();
Preorder(root);
return 0;
}
```
该代码中,CreateTree()函数用于创建二叉树,Preorder()函数用于先序遍历二叉树。在CreateTree()函数中,我们使用了一个while循环来读取用户输入的数据,并根据数据的大小来判断新节点应该插入到左子树还是右子树中。在插入新节点时,我们使用了一个while循环来找到新节点应该插入的位置。
程序设计非递归创建二叉树
非递归创建二叉树可以使用栈来实现。具体步骤如下:
1. 创建一个栈,并将根节点入栈。
2. 循环执行以下步骤,直到栈为空:
- 弹出栈顶元素,作为当前节点。
- 接收用户输入,判断用户输入是否为左子树节点的值,如果是则创建左子节点,并将左子节点入栈。
- 如果用户输入不是左子树节点的值,那么就弹出当前节点,再接收用户输入,判断用户输入是否为右子树节点的值,如果是则创建右子节点,并将右子节点入栈。
3. 完成二叉树的创建。
下面是示例代码实现:
```
#include <iostream>
#include <stack>
using namespace std;
// 二叉树节点结构体
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* createBinaryTree() {
int val;
cout << "请输入根节点的值:";
cin >> val;
TreeNode* root = new TreeNode(val);
stack<TreeNode*> nodeStack;
nodeStack.push(root);
while (!nodeStack.empty()) {
TreeNode* cur = nodeStack.top();
nodeStack.pop();
int leftVal, rightVal;
cout << "请输入节点 " << cur->val << " 的左子节点的值(-1表示无左子节点):";
cin >> leftVal;
if (leftVal != -1) {
TreeNode* leftNode = new TreeNode(leftVal);
cur->left = leftNode;
nodeStack.push(leftNode);
}
cout << "请输入节点 " << cur->val << " 的右子节点的值(-1表示无右子节点):";
cin >> rightVal;
if (rightVal != -1) {
TreeNode* rightNode = new TreeNode(rightVal);
cur->right = rightNode;
nodeStack.push(rightNode);
}
}
return root;
}
int main() {
TreeNode* root = createBinaryTree();
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)