用c++建立一个完全二叉树
时间: 2024-02-18 19:30:17 浏览: 18
用C语言建立一个完全二叉树的过程如下:
1. 定义结构体Node,表示二叉树节点的结构体。该结构体包含三个成员变量:一个整数值data,以及两个指向左右子节点的指针left和right。
```
struct Node {
int data;
struct Node *left;
struct Node *right;
};
```
2. 定义一个函数createNode,负责创建新节点并初始化。该函数接受一个整数值作为参数,返回一个指向新节点的指针。
```
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
```
3. 定义一个函数insertNode,负责向完全二叉树中插入新节点。该函数接受三个参数:一个指向根节点的指针root,一个表示新节点要插入的位置的二进制整数index,以及一个表示新节点的值的整数data。
```
void insertNode(struct Node** root, int index, int data) {
if (*root == NULL) {
*root = createNode(data);
return;
}
int height = floor(log2(index + 1));
int mask = (1 << height) - 1;
int parentIndex = (index & ~mask) >> 1;
struct Node* parent = *root;
for (int i = height - 2; i >= 0; i--) {
if (parent == NULL) {
return;
}
if ((parentIndex & (1 << i)) == 0) {
parent = parent->left;
} else {
parent = parent->right;
}
}
if (parent == NULL) {
return;
}
struct Node* newNode = createNode(data);
if ((index & 1) == 0) {
parent->left = newNode;
} else {
parent->right = newNode;
}
}
```
4. 在主函数中,声明一个指向根节点的指针root。调用insertNode函数来插入新节点。
```
int main() {
struct Node* root = NULL;
insertNode(&root, 0, 1);
insertNode(&root, 1, 2);
insertNode(&root, 2, 3);
insertNode(&root, 3, 4);
insertNode(&root, 4, 5);
insertNode(&root, 5, 6);
return 0;
}
```
5. 完成后,该程序会生成一个如下显示的完全二叉树:
```
1
/ \
2 3
/ \ /
4 5 6
```