点击查看代码
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* left;
Node* right;
};
Node* newNode(int x)
{
Node* temp = new Node;
temp->data = x;
temp->left = temp->right = nullptr;
return temp;
}
/*************************wrong code*********8***************************
void insert(Node** headref, int data)
{
Node* travptr = *headref;
//travptr是局部变量,副本,修改副本指针的指向不会改变原指针
while (travptr != NULL)
{
travptr = (data > travptr->data) ? travptr->right : travptr->left;
}
travptr = newNode(data);
//只能通过指向原指针的另一个指针取修改原指针
}
***************************************************************************/
void insert(Node** headref, int data)//可能跟头指针操作相关
{
if (*headref == NULL)
{
*headref = newNode(data);
return;
}//跟头指针操作相关
//直接修改原指针
Node* travptr = *headref;
Node* run= NULL;//初始化为空
while (travptr != NULL)//当travptr指向NULL时结束,条件更简单
{
run = travptr;
travptr = (data > travptr->data) ? travptr->right : travptr->left;
}//关键是 run,结束时 run指向待插入节点
if (data > run->data)
run->right = newNode(data);
else
run->left = newNode(data);//利用 run修改待插入节点左右link
//只能通过指向原指针的另一个指针取修改原指针
}//时间复杂度:O(logn)in best case(balanced bst)
bool search(Node* travptr, int data)//没有与头指针相关操作,可以用形参(副本)
{
while (travptr != NULL && travptr->data != data)//关注结束时
travptr = (data > travptr->data) ? travptr->right : travptr->left;
//结束情况:travptr指向NULL,或找到目标值
if (travptr == NULL)
{
return false;
}
return true;//判定具体情况
}//时间复杂度:O(logn)in best case(balanced bst)
int main()
{
Node* head = NULL;
insert(&head, 1);
insert(&head, 2);
insert(&head, 3);
insert(&head, 4);
cout << search(head, 3) << "\t" << search(head, 10);
return 0;
}