您好,想要实现一个二叉树,需要用到结构体来存储每个节点的信息,并使用指针来存储每个节点的左右子节点的地址。具体的实现方法可以参考下面的代码示例:
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val
struct TreeNode *left
struct TreeNode *right
}
struct TreeNode* createNode(int val) {
struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode))
node->val = val
node->left = NULL
node->right = NULL
return node
}
void insertNode(struct TreeNode* root, int val) {
if (root == NULL) {
return
}
if (val <root->val) {
if (root->left == NULL) {
root->left = createNode(val)
} else {
insertNode(root->left, val)
}
} else {
if (root->right == NULL) {
root->right = createNode(val)
} else {
insertNode(root->right, val)
}
}
}
void printTree(struct TreeNode* root) {
if (root == NULL) {
return
}
printf("%d\n", root->val)
printTree(root->left)
printTree(root->right)
}
int main() {
struct TreeNode* root = createNode(5)
insertNode(root, 3)
insertNode(root, 2)
insertNode(root, 4)
insertNode(root, 7)
insertNode(root, 6)
insertNode(root, 8)
printTree(root)
return 0
}
在这段代码中,我们定义了一个结构体 TreeNode 来表示二叉树的每个节点,结构体中包含了一个节点的数值 val,以及指向左子节点和右子节点的指针 left 和 right。
创建二叉树的源程序如下:
#include <cstdlib>
#include <stdio.h>
typedef struct node
{ //树的结点
int data
struct node* left
struct node* right
} Node
typedef struct
{ //树根
Node* root;
} Tree
void insert(Tree* tree, int value)//创建树
{
Node* node=(Node*)malloc(sizeof(Node))//创建一个节点
node->data = value
node->left = NULL
node->right = NULL
if (tree->root == NULL)//判断树是不是空树
{
tree->root = node
}
else
{//不是空树
Node* temp = tree->root//从树根开始
while (temp != NULL)
{
if (value <temp->data)//小于就进左儿子
{
if (temp->left == NULL)
{
temp->left = node
return
}
else
{//继续判断
temp = temp->left
}
}
else {//否则进右儿子
if (temp->right == NULL)
{
temp->right = node
return
}
else {//继续判断
temp = temp->right
}
}
}
}
return;
}
void inorder(Node* node)//树的中序遍历
{
if (node != NULL)
{
inorder(node->left)
printf("%d ",node->data)
inorder(node->right)
}
}
int main()
{
Tree tree
tree.root = NULL//创建一个空树
int n
scanf("%d",&n)
for (int i = 0i <ni++)//输入n个数并创建这个树
{
int temp
scanf("%d",&temp)
insert(&tree, temp)
}
inorder(tree.root)//中序遍历
getchar()
getchar()
return 0
}
扩展资料:
简单二叉树定义范例:此树的顺序结构为:ABCDE
#include <cstdlib>
#include <stdio.h>
#include <string>
int main()
{
node* p = newnode
node* p = head
head = p
string str
cin >>str
creat(p, str, 0)//默认根结点在str下标0的位置
return 0
}
//p为树的根结点(已开辟动态内存),str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组,r当前结点所在顺序存储数组位置
void creat(node* p, string str, int r)
{
p->data = str[r]
if (str[r * 2 + 1] == '#' || r * 2 + 1 >str.size() - 1)p->lch = NULL;
else
{
p->lch = newnode
creat(p->lch, str, r * 2 + 1)
}
if (str[r * 2 + 2] == '#' || r * 2 + 2 >str.size() - 1)p->rch = NULL
else
{
p->rch = newnode
creat(p->rch, str, r * 2 + 2)
}
}