二進制搜索樹數組實現C++

Im在實現二進制搜索樹的過程中，該樹使用Array實現來表示。這是我到目前爲止的代碼：請注意，我已完成樹的結構並將其保存爲鏈接列表。我想將這個鏈表轉換成一個數組。二進制搜索樹數組實現C++

我對如何去做這件事的想法如下。做一個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) 
}

來源

2013-07-30 Conor F

用數組表示二叉搜索樹並不是一個好主意，除非您知道關於數據的特定信息 – aaronman

如果你想存儲陣列中的樹節點，你最好從你的陣列的位置1啓動，以便家長和孩子之間的關係應該是簡單的：

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

您應該BFS樹，並將節點存儲在數組中（如果節點爲空，您還應該使用標誌ex 0存儲在數組中），則應該獲得樹的數組！

來源

2013-07-30 02:35:26 minicaptain

要做到這一點，你必須遵循這些步驟。

創建一個空隊列。
以root身份創建列表的第一個節點，並將其排入隊列。
直到我們到達列表的末尾，請執行以下操作。

a。從隊列中取出一個節點。這是目前的父母。

b。遍歷列表中的兩個節點，將它們添加爲當前父級的子級。

c。將兩個節點排入隊列。

時間複雜度：上述方案的時間複雜度爲O（n），其中n爲節點數。

來源

2015-10-05 15:12:22

考慮到要有效地存儲二進制搜索樹，使用

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

每一個你遇到樹的葉節點的時間未在樹的結尾處出現（廣度會浪費空間第一）。考慮下面的簡單的例子：

這（當轉化的廣度優先成陣列）導致

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

和廢物兩個時隙在數組中。

現在，如果你想存儲陣列中的同一棵樹不浪費空間，只需將它轉換爲數組深度優先：

[ 2 1 4 3 5 ]

恢復從該原樹，請按照下列步驟爲每個節點：

選擇第一個節點作爲根
對於每個節點（包括根），選擇

a）所述左孩子從陣列的當前鍵

B之後的下一個較小的鍵）右子如從陣列的下一個更大的鍵，是不大於最小的母密鑰較大當您目前在它的左分支

顯然找到正確的b最後分支離開時遇到的，而小於直接父的關鍵）是稍微更復雜，但不會太大。請參閱我的代碼示例here。

如果我沒有弄錯，在任何一種情況下，從一個數組到另一個數組的轉換都將花費O（n）。由於沒有空間浪費，空間複雜性也是O（n）。

這是有效的，因爲二叉搜索樹比普通二叉樹有更多的結構;在這裏，我只是使用左側子元素的二叉搜索樹屬性更小，右側子元素大於當前節點的鍵值。

編輯：

的話題做一些進一步的研究後，我發現，在序遍歷爲了重建樹要簡單得多。這樣做的遞歸函數分別實現了here和here。

它基本上由以下步驟組成：

只要輸入陣列具有看不見條目，
- 如果插入值是更大比當前分支的最小值和少比當前分支的最大允許值，
  - 在當前位置添加一個節點到樹中，並且s等它的值到當前輸入值
  - 卸下輸入電流值
- 如果有剩餘的輸入項目，
  - 遞歸到左子
  - 遞歸到右子

當前的最小值和最大值由樹中的位置定義（左邊的孩子：小於父母，右邊的孩子：大於父母）。

欲瞭解更詳細的細節，請參閱我的源代碼鏈接。

來源

2016-01-23 22:13:35

二進制搜索樹數組實現C++

回答

相關問題