二叉搜索树？ [英] Binary Search Tree?

问题描述

我想使用C ++做一个二叉搜索树。我只使用函数来插入数据和查找数据。
我似乎不能让程序工作，虽然我发现它是非常逻辑和正确的？

任何帮助将非常感激。 / p>

 ＃include< iostream> 
 using namespace std; 
 
 template< class T> 
 class BinarySearchTree 
 {
 private：
 struct tree 
 {
 tree * leftchild; 
 tree * rightchild; 
 T data; 
}; 
 tree * root; 
 public：
 BinarySearchTree（）
 {
 root = NULL; 
} 
 void insert（T）; 
 void searchForItem（T）; 
}; 
 
 template< class T> 
 void BinarySearchTree< T> :: insert（T newNum）
 {
 tree * newItem = new tree; 
 tree * parent; 
 
 newItem-> data = newNum; 
 newItem-> leftchild = NULL; 
 newItem-> rightchild = NULL; 
 
 if（root == NULL）
 root = newItem; 
 
 else 
 {
 tree * current; 
 current = root; 
 while（current）
 {
 parent = current; 
 
 if（newItem-> data> current-> data）
 current = current-> rightchild; 
 else 
 current = current-> leftchild; 
} 
 
 if（newItem-> data> parent-> data）
 parent-> rightchild = newItem; 
 else 
 parent-> leftchild = newItem; 
} 
 
} 
 
 template< class T> 
 void BinarySearchTree< T> :: searchForItem（T toFindNum）
 {
 tree * current; 
 tree * parent; 
 
 current = root; 
 if（current-> data == toFindNum）
 cout<< toFindNum<<是这个二叉搜索树的根。<< endl; 
 
 while（current-> data！= toFindNum）
 {
 parent = current; 
 
 if（current-> data> toFindNum）
 current = current-> rightchild; 
 else 
 current = current-> leftchild; 
} 
 
 cout << toFindNum<<是<<< parent-> data<< endl; 
} 
 int main（）
 {
 BinarySearchTree< int> b; 
 
 b.insert（5）; 
 b.insert（4）; 
 b.insert（3）; 
 b.insert（2）; 
 b.insert（7）; 
 
 b.searchForItem（4）; 
} 
  

解决方案

/ p>

  if（current-> data> toFindNum）
 current = current-> rightchild; 
  

考虑这个树。

  5 
 / \ 
 4 6 
  

你的 toFindNum 是4.如果 current-> data 是5，大于4，

 <$ c $ 
 c> if（current-> data> toFindNum）
 current = current-> leftchild; 
 else 
 current = current-> rightchild; 
  

I am trying to make a binary search tree using C++. I am using only the functions to insert data and find data. I can't seem to get the program to work, although I find that it is very logic and correct?

Any help would be greatly appreciated.

#include<iostream>
using namespace std;

template <class T>
class BinarySearchTree
{
private:
    struct tree
    {
        tree *leftchild;
        tree *rightchild;
        T data;
    };
    tree *root;
public:
    BinarySearchTree()
    {
        root=NULL; 
    }
    void insert(T);
    void searchForItem(T);
};

template<class T>
void BinarySearchTree<T>::insert(T newNum)
{
    tree *newItem = new tree; 
    tree *parent; 

    newItem->data = newNum;
    newItem->leftchild = NULL;
    newItem->rightchild = NULL;

    if(root==NULL) 
        root=newItem;

    else
    {
        tree *current;
        current=root;
        while(current) 
        {
            parent = current;

            if(newItem->data > current->data)
                current = current->rightchild;
            else
                current = current->leftchild;
        }

        if(newItem->data > parent->data)
            parent->rightchild = newItem;
        else
            parent->leftchild = newItem;
    }

}

template<class T>
void BinarySearchTree<T>::searchForItem(T toFindNum)
{
    tree *current;
    tree *parent;

    current = root;
    if(current->data == toFindNum)
        cout<<toFindNum<<" is the root of this binary search tree."<<endl;

    while(current->data != toFindNum)
    {
        parent = current;

        if(current->data > toFindNum)
            current = current->rightchild;
        else
            current = current->leftchild;
    }

    cout<<toFindNum<<" is the child of "<<parent->data<<endl;
}
int main()
{
    BinarySearchTree<int> b;

    b.insert(5);
    b.insert(4);
    b.insert(3);
    b.insert(2);
    b.insert(7);

    b.searchForItem(4);
} 

解决方案

One problem is here.

if(current->data > toFindNum)
    current = current->rightchild;

Consider this tree.

  5
 /  \
 4   6

Your toFindNum is 4. If current->data is 5, greater than 4, you need to look in the left child, not right one.

Your statement should be this.

if(current->data > toFindNum)
    current = current->leftchild;
else
current = current->rightchild;

这篇关于二叉搜索树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！