请给出C语言构建排序二叉树的具体代码
时间: 2023-09-23 20:05:46 浏览: 65
### 回答1:
#include <stdio.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
/* function to create a new node of tree and returns pointer */
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* function for inorder traversal */
void inorder(struct node* root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
/* function to insert data recursively */
struct node* insert(struct node* node, int data)
{
/* if the tree is empty, return a new node */
if (node == NULL) return newNode(data);
/* otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);
/* return the (unchanged) node pointer */
return node;
}
/* Driver program to test above functions */
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
// print inoder traversal of the BST
inorder(root);
return 0;
}答:这是用C语言构建排序二叉树的具体代码:#include <stdio.h>struct node {int data;struct node *left;struct node *right;};/* function to create a new node of tree and returns pointer */struct node* newNode(int data){struct node* node = (struct node*)malloc(sizeof(struct node));node->data = data;node->left = NULL;node->right = NULL;return(node);}/* function for inorder traversal */void inorder(struct node* root){if (root != NULL){inorder(root->left);printf("%d ", root->data);inorder(root->right);}}/* function to insert data recursively */struct node* insert(struct node* node, int data){/* if the tree is empty, return a new node */if (node == NULL) return newNode(data);/* otherwise, recur down the tree */if (data <= node->data)node->left = insert(node->left, data);elsenode->right = insert(node->right, data);/* return the (unchanged) node pointer */return node;}/* Driver program to test above functions */int main(){/* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */struct node *root = NULL;root = insert(root, 50);insert(root, 30);insert(root, 20);insert(root, 40);insert(root, 70);insert(root, 60);insert(root, 80);// print inoder traversal of the BSTinorder(root);return 0;}
### 回答2:
以下是用C语言构建排序二叉树的具体代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct node {
int data;
struct node* left;
struct node* right;
} Node;
// 创建新的节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// 将节点插入二叉树
Node* insertNode(Node* root, int data) {
// 如果根节点为空,则将数据创建为根节点
if (root == NULL) {
root = createNode(data);
return root;
}
// 如果数据小于根节点的值,则将数据插入到左子树中
else if (data < root->data) {
root->left = insertNode(root->left, data);
}
// 如果数据大于等于根节点的值,则将数据插入到右子树中
else {
root->right = insertNode(root->right, data);
}
return root;
}
// 前序遍历二叉树(根-左-右)
void preOrder(Node* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
int main() {
Node* root = NULL;
int inputData[] = { 6, 4, 8, 2, 5, 7, 9 };
// 插入数组中的元素到二叉树中
int i;
for (i = 0; i < sizeof(inputData) / sizeof(inputData[0]); i++) {
root = insertNode(root, inputData[i]);
}
printf("前序遍历结果:");
preOrder(root);
return 0;
}
```
这段代码首先定义了一个节点结构体,结构体中包含节点数据和指向左右子节点的指针。然后定义了创建节点的函数`createNode`和插入节点的函数`insertNode`。在插入节点的函数中,如果根节点为空,则将数据创建为根节点;如果数据小于根节点的值,则将数据插入到左子树中;如果数据大于等于根节点的值,则将数据插入到右子树中。最后定义了一个前序遍历二叉树的函数`preOrder`,用来递归遍历二叉树并输出节点的值。在主函数中,首先初始化根节点为NULL,然后将数组中的元素都插入到二叉树中,最后调用前序遍历函数输出排序后的结果。
### 回答3:
要构建一个排序二叉树,首先需要定义二叉树的结构。可以使用如下的C语言代码定义一个二叉树的结构:
```c
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
```
接下来,可以通过递归的方式来构建排序二叉树。具体代码如下:
```c
struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
if (root == NULL) {
// 如果二叉树为空,则创建一个新的节点作为根节点
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
if (val < root->val) {
// 如果插入的值小于当前节点的值,则递归地插入到左子树中
root->left = insertIntoBST(root->left, val);
} else {
// 如果插入的值大于等于当前节点的值,则递归地插入到右子树中
root->right = insertIntoBST(root->right, val);
}
return root;
}
```
在上述代码中,`insertIntoBST`函数用于向排序二叉树中插入一个新的节点。当二叉树为空时,创建一个新节点作为根节点。如果要插入的值小于当前节点的值,则递归地插入到左子树中;如果要插入的值大于等于当前节点的值,则递归地插入到右子树中。最后返回根节点。
通过多次调用`insertIntoBST`函数,就可以依次插入多个节点,从而构建出一个排序二叉树。