二叉搜索树未将插入值加载到树中

Question

我的问题是尝试获取函数 treeLeavesCount() 和 treeNodeCount() 到 return 树中叶子和节点的值，但是，我的问题是在通过 while 循环提供值之后使用 insert() 函数，树似乎保持为空，我通过在将值插入树之前和之后使用 isEmpty() 函数知道这一点。

main.cpp

#include <iostream>
#include "binaryTreeType.h"
#include "bSearchTreeType.h"

using namespace std;


int main()
{    
    int num;
    bSearchTreeType<int> *myTree= new bSearchTreeType<int>();

//test if tree is empty
    if(myTree->isEmpty())
        cout << "yes" << endl;
    else
        cout << "no" << endl;


     cout << "Line 10: Enter numbers ending with -999"<< endl;
     cin >> num;
     while (num != -999)
     {
         myTree->insert(num);
         cin >> num;
     }

    myTree->inorderTraversal();
    int p;
    p=myTree->treeNodeCount();
    cout << p << endl;

    p=myTree->treeLeavesCount();
    cout << p << endl;

    //test if tree is empty after data is inserted
    if(myTree->isEmpty())
        cout << "yes" << endl;
    else
        cout << "no" << endl;

    delete myTree;
    return 0;
}

binaryTreeType.h

#ifndef BINARYTREETYPE_H
#define BINARYTREETYPE_H
#include <queue>

template <class elemType>
struct binaryTreeNode
{
    elemType info;
    binaryTreeNode<elemType> *llink;
    binaryTreeNode<elemType> *rlink;
};


template <class elemType>
class binaryTreeType
{
    public:
        const binaryTreeType<elemType>& operator=(const binaryTreeType<elemType>&);
        //Overload the assignment operator.
        bool isEmpty() const;
        //Returns true if the binary tree is empty;
        //otherwise, returns false.
        void inorderTraversal() const;
        //Function to do an inorder traversal of the binary tree.
        void preorderTraversal() const;
        //Function to do a preorder traversal of the binary tree.
        void postorderTraversal() const;
        //Function to do a postorder traversal of the binary tree.
        int treeHeight() const;
        //Returns the height of the binary tree.
        int treeNodeCount() const;
        //Returns the number of nodes in the binary tree.
        int treeLeavesCount() const;
        //Returns the number of leaves in the binary tree.
        void destroyTree();
        //Deallocates the memory space occupied by the binary tree.
        //Postcondition: root = NULL;
        binaryTreeType(const binaryTreeType<elemType>& otherTree);
        //copy constructor
        binaryTreeType();
        //default constructor
        ~binaryTreeType();
        //destructor

    protected:
        binaryTreeNode<elemType> *root;
    private:
        void copyTree(binaryTreeNode<elemType>* &copiedTreeRoot,binaryTreeNode<elemType>* otherTreeRoot);
        //Makes a copy of the binary tree to which
        //otherTreeRoot points. The pointer copiedTreeRoot
        //points to the root of the copied binary tree.
        void destroy(binaryTreeNode<elemType>* &p);
        //Function to destroy the binary tree to which p points.
        //Postcondition: p = NULL
        void inorder(binaryTreeNode<elemType> *p) const;
        //Function to do an inorder traversal of the binary
        //tree to which p points.
        void preorder(binaryTreeNode<elemType> *p) const;
        //Function to do a preorder traversal of the binary
        //tree to which p points.
        void postorder(binaryTreeNode<elemType> *p) const;
        //Function to do a postorder traversal of the binary
        //tree to which p points.
        int height(binaryTreeNode<elemType> *p) const;
        //Function to return the height of the binary tree
        //to which p points.
        int max(int x, int y) const;
        //Returns the larger of x and y.
        int nodeCount(binaryTreeNode<elemType> *p) const;
        //Function to return the number of nodes in the binary
        //tree to which p points
        int leavesCount(binaryTreeNode<elemType> *p) const;
        //Function to return the number of leaves in the binary
        //tree to which p points
};

template <class elemType>
bool binaryTreeType<elemType>::isEmpty() const
{
    return (root == NULL);
};

template <class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
    root = NULL;
}

template <class elemType>
void binaryTreeType<elemType>::inorderTraversal() const
{
    inorder(root);
}

template <class elemType>
void binaryTreeType<elemType>::preorderTraversal() const
{
    preorder(root);
}

template <class elemType>
void binaryTreeType<elemType>::postorderTraversal() const
{
    postorder(root);
}

template <class elemType>
int binaryTreeType<elemType>::treeHeight() const
{
    return height(root);
}

template <class elemType>
int binaryTreeType<elemType>::treeNodeCount() const
{
    return nodeCount(root);
}

template <class elemType>
int binaryTreeType<elemType>::treeLeavesCount() const
{
    return leavesCount(root);
}

template <class elemType>
void binaryTreeType<elemType>::inorder(binaryTreeNode<elemType> *p) const
{
    if (p != NULL)
    {
        inorder(p->llink);
        std::cout << p->info << " ";
        inorder(p->rlink);
    }

}

template <class elemType>
void binaryTreeType<elemType>::preorder(binaryTreeNode<elemType> *p) const
{
    if (p != NULL)
    {
        std::cout << p->info << " ";
        preorder(p->llink);
        preorder(p->rlink);
    }
}

template <class elemType>
void binaryTreeType<elemType>::postorder(binaryTreeNode<elemType> *p) const
{
    if (p != NULL)
    {
        postorder(p->llink);
        postorder(p->rlink);
        std::cout << p->info << " ";
    }
}

template <class elemType>
int binaryTreeType<elemType>::height(binaryTreeNode<elemType> *p) const
{
    if (p == NULL)
        return 0;
    else
        return 1 + max(height(p->llink), height(p->rlink));
}

template <class elemType>
int binaryTreeType<elemType>::max(int x, int y) const
{
    if (x >= y)
        return x;
    else
        return y;
}

template <class elemType>
void binaryTreeType<elemType>::copyTree(binaryTreeNode<elemType>* &copiedTreeRoot,binaryTreeNode<elemType>* otherTreeRoot)
{
    if (otherTreeRoot == NULL)
        copiedTreeRoot = NULL;
    else
    {
        copiedTreeRoot = new binaryTreeNode<elemType>;
        copiedTreeRoot->info = otherTreeRoot->info;
        copyTree(copiedTreeRoot->llink, otherTreeRoot->llink);
        copyTree(copiedTreeRoot->rlink, otherTreeRoot->rlink);
    }
} //end copyTree


template <class elemType>
void binaryTreeType<elemType>::destroy(binaryTreeNode<elemType>* &p)
{
    if (p != NULL)
    {
        destroy(p->llink);
        destroy(p->rlink);
        delete p;
        p = NULL;
    }
}

template <class elemType>
void binaryTreeType<elemType>::destroyTree()
{
    destroy(root);
}

template <class elemType>
binaryTreeType<elemType>::binaryTreeType(const binaryTreeType<elemType>& otherTree)
{
    if (otherTree.root == NULL) //otherTree is empty
        root = NULL;
    else
        copyTree(root, otherTree.root);
}

template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
    destroy(root);
}

template <class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::operator=(const binaryTreeType<elemType>& otherTree)
{
    if (this != &otherTree) //avoid self-copy
    {
        if (root != NULL) //if the binary tree is not empty,
            //destroy the binary tree
            destroy(root);
        if (otherTree.root == NULL) //otherTree is empty
            root = NULL;
        else
            copyTree(root, otherTree.root);
    }//end else
    return *this;
}
template <class elemType>
int binaryTreeType<elemType>::leavesCount(binaryTreeNode<elemType> *p) const
{
  if(p == NULL)
    return 0;
  if(p->llink == NULL && p->rlink==NULL)
    return 1;
  else
    return leavesCount(p->llink) + leavesCount(p->rlink);
}
template <class elemType>
int binaryTreeType<elemType> ::nodeCount(binaryTreeNode<elemType> *p) const
{
    int count = 1;
      if ( p == NULL ){
        return 0;
      }else{
        count += nodeCount(p->llink);
        count += nodeCount(p->rlink);
      }
  return count;
}

#endif // BINARYTREETYPE_H

bSearchTreeType.h

#ifndef BSEARCHTREETYPE_H
#define BSEARCHTREETYPE_H
#include "binaryTreeType.h"
#include <iostream>
#include <cassert>

template <class elemType>
class bSearchTreeType : public binaryTreeType<elemType>
{


public:

    bool search(const elemType& searchItem) const;
    //Function to determine if searchItem is in the binary
    //search tree.
    //Postcondition: Returns true if searchItem is found in the
    // binary search tree; otherwise, returns false.

    void insert(const elemType& insertItem);
    //Function to insert insertItem in the binary search tree.
    //Postcondition: If no node in the binary search tree has the
    // same info as insertItem, a node with the info insertItem
    // is created and inserted in the binary search tree.

    void deleteNode(const elemType& deleteItem);
    //Function to delete deleteItem from the binary search tree.
    //Postcondition: If a node with the same info as deleteItem
    // is found, it is deleted from the binary search tree.

protected:
    binaryTreeNode<elemType> *root;

private:
    void deleteFromTree(binaryTreeNode<elemType>* &p);
    //Function to delete the node to which p points is deleted
    //from the binary search tree.
    //Postcondition: The node to which p points is deleted from
    // the binary search tree.
};



using namespace std;


template <class elemType>
bool bSearchTreeType<elemType>::search(const elemType& searchItem) const
{
    binaryTreeNode<elemType> *current;
    bool found = false;

    if (root == NULL)
        cerr << "Cannot search the empty tree." << endl;
    else
    {
        current = root;
        while (current != NULL && !found)
        {
            if (current->info == searchItem)
                found = true;
            else if (current->info > searchItem)
                current = current->llink;
            else
                current = current->rlink;
        }//end while
    }//end else
    return found;
}//end search


template <class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
    binaryTreeNode<elemType> *current; //pointer to traverse the tree
    binaryTreeNode<elemType> *trailCurrent; //pointer behind current
    binaryTreeNode<elemType> *newNode; //pointer to create the node

    newNode = new binaryTreeNode<elemType>;
    assert(newNode != NULL);
    newNode->info = insertItem;
    newNode->llink = NULL;
    newNode->rlink = NULL;

    if (root == NULL)
        root = newNode;

    else
    {
        current = root;
        while (current != NULL)
        {
            trailCurrent = current;
            if (current->info == insertItem)
            {
                std::cerr << "The insert item is already in the list-";
                std::cerr << "duplicates are not allowed." << insertItem << std::endl;
                return;
            }
            else if (current->info > insertItem)
                current = current->llink;
            else
                current = current->rlink;
        }//end while
        if (trailCurrent->info > insertItem)
            trailCurrent->llink = newNode;
        else
            trailCurrent->rlink = newNode;
    }
}//end insert


template <class elemType>
void bSearchTreeType<elemType>::deleteFromTree(binaryTreeNode<elemType>* &p)
{
    binaryTreeNode<elemType> *current;//pointer to traverse the tree
    binaryTreeNode<elemType> *trailCurrent; //pointer behind current
    binaryTreeNode<elemType> *temp; //pointer to delete the node

    if (p == NULL)
        cerr << "Error: The node to be deleted is NULL." << endl;
    else if(p->llink == NULL && p->rlink == NULL)
    {
        temp = p;
        p = NULL;
        delete temp;
    }
    else if(p->llink == NULL)
    {
        temp = p;
        p = temp->rlink;
        delete temp;
    }
    else if(p->rlink == NULL)
    {
        temp = p;
        p = temp->llink;
        delete temp;
    }
    else
    {
        current = p->llink;
        trailCurrent = NULL;
        while (current->rlink != NULL)
        {
            trailCurrent = current;
            current = current->rlink;
        }//end while
        p->info = current->info;
        if (trailCurrent == NULL) //current did not move;
        //current == p->llink; adjust p
            p->llink = current->llink;
        else
            trailCurrent->rlink = current->llink;
        delete current;
    }//end else
}//end deleteFromTree


template <class elemType>
void bSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
    binaryTreeNode<elemType> *current; //pointer to traverse the tree
    binaryTreeNode<elemType> *trailCurrent; //pointer behind current

    bool found = false;

    if (root == NULL)
        std::cout << "Cannot delete from the empty tree." << endl;
    else
    {
        current = root;
        trailCurrent = root;

        while (current != NULL && !found)
        {
            if (current->info == deleteItem)
                found = true;
            else
            {
                trailCurrent = current;
                if (current->info > deleteItem)
                    current = current->llink;
                else
                    current = current->rlink;
            }
        }//end while
        if (current == NULL)
            std::cout << "The delete item is not in the tree." << endl;
        else if (found)
        {
            if (current == root)
                deleteFromTree(root);
            else if (trailCurrent->info > deleteItem)
                deleteFromTree(trailCurrent->llink);
            else
                deleteFromTree(trailCurrent->rlink);
        }//end if
    }
}//end deleteNode



#endif // BSEARCHTREETYPE_H

Answer 1

（这是一个巨大的代码量。下次请删除您的测试用例不需要的所有内容。）

将您的代码精简到最基本的部分，我们得到

template <class elemType>
class binaryTreeType
{
    public:
        bool isEmpty() const;
    protected:
        binaryTreeNode<elemType> *root;
};

template <class elemType>
bool binaryTreeType<elemType>::isEmpty() const
{
    return (root == NULL);
};

template <class elemType>
class bSearchTreeType : public binaryTreeType<elemType>
{
    void insert(const elemType& insertItem);
protected:
    binaryTreeNode<elemType> *root;
};

template <class elemType>
void bSearchTreeType<elemType>::insert(const elemType& insertItem)
{
    // ...
    if (root == NULL)
        root = newNode;
    else
    {
        current = root;
        //...
    }
}//end insert

现在我们可以看到您声明了两个个名为 "root".
的成员变量 bSearchTreeType 中的那个隐藏了 binaryTreeType 中的那个 - 它不是同一变量的重新声明或 "override"。

这意味着你的binaryTreeType成员函数（如isEmpty）使用binaryTreeType中的root，而bSearchTreeType的成员函数（例如 insert) 在 bSearchTreeType 中使用 root，因此在 insert 更新了其中一个根后，另一个仍然为空。

顺便说一下，这个问题也很难用调试器发现，在调试器中你只会盯着一个变量，它的值会像变魔术一样变化。

你需要做两件事：

从 bSearchTreeType

root

因为这些是模板，你还需要在bSearchTreeType成员函数中将root改为this->root。（找出离开的原因作为练习 - 这是一篇独立的文章。）

（顺便说一下，它似乎只对这些更改有效。干得好。）

二叉搜索树未将插入值加载到树中

Binary search tree not loading insert values into tree

c++

algorithm

binary-tree

binary-search-tree