創建了一個用于二叉樹遍歷、中序和后序列印錯誤序列的程式

我制作了一個程式，該程式接受用戶輸入來創建二叉樹，并帶有根據用戶輸入遍歷所述樹的選項。插入和 Preorder 遍歷作業正常，但由于某種原因，Inorder 遍歷列印與 Preorder 相同的輸出，而 Postorder 遍歷向后列印輸入。我已經檢查了我的插入和遍歷功能一百萬次，但我看不出哪里出錯了......非常感謝幫助！

#include <iostream> 
using namespace std; 
  
struct Node {   
    int data;
    Node *right;
    Node *left;
};


Node *createNode(int data) {
    Node *temp = new Node();
    temp->data = data;
    temp->right = temp->left = NULL;
    return temp;
}


void insertNode(Node* &root, int data) {  
    if(root == NULL)
        root = createNode(data);
    else if(root->data > data)  
        insertNode(root->left, data); 
    else
        insertNode(root->right, data);
}


void printInorder(Node *root) { 
    if(root != NULL){
        printInorder(root->left); 
        cout << root->data << " "; 
        printInorder(root->right); 
    }
}


void printPreorder(Node *root) {
    if(root != NULL){
        cout << root->data << " "; 
        printPreorder(root->left); 
        printPreorder(root->right); 
    }
}


void printPostorder(Node *root) { 
    if(root != NULL){
        printPostorder(root->left);
        printPostorder(root->right);
        cout << root->data << " ";
    }
}

  
int main() 
{ 
    Node *root = NULL;  
    int n, val;         
    int treeOp;
    
    do {                
        
        cout << "\nBINARY TREE OPTIONS";
        cout << "\n------------------------------\n";
        cout << "(1) Insert element(s)";
        cout << "\n(2) Inorder traversal";
        cout << "\n(3) Preorder traversal";
        cout << "\n(4) Postorder traversal";
        cout << "\n(5) Return to main menu\n\n";
        cout << "Enter the number of your choice: ";
        cin >> treeOp;
        cout << endl;
        
        switch(treeOp) {
            case 1: 
                cout << "How many elements will you insert: "; 
                cin >> n;
                cout << "\nInsert " << n <<" elements, hit enter after each:\n";
                for(int i=0; i < n; i  ) {
                    cin >> val, insertNode(root, val); 
                }
                cout << "\nElement(s) inserted!" << endl;
                break;
            case 2:
                if(root == NULL) {
                    cout << "\nNo elements found!\n";
                } else {
                    cout << "INORDER TRAVERSAL OF YOUR BINARY TREE: " << endl;
                    printInorder(root); 
                    cout << endl;
                }
                break;
            case 3:
                if(root == NULL) {
                    cout << "\nNo elements found!\n";
                } else {
                    cout << "PREORDER TRAVERSAL OF YOUR BINARY TREE: " << endl;
                    printPreorder(root);
                    cout << endl;
                }
                break;
            case 4:
                if(root == NULL) {
                    cout << "\nNo elements found!\n"; 
                } else {
                    cout << "POSTORDER TRAVERSAL OF YOUR BINARY TREE: " << endl;
                    printPostorder(root);
                    cout << endl;
                }
                break;
            default:
                if(treeOp!=5){
                    cout << "\nInput invalid, please try again\n";
                }
        }
        
    } while (treeOp != 5);      
  
    return 0; 
} 

不確定我在上面的解釋中是否清楚，但基本上當我插入 1 2 3 4 5 時，我會得到：

• 順序：1 2 3 4 5（錯誤）
• 預購：1 2 3 4 5（右）
• 后序：5 4 3 2 1（錯誤）

uj5u.com熱心網友回復：

你根本沒有犯錯。但是您現在已經親身體驗了樹木平衡的存在理由。（例如紅黑樹或 AVL 樹）

使用您的代碼按該順序插入“1 2 3 4 5”，得到以下樹（也稱為鏈表）：

1
  2
    3
      4
        5

如果您將輸入更改為“3 1 2 4 5”，您將得到一個更加平衡的樹：

     3
   1   4
    2   5

uj5u.com熱心網友回復：

輸入 (1,2,3,4,5) 被排序，并且在插入它們時會產生傾斜的樹結構。

    >       1
    >     /   \
    > left(1)  2
    >          / \
    >    left(2)  3
    >             / \
    >       left(3)  4
    >                / \
    >          left(4)  5
    >                   / \
    >            left(5)  right(5)

在前序遍歷的情況下，所有左邊的節點都是NULL，所以它會先列印根然后向右移動。所以，在前序遍歷中它應該列印

左(1)---->1--->左(2)--->2--->左(3)--->3--->(左4)---->4 ---->(左5)--->5---->右(5)

由于給定輸入 left(1)、left(2)、left(3)、left(4)、left(5) 和 right(5) 為空，因此序列列印為 1、2、3、4， 5 對于前序遍歷是正確的。

同樣，您可以對其他遍歷進行分析。

標籤：C 指针 递归 二叉搜索树 树遍历

上一篇：是否建議在回圈內宣告變數？

下一篇：Go中的陣列不應該表現得像單個變數嗎？