2

对于类,我必须创建一个二叉树,我似乎无法让插入方法正常工作。

预期成绩:

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

3 回答 3

1

您的错误在您的高度方法中。如果您有一个不为空但没有子节点的节点,则返回零。你应该返回 1。

在您的高度方法中更改此条件:

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

到:

if (node == NULL) {
    return 0;
}
于 2013-03-23T02:13:39.300 回答
0

看来您的向量的符号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

这些看起来甚至不完全相同。

某处转录错误?

于 2013-03-22T23:10:09.523 回答
0

你的 height() 函数是什么?

我认为您误解了 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;
            }
    }

您只需比较节点的高度,而不是比较节点的实际值。

于 2013-03-23T00:49:55.457 回答