对于类,我必须创建一个二叉树,我似乎无法让插入方法正常工作。
预期成绩:
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;
}
}