完全二叉树存入二叉链表
时间: 2023-12-04 17:41:44 浏览: 39
完全二叉树可以通过二叉链表来存储,具体实现方法如下:
1.定义二叉树节点结构体,包括节点值、左右子节点指针。
2.定义一个数组来存储完全二叉树的节点值,按照完全二叉树的顺序存储。
3.从根节点开始,按照完全二叉树的顺序依次遍历数组,将节点值存储到对应的节点中。
4.如果当前节点的下标为i,则它的左子节点下标为2i,右子节点下标为2i+1。
5.如果当前节点的下标为i,则它的父节点下标为i/2。
6.如果数组中的某个位置没有节点值,则对应的节点指针为空。
下面是一个C++的实现代码示例:
```cpp
#include <iostream>
using namespace std;
// 定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 将完全二叉树存入二叉链表
TreeNode* createTree(int arr[], int n, int i) {
if (i >= n || arr[i] == -1) {
return NULL;
}
TreeNode* root = new TreeNode(arr[i]);
root->left = createTree(arr, n, 2 * i + 1);
root->right = createTree(arr, n, 2 * i + 2);
return root;
}
// 测试代码
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
TreeNode* root = createTree(arr, n, 0);
return 0;
}
```