时间戳

首页 > 解决方案 > 二叉搜索树未将插入值加载到树中

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

问题描述

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

主文件

#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

标签： c++algorithmbinary-treebinary-search-tree

解决方案

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

将你的代码缩减到最基本的部分，我们得到

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”的成员变量。
一个 inbSearchTreeType 隐藏一个 in binaryTreeType- 它不是对同一变量的重新声明或“覆盖”。

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

顺便说一句，使用调试器也很难发现这个问题，在调试器中，您只会盯着一个变量，其值会像变魔术一样发生变化。

你需要做两件事：

  1. 删除root成员bSearchTreeType
  2. 因为这些是模板，所以您还需要在成员函数中更改root为。（找出为什么离开作为一个练习——这是一篇自己的文章。）this->rootbSearchTreeType

（顺便说一句，它似乎只适用于这些更改。做得好。）

推荐阅读