幫助將值列表插入二叉樹..？

嗯，我一直在這裏一段時間...試圖找出一種算法，將我的隨機數列表插入到二叉樹中。幫助將值列表插入二叉樹..？

這是我迄今爲止得到：

NODEPTR和樹都指向一個節點

NodePtr CreateTree(FILE * fpData) 
{ 
    int in; 

    fscanf(fpData, "%i", &in); 
    Tree T = (NodePtr)malloc(sizeof(Node)); 
    T->Left = NULL; 
    T->Right = NULL; 
    T->value = in; 

    while((fscanf(fpData, "%i", &in)) != EOF) 
    { 
     InsertInTree(in, T); 
     printf("\n %p", T); 
    } 

    return T; 

} 


void InsertInTree(int value,Tree T) 
{ 
    if(T == NULL) 
    { 
     T->Left = (NodePtr)malloc(sizeof(Node)); 
     T->Left->Left = NULL; 
     T->Left->Right = NULL; 
     T->Left->value = value; 
     printf("\n %i ", value); 
     return; 
    } 
    if(T->Left == NULL) 
    { 
     InsertInNull(value, T->Left); 
    } 
    else if(T->Right == NULL) 
    { 
     InsertInNull(value, T->Right); 
    } 
    else 
    { 
     if(T->Left->Left == NULL || T->Left->Right == NULL) InsertInTree(value, T->Left); 
     else InsertInTree(value, T->Right); 
    } 
}

我迷路了。如果一個特定節點的兩個孩子都沒有做什麼空值。我在這裏所做的只是少量數字（1,2,3,5,6），但如果列表較大，它會變得不平衡並且是錯誤的。

來源

2010-11-07 Bri

這個二叉樹的目的是什麼？例如，在二叉搜索樹中，在每個節點上，將要插入的值與該節點的值進行比較。如果它小於（或等於，爲了論點的緣故）你檢查左子樹的值。如果它更大，你檢查正確的。無論何時您嘗試檢查一個空的子樹，都會創建一個新的葉節點併爲其添加值。你似乎總是以任何一種方式未被填充？ – Tommy 2010-11-07 23:11:24

你的選擇是重新平衡自己。或者使用一種略微不同的算法，如自動重新平衡的[紅黑樹] [1]。 [1]：http://en.wikipedia.org/wiki/Red-black_tree – Wolph 2010-11-07 23:11:37

我想我知道我現在需要做什麼....我可能誤解了我對這個二叉樹的設想。我需要訂購它。感謝大家。 – Bri 2010-11-07 23:14:57

在二叉樹中簡單插入並保持二叉樹平衡是不同的問題。我建議你從第一個問題開始，並着重於在樹中保持訂單屬性的正確性。你離這不遠。

然後，你應該看看紅黑樹的經典實現，研究和高效的方法來保持樹木平衡，但是成本更加複雜。

來源

2010-11-07 23:14:29 kriss

它是一個搜索樹嗎？我沒有看到任何if (value < T->Value)條件。

而你有一個InsertNull（未顯示）。這應該沒有必要，1個功能應該足夠了。

爲了解決您的主要問題，使用指針到指針參數或者，更優雅，總是返回一個新的樹：

//untested, no balancing 
Tree InsertValue(Tree t, int value) 
{ 
    if (t == null) 
     t = // create and return new node 
    else 
    { 
     if (value < t->Value) 
     t->Left = InsertValue(t->Left, value); 
     else 
     t->Right = InsertValue(t->Left, value);  
    } 
    return t; 
}

而且在CreateTree：

Tree t = InsertValue(null, in);

來源

2010-11-07 23:15:40

變量'old'是什麼？當然，你的意思是't'？ – 2010-11-07 23:22:42

所以，我試過這個......但是如果我有已經排序的東西......就像1,2,3,4,5,6它只是將它們鏈接在一起.....我怎麼把它放入喜歡一個二叉樹...：\ – Bri 2010-11-07 23:33:59

@Bri：你想要的是一個*平衡的*二叉搜索樹，這比僅僅是一個簡單的二叉搜索樹更具挑戰性。請參閱http://en.wikipedia.org/wiki/Balanced_binary_search_tree以獲取用於平衡二叉查找樹的多種不同算法的鏈接。 – 2010-11-07 23:41:24

由於分配不是針對已排序的樹，您可以以寬度優先的方式填充它。這意味着插入的第一件事一定是根，接下來是下一級的第一個節點，所以它看起來是這樣的：

0 
    1 2 
3 4 5 6

這裏是一個進一步解釋的一篇文章：

http://www.cs.bu.edu/teaching/c/tree/breadth-first/

來源

2010-11-08 01:01:37

有關如何以該格式插入數字列表的任何想法？ – Bri 2010-11-08 02:28:33

它通常使用數組作爲存儲和div/mult在父母和子女之間導航。我想出了一個使用指針來實現的方案，但最終結果太過於人爲。你應該真的和你的老師談談，以便對問題有更清晰的定義。我猜想這是一個排序樹，問題措辭不佳。在CS課程中，我們編寫了一個不平衡的排序樹，並使用pre，post和mid遍歷來打印樹的內容（而不是find函數）。對於CS老師來說，任何其他事情似乎都很奇怪。 – 2010-11-08 06:03:10

幫助將值列表插入二叉樹..？

回答

相關問題