BST級別遍歷

好吧，所以我正在嘗試對二叉查找樹進行級別遍歷並且它不工作。下面的代碼對我來說很合理，但這可能是因爲我一直在看它，並且我確信它應該可以工作。BST級別遍歷

void BST<T>::levelByLevel(ostream &out) { 
Queue<BinNodePointer> q; 
BinNodePointer subtreeRoot; 

if(myRoot == NULL) 
    return; 
q.enqueue(myRoot); 
while(!q.empty()) { 
    subtreeRoot = q.front(); 
    out << subtreeRoot->data << " "; 
    q.dequeue(); 

    if(subtreeRoot->left != NULL) 
    q.enqueue(subtreeRoot->left); 
    if(subtreeRoot->right != NULL) 
    q.enqueue(subtreeRoot->right); 
} 
}

也許你們能指出我在做什麼錯誤的，因爲，雖然我知道二叉搜索樹的概念，我不是所有的來龍去脈100％。

來源

2010-05-02 Dalton Conley

那麼你會得到什麼結果？你期望什麼？ – stefanB 2010-05-02 23:00:46

好吧，如果我進入這樣的事情到樹：12 24 18 .. 水平遍歷的輸出爲：12 24 18 ..這是不正確的。我期待的輸出是24 12 18 – 2010-05-02 23:08:19

是'BST <>'AVL？如果不是，那麼你的期望是錯誤的。這個輸入會產生一個有三個級別的樹。如果樹按左右排序排序，那麼你應該得到這樣一棵樹：root是12，左邊的孩子是24，右邊的孩子是NULL; 24的左邊孩子是NULL，24的右邊孩子是18. – wilhelmtell 2010-05-02 23:16:12

結果沒有問題。

你能解釋一下你怎麼在24,12,18到達？

我假設你首先在根級插入12，然後插入24作爲根12的右節點，然後插入18，最終作爲24的左節點 - 因爲18比12更大，所以向右，然後18小於24，因此被插入作爲24

所以，正確的節點：

所以，你有3個級別，級別1（12），2級（24），級別3（ 18），所以級別遍歷12,24,18作爲您的算法插入。

來源

2010-05-02 23:22:35 stefanB

啊謝謝你！它更有意義..事實上，如果我只想把它抽出來，我可能會得出同樣的結論。我的問題是，它來自實驗室手冊，我已經總結出樹的顯示不正確。 – 2010-05-02 23:42:07

回答

相關問題