BST與遞歸和給定的結構

我必須編寫一些BST的方法，我有一些問題，讓我解釋一下。BST與遞歸和給定的結構

我具有以下結構：

struct node { 
    struct node *lChild; 
    struct node *rChild; 
    int value; 
};

和

struct tree { 
    struct node *root; 
};

具有以下功能沿着：

struct tree* constructNewTree() 
{ 
    struct tree *T=malloc(sizeof(struct tree)); 
    T->root=NULL; 

    return T; 
}

和

struct node* constructNewNode(int i) 
{ 
    struct node *N=malloc(sizeof(struct node)); 
    N->value=i; 
    N->lChild=NULL; 
    N->rChild=NULL; 

    return N; 
}

在我主我必須調用此（例如）：

int main() 
{ 
    struct tree *T; 
    T=constructNewTree(); 

    insertKey(5,T); 
    insertKey(2,T); 
    insertKey(9,T); 
    return 0; 
}

我要做的就是創建功能insertKey（INT I，結構樹* T）使用遞歸。

我想做一些像

void insertKey(int i, struct tree *T) 
{ 
    if (T->root==NULL) { 
     T->root=constructNewNode(i); 
     return; 
    } 
    else { 
     if (i<=T->root->value) { 
      T->root->lChild=constructNewNode(i); 
     else if (i>T->root->value) { 
      T->root->rChild=constructNewNode(i); 
     } 
    } 
}

但是它沒有得到很遠，使用遞歸，讓我再次打電話insertKey，但我似乎無法使用節點和樹同樣的方式。

有誰知道我怎麼能做到這一點，而不改變給定的結構？

非常感謝。

來源

2011-03-20 Sword22

這看起來像是一個家庭作業問題。標籤更新得當。 – BMitch 2011-03-20 18:21:29

您的insertKey以Tree爲參數。樹只是一個指向最頂層的指針。

我推薦你做的是寫一個insertKey函數，它的參數需要一個Node。同樣在這個函數中，你必須檢查左/右兒童是否有另一棵樹。

目前您只是構造一個新的節點，不管有什麼。這將覆蓋任何以前的插入。

來源

2011-03-20 18:47:26 Starkey

謝謝，但不會弄亂主要（）上的代碼？也許我應該創建一個其他函數insertNode，做同樣的事情，但節點，然後在insertKey檢查如果T>根是空的，如果沒有使用insertNode與T>根作爲參數？ – Sword22 2011-03-20 19:01:58

+1這是正確的做法。現在給Starkey +15，這樣我們就可以繼續:) – ralphtheninja 2011-03-20 19:09:22

只是最後一個問題之前，我這樣做，對於其他方法，我必須像findKey（int i，struct tree * T）或deleteKey（int i，struct tree * T），每次都會出現同樣的問題，我是否應該按照相同的方式進行操作？ – Sword22 2011-03-20 20:32:34

BST與遞歸和給定的結構

回答

相關問題