BinaryTree插入方法

Question

對於類我必須創建一個binaryTree，我似乎無法讓插入方法正常工作。

預期的結果：

first: tree is not empty 
     no of nodes = 15 
     height of tree = 5 

The elements of 'first' in inorder: 
     -11 8 -3 12 -1 -9 -5 2 16 10 6 -13 4 14 -7 
The elements of 'first' in preorder: 
     2 -1 -3 8 -11 12 -5 -9 4 6 10 16 -13 -7 14 
The elements of 'first' in postorder: 
     -11 8 12 -3 -9 -5 -1 16 10 -13 6 14 -7 4 2 

second: tree is not empty 
     no of nodes = 9 
     height of tree = 4 

The elements of 'second' in inorder: 
     7 3.25 0.75 -7.75 -0.5 -11.5 4.5 -4 8.25 
The elements of 'second' in preorder: 
     -0.5 0.75 3.25 7 -7.75 -4 4.5 -11.5 8.25 
The elements of 'second' in postorder: 
     7 3.25 -7.75 0.75 -11.5 4.5 8.25 -4 -0.5 

third: tree is not empty 
     no of nodes = 7 
     height of tree = 4 

The elements of 'third' in inorder: 
     objects. list is string This of a 
The elements of 'third' in preorder: 
     This is list objects. string a of 
The elements of 'third' in postorder: 
     objects. list string is of a This 

我的結果：

first: tree is not empty 
     no of nodes = 15 
     height of tree = 4 
The elements of 'first' in inorder: 
-9 -5 4 16 -1 -13 10 -7 2 14 8 6 -3 -11 12 
The elements of 'first' in preorder: 
2 -1 4 -5 -9 16 -7 10 -13 -3 6 8 14 12 -11 
The elements of 'first' in postorder: 
-9 -5 16 4 -13 10 -7 -1 14 8 6 -11 12 -3 2 
second: tree is not empty 
     no of nodes = 9 
     height of tree = 3 
The elements of 'second' in inorder: 
-7.75 -4 0.75 -11.5 8.25 -0.5 7 4.5 3.25 
The elements of 'second' in preorder: 
-0.5 0.75 -4 -7.75 8.25 -11.5 3.25 4.5 7 
The elements of 'second' in postorder: 
-7.75 -4 -11.5 8.25 0.75 7 4.5 3.25 -0.5 
third: tree is not empty 
     no of nodes = 7 
     height of tree = 3 
The elements of 'third' in inorder: 
string a is This objects. of list 
The elements of 'third' in preorder: 
This is a string list of objects. 
The elements of 'third' in postorder: 
string a is objects. of list This 

代碼：

template <class T> 
void binTree<T>::insert(binTreeNode <T>*& node, const T& data) { 
     if(node == NULL) { 
       root = new binTreeNode<T>(data, NULL, NULL); 
       return; 
     } 

     binTreeNode<T>* ptr1 = node; 
     binTreeNode<T>* ptr2 = node; 
     bool placeRight = 0; 
     while(ptr1 != NULL) { 
       ptr2 = ptr1; 
       if(height(ptr1->left) > height(ptr1->right)) { 
         placeRight = true; 
         ptr1 = ptr1->right; 
       } else if (height(ptr1->right) > height(ptr1->left)) { 
         placeRight = false; 
         ptr1 = ptr1->left; 
       } else { 
         placeRight = false; 
         ptr1 = ptr1->left; 
       } 
     } 

     if(placeRight) { 
       ptr2->right = new binTreeNode<T>(data, NULL, NULL); 
     } else { 
       ptr2->left = new binTreeNode<T>(data, NULL, NULL); 
     } 
} 

驅動程序：

const vector<int> A { 1, -2, 3, -4, 5, -6, 7, -8, 9, -10, 11, -12, 13, -14, 15 }; 
const vector<float> B { 0.5, 1.75, -3, 4.25, 5.50, -6.75, 8, 9.25, -10.5 }; 
const vector<string> C { "This", "is", "a", "list", "of", "string", "objects." }; 
int main() { 
     binTree<int> intTree = binTree<int>(); 
     binTree<float> floatTree = binTree<float>(); 
     binTree<string> strTree = binTree<string>(); 

     for (std::vector<int>::const_iterator it = A.begin() ; it != A.end(); ++it) { 
       intTree.insert(*it); 
     } 
     intTree.preorder(increase); 
     cout << "first: "; 
     header(intTree); 

     inorder(intTree, "first"); 
     preorder(intTree, "first"); 
     postOrder(intTree, "first"); 
} 

個

函數來顯示結果：（應該是正確的）

template <class T> 
void binTree<T>::inorder(binTreeNode <T>* node, void (*f)(T&)) 
{ 
     if (node == NULL) { 
       return; 
     } 
     inorder(node->left,f); 
     f(node->data); 
     inorder(node->right,f); 
} 


template <class T> 
void binTree<T>::preorder(binTreeNode <T>* node, void(*f)(T&)) 
{ 
     if (node == NULL) { 
       return; 
     } 
     f(node->data); 
     preorder(node->left, f); 
     preorder(node->right, f); 
} 


template <class T> 
void binTree<T>::postorder(binTreeNode <T>* node, void(*f)(T&)) 
{ 
     if (node == NULL) { 
       return; 
     } 
     postorder(node->left, f); 
     postorder(node->right, f); 
     f(node->data); 
} 

template <class T> 
    int binTree<T>::height(binTreeNode <T>* node) const { 
    if (node == NULL || ((node->left == NULL) && (node->right == NULL))) { 
      return 0; 
    } 

    int leftSide = height(node->left); 
    int rightSide = height(node->right); 

    if (leftSide > rightSide) { 
      return leftSide + 1; 
    } else { 
      return rightSide + 1; 
    } 
} 

Answer 1

你的錯誤是在你的身高方法。如果你有一個不爲null但沒有子節點的節點，你將返回零。

if (node == NULL || ((node->left == NULL) && (node->right == NULL))) { 
    return 0; 
} 

到：您應該可以返回1.

改變這種狀況在你的身高方法

if (node == NULL) { 
    return 0; 
} 

Answer 2

它出現在載體的標誌A是倒退。您有1,-2,3,-4,...但正確的解決方案有-1,2,-3,4,...。同樣的，你B是

const vector<float> B { 0.5, 1.75, -3, 4.25, 5.50, -6.75, 8, 9.25, -10.5 }; 

這跟你說，我們期待的元素比較：

7, 3.25, 0.75, -7.75, -0.5, -11.5, 4.5, -4, 8.25 

這些不看甚至接近相同。

某處存在轉錄錯誤？

Answer 3

什麼是你的身高（）功能？

我想你誤解了BST的定義：

A. the value of the left child is smaller than the value of root node. 

B. the value of the right child is bigger than the value of root node. 

C. his left child tree and right child tree are also a BST. 

但是通過您的代碼在這裏：

while(ptr1 != NULL) { 
      ptr2 = ptr1; 
      if(height(ptr1->left) > height(ptr1->right)) { 
        placeRight = true; 
        ptr1 = ptr1->right; 
      } else if (height(ptr1->right) > height(ptr1->left)) { 
        placeRight = false; 
        ptr1 = ptr1->left; 
      } else { 
        placeRight = false; 
        ptr1 = ptr1->left; 
      } 
    } 

你只是比較你的節點的高度，而不是比較的真正價值節點。