Search(T, key)
{
if (T为空 || 找到)
{
return T;
}
if (key < T - key)
{
return Search(左子树查找);
}
else
{
return Search(右子树查找);
}
void InsertBST(T, key) {
if (T为空){
新生成一个结点;
}
else if (T == key)
{
return 0;
}
else if (T > key)
InsertBST(T->lchild, key);
else
InsertBST(T->rchild, key);
}
void CreateBST(BSTree& T)
{
int n;
输入插入个数
int a[100];
for (int i = 0; i < n; i++)
{
cin >> a[i];//输入插入数据
InsertBST(T, a[i]);
}
}
typedef struct BSTNode
{
int data;
struct BSTNode* lchild, * rchild;
}* BSTree;
int main()
{
BSTree T = NULL;
int key;
CreateBST(T);
cout << "中序遍历的结果为:" << endl;
InOrder(T);
cout << endl;
return 0;
}
void InsertBST(BSTree& T, int key)
{
if (T==NULL)
{
T = new BSTNode;
T->data = key;
T->lchild = T->rchild = NULL;
}
else if (T->data == key)
{
return;
}
else if (T->data > key)
{
InsertBST(T->lchild, key);
}
else
{
InsertBST(T->rchild, key);
}
}
void InsertBST(BSTree& T, int key)
{
if (T==NULL)
{
T = new BSTNode;
T->data = key;
T->lchild = T->rchild = NULL;
}
else if (T->data == key)
{
return;
}
else if (T->data > key)
{
InsertBST(T->lchild, key);
}
else
{
InsertBST(T->rchild, key);
}
}
void InOrder(BSTree T)
{
if (T)
{
InOrder(T->lchild);
cout << T->data << " ";
InOrder(T->rchild);
}
}
直接删除该节点
用其左子树或者右子树代替它,用其父结点指向其子节点
用其前驱或后驱节点替代,并将其前驱节点或后驱节点删掉
Delete(T,key)
{
if (树空)
{
return 删除失败;
}
else if (找到)
{
Delete(T);
return 1;
}
else if (key < T->data)
{
return Delete(T->lchild, key);
}
else
{
return Delete(T->rchild, key);
}
}
#include<iostream>
using namespace std;
typedef struct BSTNode
{
int data;
struct BSTNode* lchild, * rchild;
}* BSTree;
void InsertBST(BSTree& T, int key)
{
if (T==NULL)
{
T = new BSTNode;
T->data = key;
T->lchild = T->rchild = NULL;
}
else if (T->data == key)
{
return;
}
else if (T->data > key)
{
InsertBST(T->lchild, key);
}
else
{
InsertBST(T->rchild, key);
}
}
void CreateBST(BSTree& T)
{
int n;
cout << "请输入要插入的节点数: ";
cin >> n;
int a[100];
cout << "请输入" << endl;
for (int i = 0; i < n; i++)
{
cin >> a[i];
InsertBST(T, a[i]);
}
}
void InOrder(BSTree T)
{
if (T)
{
InOrder(T->lchild);
cout << T->data << " ";
InOrder(T->rchild);
}
}
int main()
{
BSTree T = NULL;
int key;
CreateBST(T);
cout << "中序遍历的结果为:" << endl;
InOrder(T);
cout << endl;
return 0;
}
原文:https://www.cnblogs.com/254916-cn/p/12731063.html