在AVL樹上設置父項

我想實現一個AVL樹，並且不確定插入和跟蹤每個節點的父項的最佳方法。這是教育，所以請不要建議「使用提升」:)在AVL樹上設置父項

這編譯，但我不相信它的正確性或它是最好的方法。具體這個

insert(someNumber,root,root);

另外，我會重做高度一部分，當我重新平衡和移樹。

我插入這樣

myTree.insert(someNumber);

這裏是方法。我不確定我的第二個參數應該在這裏。我會認爲NULL，但編譯器不喜歡（不同的函數定義）。

void Tree::insert(int someNumber){ 
    insert(someNumber,root,root); 
}

這裏是我的插入

void Tree::insert(int someNumber,Node*& subTreeRoot,Node*& parent){ 
    if(subTreeRoot==NULL) 
    { 
     subTreeRoot = new Node(someNumber,parent); 
     if(subTreeRoot->myParent) 
    } 
    else if (someNumber<subTreeRoot->myNumber) 
    { 
     if((subTreeRoot->right==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL))) 
      subTreeRoot->height++; 
     insert(someNumber,subTreeRoot->left,subTreeRoot); 
    } 
    else 
    { 
     if((subTreeRoot->left==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL))) 
      subTreeRoot->height++; 
     insert(someNumber,subTreeRoot->right,subTreeRoot); 
    } 
}

來源

2010-08-06 Maestro1024

既然你是爲教育這樣做，我會建議你制定一些情況下進行手工，然後將它們編碼到的測試表格

Insert(6); 
Insert(11); 
// ... 
Insert(3); 

Node test = root; 
assert(root->height == 3); 
assert(root->value == 6); 
test = root->right; 
assert(...);

這些數字是完全組成的。

這將

給您的感覺更多的是對你的代碼是否正在工作。（提示：如果你不確定你的代碼是否正常工作，它可能不是）
給你一個地方開始搞清楚發生了什麼問題。
培養測試習慣。對一些人來說，編寫兩倍的代碼（測試+代碼）比首先編寫代碼更快，但嘗試它是違反直覺的。另外寫更多的代碼=更多的練習。

來源

2010-08-06 00:23:55 deinst

我一直在測試相當多。你的斷言看起來不錯。我真的很喜歡eclipse cdt的單元測試插件或框架。這就是說，我不知道這回答有關父母的一點。我想我會進行重新平衡並通過父母測試。 – Maestro1024 2010-08-06 00:56:47

樹和節點之間有什麼區別？（樹只是根節點的佔位符，僅此而已，一個節點有時被認爲有兩個子樹，Tree和Node沒有區別，一個類就足夠了）。什麼時候需要它？更容易編程和校正正確。如果性能傷害了你，你總是可以改變函數返回一個緩存值。

節點不應該知道它是父節點（在我看來）。所以插入功能需要一個父參數。創建新節點後，比較父母孩子的深度，看看你是否需要做任何旋轉。編程旋轉是棘手的：嘗試，調試和測試！

Node::insert(int number,Node * parent) 
{ 
    //code 
    left=new node(number); 
    if (parent->left->depth() > parent->right->depth()+1) 
    parent->rotate_tree_or_something(); 
    // 
}

來源

2010-08-06 00:28:53 Ishtar

節點是樹的一部分。節點1 /\ 節點2節點3 你會如何「新節點比較父母 - 孩子的深度」沒有親子關係？ – Maestro1024 2010-08-06 01:00:54

如果一個節點不知道它是父節點，那麼在AVL樹中，在重新平衡時如何爬樹？ – 2010-09-30 14:33:09

在AVL樹上設置父項

回答

相關問題