二進制搜索樹打印

Question

我正在爲學校開發一個二叉樹程序，我的一切都很完美。我現在正在處理的是正確的輸出。我的老師希望輸出成爲排序順序的所有數字，後面跟着逗號。

我的代碼，我有完美的排序數字和打印他們，我只是不知道如何刪除最後一個數字後的逗號。

電流輸出：1，2，3，4，

需要是：1，2，3，4

這是我的代碼：

void BinaryTree::inorder(tree_node* p) 
{ 
    if(p != NULL) 
    { 
     if(p->left) 
      inorder(p->left); 

     cout << p->data << ", "; 

     if(p->right) 
      inorder(p->right); 
    } 
    else 
     return; 
} 

我已經嘗試了很少有事情做得對，但我無法弄清楚。

任何幫助將是偉大的。

謝謝。

Answer 1

一個簡單的方法是之前打印的分隔符數據，這樣

cout << ", " << p->data; 

這種方式，我們已經改變了你的問題爲跳過打印第一逗號。這很容易。提示：爲了跟蹤是否跳過逗號，您可能需要爲函數引入另一個參數，因爲它是遞歸函數。

正如xmoex指出的那樣，打印這棵樹的方式更加優雅，因此可讀性和邏輯代碼非常可讀。試着找到這種方式來應對額外的挑戰。

一個無關的提示：您可以放棄return語句，因爲它的冗餘 - 該函數將返回！就像這樣：

void BinaryTree::inorder(tree_node* p) 
{ 
    if (p != NULL) 
    { 
    // stuff goes inside here! 
    } 
    // no return here - the function will return anyway 
} 

這將產生更少的uneccessary代碼，並會幫助你讀自己的代碼，如果你需要，例如，調試它很快一個作業截止日期之前。

Answer 2

變化

cout << p->data << ", "; 
if(p->right) 
{ 
    inorder(p->right); 
} 

到

cout << p->data; 
if(p->right) 
{ 
    cout << ", "; 
    inorder(p->right); 
} 

即，只有當您確定自己是在你的右孩子的東西打印逗號。

Answer 3

我想說你設置一個布爾標誌，你通過參考你的打印例程（和打印例程傳遞標誌周圍，因爲它遞歸）。

最初該標誌設置爲false。當你打印某物時，請檢查旗幟。如果爲false，則將flag設置爲true並打印您的元素。如果已經如此，請打印逗號，空格和元素。

Answer 4

您可以引入一個max()方法，它將指針返回到最右邊的節點，然後比較指向當前節點的指針是否等於最大節點的指針。

tree_node* BinaryTree::max(tree_node *p) { 
    if(p != NULL && p->right != NULL) return max(p->right); 
    return p; 
} 

您需要調用inorder()並傳遞最大的包裝方法，因爲你不想來計算每次遞歸調用最大。

void BinaryTree::print() { 
    inorder(root, max(root)); 
} 

void BinaryTree::inorder(tree_node *p, tree_node *max) { 
    if(p == NULL) return;   

    if(p->left) inorder(p->left, max); 

    cout << p->data; 
    if(p != max) cout << ", "; 

    if(p->right) inorder(p->right, max); 
} 

Answer 5

也許您需要關於該問題的另一個觀點。認爲一個節點作爲
<left subtree> p->data <right subtree>

在您的節點都印像
<left subtree> p->data ", " <right subtree>至極的時刻導致尾隨", "每次

但你不希望每個元素上打印", "。
- >你只想打印", "（在正確的地方）時（只有當！）你decend成樹，否則就沒有必要爲一個分隔符...

有一個很簡單的，實現這一目標沒有隨身帶上......隨意詢問您是否需要進一步的幫助需要任何額外的數據非常優雅的方式......

更新： ，因爲我認爲你的功課是在現在，我想顯示我的解決方案：

void BinaryTree::inorder(tree_node* p) 
{ 
    if(p != NULL) 
    { 
     if(p->left) 
     { 
      inorder(p->left); 
      cout << ", "; // print ", " everytime after you descended to the left 
     } 

     cout << p->data; 

     if(p->right) 
     { 
      cout << ", "; // print ", " everytime before you descend to the right 
      inorder(p->right); 
     } 
    } 
} 

它應該看起來像
<left subtree ", "> p->data <", " rightsubtree>