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; 
      } 
    } 

你只是比较你的节点的高度，而不是比较的真正价值节点。