c++二叉排序树根结点的问题，请大神来回答一下

问题描述：

列如我用构造函数构造了一个BST，那么我怎么查找某一个元素的，因为要输入根结点的指针，但是我不知道根结点的指针
template
struct BSTNode
{
T m_nValue;
BSTNode m_pLeft;
BSTNode *m_pRight;
};
template
class BST
{
public:
BST(T r[],int n);
void InsertBST(BSTNode *&R, BSTNode *s);//插入数据在BST,R根结点，插入结点s
BSTNode *Search(BSTNode *r, T key);
bool DeleteBST(BSTNode&R, T key);//删除key
void Delete(BSTNode*&R);

BSTNode <T> *root;

};
template
void BST::InsertBST(BSTNode *&R, BSTNode *s)
{
if (R == nullptr)
R == s;//R为空，将s直接插入
else if (s->m_nValue < R->m_nValue)
InsertBST(R->m_pLeft, s);//递归向左子树中插入
else
InsertBST(R->m_pRight, s);

}
//构造BST的过程即是一个反复插入的过程
template
BST::BST(T r[], int n)
{
root = nullptr;
for (size_t i = 0; i < n; i++)
{
BSTNodes = new BSTNode;
s->m_nValue = r[i];
s->m_pLeft= nullptr;
s->m_pRight = nullptr;
InsertBST(root, s);//插入
}
}
template
BSTNode BST::Search(BSTNoder, T key)
{
if (r == nullptr)
return nullptr;
if (key == r->m_nValue)
return r;
else if (r->m_nValue < key)
return Search(r->m_pLeft, key);
else
return Search(r->m_pRight, key);
}
template
bool BST::DeleteBST(BSTNode&R, T key)
{
if (R == nullptr)
return false;
else if (R->m_nValue == key)
{
Delete(R);
return true;
}
else if (key < R->m_nValue)
return DeleteBST(R->m_pLeft, key);//查找key值
else
return DeleteBST(R->m_pRight, key);
}
//删除情况分为三种情况
//仔细理解
template
void BST::Delete(BSTNode*&R)
{
BSTNode*q, *s;
if (R->m_pLeft==nullptr)//如果其左子树为空
{
q = R;
R = R->m_pRight;//R的右子数赋给R
delete q;//删除q,即以前的R
}
if (R->m_pRight==nullptr)
{
q = R;
R = R->m_pLeft;
delete q;
}
else//左右子数都在
{
q = R; s = R->m_pLeft;
//寻找最大值进行与根结点的替换
while (s->m_pRight!=nullptr)
{
q = s;
s = s->m_pRight;
}
R->m_nValue = s->m_nValue;//将此最大值赋给要删除的节点
if (q != R)//即进行了while循环，改变q
q->m_pRight = s->m_pLeft;//s是q的右孩子，s是没有右子数的
else
R->m_pLeft = s->m_pLeft;
delete s;
}
}

答

可以定义个接口，调用接口返回根指针。或者从查找函数地方下手。说的不对，自动忽略。

答

来大神啊。。。。。。。。。。。、

答

BSTNode *root; this is the root of BST

答

例如这样的测试，其实这个root不存在的，即使我在类中，将其public
int main()
{
int a[] = { 10,6,14,4,8,12,16 };
BSTbst(a, 7);
BSTNode*pNode;
pNode=bst.Search(bst.root,10);
system("pause");
return 0;
}

答

下面是完整的测试方案

 #include "stdafx.h"
#include "binarySortTree.h"
#include <iostream>
using namespace std;
BSTNode<int>*CreateBinaryTreeNode(int value)
{
    BSTNode<int>* pNode = new BSTNode<int>();
    pNode->m_nValue = value;
    pNode->m_pLeft = NULL;
    pNode->m_pRight = NULL;

    return pNode;
}

void ConnectTreeNodes(BSTNode<int>* pParent, BSTNode<int>* pLeft, BSTNode<int>* pRight)
{
    if (pParent != NULL)
    {
        pParent->m_pLeft = pLeft;
        pParent->m_pRight = pRight;
    }
}

void PrintTreeNode(BSTNode<int>* pNode)
{
    if (pNode != NULL)
    {
        printf("value of this node is: %d\n", pNode->m_nValue);

        if (pNode->m_pLeft != NULL)
            printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue);
        else
            printf("left child is null.\n");

        if (pNode->m_pRight != NULL)
            printf("value of its right child is: %d.\n", pNode->m_pRight->m_nValue);
        else
            printf("right child is null.\n");
    }
    else
    {
        printf("this node is null.\n");
    }

    printf("\n");
}

void PrintTree(BSTNode<int>* pRoot)
{
    PrintTreeNode(pRoot);

    if (pRoot != NULL)
    {
        if (pRoot->m_pLeft != NULL)
            PrintTree(pRoot->m_pLeft);

        if (pRoot->m_pRight != NULL)
            PrintTree(pRoot->m_pRight);
    }
}

int main()
{
    int a[] = { 10,6,14,4,8,12,16 };
    BST<int>bst(a, 7);
    BSTNode<int>*pNode;
    pNode=bst.Search(bst.root,10);
    PrintTree(bst.root);
    system("pause");
    return 0;
}

答

完整二叉排序树代码

 template <typename T>
struct BSTNode
{
    T m_nValue;
    BSTNode *m_pLeft;
    BSTNode *m_pRight;
};
template <typename T>
class BST
{
public:
    BST(T r[],int n);
    void InsertBST(BSTNode<T> *&R, BSTNode<T> *s);//插入数据在BST,R根结点，插入结点s
    BSTNode<T> *Search(BSTNode<T> *r, T key);
    bool DeleteBST(BSTNode<T>*&R, T key);//删除key
    void Delete(BSTNode<T>*&R);


    BSTNode <T> *root;

};
template <typename T>
void BST<T>::InsertBST(BSTNode<T> *&R, BSTNode<T> *s)
{
    if (R == nullptr)
        R == s;//R为空，将s直接插入
    else if (s->m_nValue < R->m_nValue)
        InsertBST(R->m_pLeft, s);//递归向左子树中插入
    else
        InsertBST(R->m_pRight, s);

}
//构造BST的过程即是一个反复插入的过程
template <typename T>
BST<T>::BST(T r[], int n)
{
    root = nullptr;
    for (size_t i = 0; i < n; i++)
    {
        BSTNode<T> *s = new BSTNode<T>;
        s->m_nValue = r[i];
        s->m_pLeft= nullptr;
        s->m_pRight = nullptr;
        InsertBST(root, s);//插入
    }
}
template <typename T>
BSTNode<T>* BST<T>::Search(BSTNode<T> *r, T key)
{
    if (r == nullptr)
        return nullptr;
    if (key == r->m_nValue)
        return r;
    else if (r->m_nValue < key)
        return Search(r->m_pLeft, key);
    else
        return Search(r->m_pRight, key);
}
template <typename T>
bool BST<T>::DeleteBST(BSTNode<T>*&R, T key)
{
    if (R == nullptr)
        return false;
    else if (R->m_nValue == key)
    {
        Delete(R);
        return true;
    }
    else if (key < R->m_nValue)
        return DeleteBST(R->m_pLeft, key);//查找key值
    else
        return DeleteBST(R->m_pRight, key);
}
//删除情况分为三种情况
//仔细理解
template <typename T>
void BST<T>::Delete(BSTNode<T>*&R)
{
    BSTNode<T>*q, *s;
    if (R->m_pLeft==nullptr)//如果其左子树为空
    {
        q = R;
        R = R->m_pRight;//R的右子数赋给R
        delete q;//删除q,即以前的R
    }
    if (R->m_pRight==nullptr)
    {
        q = R;
        R = R->m_pLeft;
        delete q;
    }
    else//左右子数都在
    {
        q = R; s = R->m_pLeft;
        //寻找最大值进行与根结点的替换
        while (s->m_pRight!=nullptr)
        {
            q = s;
            s = s->m_pRight;
        }
        R->m_nValue = s->m_nValue;//将此最大值赋给要删除的节点
        if (q != R)//即进行了while循环，改变q
            q->m_pRight = s->m_pLeft;//s是q的右孩子，s是没有右子数的
        else
            R->m_pLeft = s->m_pLeft;
        delete s;
    }
}

c++二叉排序树根结点的问题，请大神来回答一下

相关推荐