Ошибка отображения обходного двоичного дерева двоичного значения

Question

Неверный дисплей для моего двоичного дерева в порядке прохождения. Я не могу понять, что я делаю неправильно. Выход отображается на уровне 1-15, когда высота равна 4 (включая уровень 0 как 1), а не отображается как: 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15.

основная:

#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 к вашему обходу, чтобы узнать, что я имею в виду.