二叉樹inorder遍歷顯示錯誤

Question

二叉樹按順序遍歷顯示是錯誤的。我無法弄清楚我做錯了什麼。當高度爲4（包括0級爲1）時，輸出顯示爲1-15，而不是顯示爲：8 4 9 2 10 5 11 1 12 6 13 3 14 7 15.

main：

#include <iostream> 
#include "math.h" 
#include "bintree.h" 
using namespace std; 

int main() 
{ 
    binary_tree bin; 
    int tmp, num, height; 

     cout << "Please enter a height that you wish to see: " ; 
     cin >> height; 
     cout << endl << endl; 

     bin.insert(num, height); 

     cout << "The In-Order Traversal is: " ; 
     bin.displayinorder(); 
     cout << endl << endl; 



    system("Pause"); 
    return 0; 
} 

void binary_tree::insert(int num, int height) 
{ 
    num = pow(2, height); 

    for(int i = 1; i < num; i++) 
    { 
    node* t = new node; 
    node* parent; 
    t-> data = i; 
    t-> left = NULL; 
    t-> right = NULL; 
    parent = NULL; 

    if(isEmpty()) root = t; 
    else 
    { 
     node* curr; 
     curr = root; 

     while(curr) 
     { 
      parent = curr; 
      if(t->data > curr->data) curr = curr->right; 
      else curr = curr->left; 
     } 

     if(t->data < parent->data) 
      parent->left = t; 
     else 
      parent->right = t; 
     } 
    } 
} 


void binary_tree::displayinorder() 
{ 
    inorder(root); 
} 

void binary_tree::inorder(node* p) 
{ 
    if(p) 
    { 
     inorder(p -> left); 
     cout<< " " << p->data <<" "; 
     inorder(p -> right); 
    } 
} 

void binary_tree::displaypreorder() 
{ 
    preorder(root); 
} 

void binary_tree::preorder(node* p) 
{ 
    if(p != NULL) 
    { 
     cout<<" "<< p -> data <<" "; 
     preorder(p -> left); 
     preorder(p -> right); 
    } 
    else return; 
} 

頭：

#ifndef BINTREE_H 
#define BINTREE_H 
#include <cstdlib> // Provides NULL and size_t 

    class binary_tree 
    { 
     private: 
     struct node 
     { 
      node* left; 
      node* right; 
      int data; 
     }; 
     node* root; 

    public: 
     binary_tree() 
     { 
      root = NULL; 
     } 

     bool isEmpty() const 
     { 
      return root==NULL; 
     } 

     void displayinorder(); 
     void inorder(node*); 

     void displaypreorder(); 
     void preorder(node*); 

     void insert(int, int); 
}; 

#endif 

Answer 1

我覺得你不清楚是什麼有序手段。 1 ... 15是包含值1 ... 15的二叉查找樹的按序遍歷的預期輸出。您給出的序列聽起來像預訂在平衡二叉搜索樹上。

換句話說，您的遍歷代碼對於按順序遍歷是正確的。

那就是說，你的樹代代碼不會產生平衡樹。按順序的遍歷不會公開那個，但是預訂或者後序遍歷。因爲你按增加的順序插入所有的值，你會得到一棵完全由正確的孩子構成的樹。在你的遍歷中添加一些cout語句來查看我的意思。