二进制搜索树数组实现C++

Question

二进制搜索树数组实现C++

Con*_*nor 1 c++ arrays binary-search-tree

我正在实现使用Array实现表示的二进制搜索树.这是我到目前为止的代码:请注意我完成了树的结构并将其保存为链接列表.我想将此链表转换为数组.

关于如何解决这个问题的想法如下.创建一个return_array函数.将数组的大小设置为最大节点数(2 ^(n-1)+1)并通过链接列表.根节点将是阵列上的@ postion 0,然后他的L-child =(2*[index_of_parent] +1)并且R-child =(2*[index_of_parent] +2).我环顾四周寻找一些可以让我知道如何保持每个节点的固定以及如何通过每个节点的东西.

我是否在思考这个问题？可以有递归吗？

我也在考虑创建一个可视树而不是一个数组,但不知道如何正确地将它分隔出来.如果有人知道如何做到这一点,那么更好地理解它将是非常棒的.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cmath>

using namespace std;

struct node { 
    int data; 
    struct node* left; 
    struct node* right; 
};

void inorder(struct node* node){
    if(node){
        inorder(node->left);
        cout << node->data << " ";
        inorder(node->right);
    }
}

void insert(struct node** node, int key){

    if(*node == NULL){
        (*node) = (struct node*)malloc(sizeof(struct node));
        (*node)->data = key;
        (*node)->left = NULL;
        (*node)->right = NULL;
        printf("inserted node with data %d\n", (*node)->data);
    }
    else if ((*node)->data > key){
        insert((&(*node)->left),key);

    }
    else
        insert((&(*node)->right),key);
}

int max_tree(struct node* node){
    int left,right;
    if(node == NULL)
       return 0;
    else
    {
      left=max_tree(node->left);
      right=max_tree(node->right);
      if(left>right)
         return left+1;
      else
         return right+1;
}
}

//This is where i dont know how to keep the parent/children the array.
void return_array(struct node* node, int height){
    int max;
    height = height - 1;
    max = pow(2, height) - 1;
    int arr [height];








}

int main(){
    int h;
    struct node* root = NULL;

    insert(&root, 10);
    insert(&root, 20);
    insert(&root, 5);
    insert(&root, 2);


   inorder(root);
   cout << endl;
   cout << "Height is: ";
   cout << max_tree(root);
   h = max_tree(root)
   return_array(root, h)
}

Run Code Online (Sandbox Code Playgroud)