2

我正在实现一个使用 Array 实现表示的二叉搜索树。到目前为止，这是我的代码：注意我已经完成了树的结构，它被保存为链接列表。我想将此链表转换为数组。

我对如何解决这个问题的想法如下。制作一个 return_array 函数。将数组的大小设置为最大节点数（2^（n-1）+1）并遍历链表。根节点将是数组上的@位置 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)
}
4

3 回答 3

9

考虑到您想要有效地存储二叉搜索树，使用

l = 2i + 1
r = 2i + 2

每次您的树遇到未出现在树末尾的叶节点时（广度优先），都会浪费空间。考虑以下简单示例：

  2
 / \
1   4
   / \
  3   5

这（当将广度优先转换为数组时）导致

[ 2, 1, 4, -, -, 3, 5 ]

并浪费了阵列中的两个插槽。

现在，如果您想在不浪费空间的情况下将同一棵树存储在数组中，只需将其转换为数组depth-first：

[ 2 1 4 3 5 ]

要从中恢复原始树，请对每个节点执行以下步骤：

  1. 选择第一个节点作为根

  2. 对于每个节点（包括根节点），选择

    a）左孩子作为当前键之后数组中的下一个较小的键

    b）右孩子作为数组中的下一个更大的键，不大于最后一次左分支时遇到的最小父键，并且小于当前在其左分支中的直接父键

显然，找到正确的 b)稍微复杂一些，但不会太多。在此处参考我的代码示例。

如果我没记错的话，在任何一种情况下，与数组之间的转换都需要 O(n) 。由于没有空间浪费，空间复杂度也是 O(n)。

这是因为二叉搜索树比普通二叉树有更多的结构。在这里，我只是使用左孩子的二叉搜索树属性较小，而右孩子比当前节点的键大。

编辑：

在对该主题进行了进一步研究之后，我发现以前序遍历顺序重建树要简单得多。执行此操作的递归函数分别在此处和此处实现。

它基本上由以下步骤组成：

  • 只要输入数组有看不见的条目，
    • 如果要插入的值大于当前分支的最小值且小于当前分支允许的最大值，
      • 在当前位置向树添加一个节点并将其值设置为当前输入值
      • 从输入中删除当前值
    • 如果输入中有剩余的项目，
      • 递归到左孩子
      • 递归到右孩子

当前的最小值和最大值由树内的位置定义（左子：小于父，右子：大于父）。

更详细的细节，请参考我的源代码链接。

于 2016-01-23T22:13:35.593 回答
5

如果要将树节点存储在数组中，最好从数组的 1 个位置开始！所以父节点和子节点之间的关系应该很简单：

parent = n;
left = 2n;
right = 2n + 1;

您应该对树进行 BFS，并将节点存储在数组中（如果节点为空，您还应该使用标志 ex 0 将节点存储在数组中），您应该得到树的数组！

于 2013-07-30T02:35:26.903 回答
0

为此，您必须按照以下步骤操作。

  1. 创建一个空队列。
  2. 将列表的第一个节点设为根节点，并将其加入队列。

  3. 在我们到达列表末尾之前，请执行以下操作。

    一个。从队列中取出一个节点。这是当前的父级。

    湾。遍历列表中的两个节点，将它们添加为当前父节点的子节点。

    C。将两个节点排入队列。

时间复杂度：上述解决方案的时间复杂度为 O(n)，其中 n 是节点数。

于 2015-10-05T15:12:22.513 回答