二叉搜索树
什么是二叉搜索树：二叉搜索树又称之为二叉排序树，它不为空树时，它左子树上所有的元素都小于根节点的元素，而根节点右子树上所有的元素都大于根节点的元素。
二叉搜索树的基本操作：
二叉树的查找：
思路 ：
非递归查找：
1.如果二叉树的根节点为空的话，直接返回0。
2.如果二叉树的该根节点不为空的话，循环下面的操作：
3 用要查找的元素与根节点的元素比较。如果要查找的元素大于根节点的元素的话，向根节点的右边查找.
4 如果要查找的元素小于根节点的元素时，向根节点的最左边查找。
5.如果要查找的元素等于根节点时，返回1。
如果循环结束时，代表此时没有找到该元素，直接返回0.
递归查找：
1.如果根节点为空的话，直接返回0；
2.如果根节点等于你要查找的元素时，返回1；
3.如果根节点大于你要查找的元素时，递归向根节点的左子树查找。
4.如果根节点小于你要查找的元素时，递归香根结点的右子树查找。
如果上面的操作全部执行完之后代表二叉搜索树中没有该元素。
//寻找数据为data的元素，找到返回1，找不到返回0
int Find(FindTree *q, DataType data)
{
FindTree *ret = q;
//当树为空时，立即返回0
if(q == NULL)
return 0;
while(q)
{
//如果找到的话，返回1；
if(data == q->data)
return 1;
//如果要查找的数据大于根节点的数据，则向右查找
else if(data > q->data)
{
q = q->right;
}
//如果要查找的数据小于根节点的数据，则向左查找
else if(data < q->data)
{
q = q->left;
}
}
//如果没有找到，返回0
return 0;
}
//递归查找
int RecursionFindTree(FindTree *q, DataType data)
{
//如果根节点为空的话，返回0
if(q == NULL)
return 0;
//如果根节点的数据等于要查找的数据时，返回1；
if(q->data == data)
return 1;
//如果根节点的数据大于要查找的数据时，向左子数查找
if(q->data > data)
return RecursionFindTree(q->left, data);
//如果根节点的数据小于要查找的数据时，向右子树查找
if(q->data < data)
return RecursionFindTree(q->right, data);
return 0;
}二叉树的插入：
思路：
二叉搜索树插入的非递归的方法：
1.如果树为空的话，直接插入该元素。
2.如果树不为空的话，执行下面的操作：
a.设置两个指针child和parent，child用来查找要插入元素的插入的位置。parent指向child的双亲节点。
b.用child在二叉搜索树中循环查找要插入元素的位置，然后让parent指向child的双亲。如果在child的查找过程中发现有元素与你要插入的元素相同的话，直接返回0.不用插入。
c.判断要插入的位置在parent的左边还是右边。然后插入此元素。
二叉搜索树的递归插入：
1.如果根节点为空时（代表此时二叉树可能是空树，也可能找到了要插入的位置），直接插入要插入的元素。
2.如果根节点的元素等于你要插入的元素的话，代表此元素已经存在，直接返回0；
3.如果根节点的元素大于你要插入的元素时，递归的向根节点的左子树查找。
4.如果根节点的元素小于你要插入的元素时，递归的向根节点的右子树查找。
//创建一个节点
FindTree *BuyNode(DataType data)
{
FindTree *ret = (FindTree *)malloc(sizeof(FindTree));
if(ret == NULL)
{
assert(0);
}
ret->data = data;
ret->left = NULL;
ret->right = NULL;
return ret;
}
//向二叉搜索树中插入元素data
int InsertTree(FindTree **q, DataType data)
{
FindTree* cur = *q;//用来寻找要插入的位置
FindTree* parent = NULL;//用来标记要插入位置的双亲节点
//如果是空树的话，直接插入
if(*q == NULL)
{
*q = BuyNode(data);
return 1;
}
//如果不是空数的话，寻找该元素应该插入的位置
while(cur != NULL)
{
//如果数据在二叉树中已经存在的话，直接返回，插入失败
if((cur)->data == data)
return 0;
//如果要查的数据比根节点的数据小的话，向做查找，并用parent记录双亲节点
else if(cur->data < data)
{
parent = cur;
cur = cur->right;
}
//如果要查的数据比根节点的数据大的话，向做查找，并用parent记录双亲节点
else
{
parent = cur;
cur = cur->left;
}
}
//此时表时插入的位置已经找到
//用data与parent的数据比较，如果大于parent中的数据的话，将要节点插入到parent节点的右边，
//如果小于的话，插入到parent节点的左边
if(data > parent->data)
parent->right = BuyNode(data);
else if(data < parent->data)
parent->left = BuyNode(data);
return 1;
}
//像二叉树中插入元素，递归写法
int RecursionInsertBSTree(FindTree **q, DataType data)
{
if(*q == NULL)
{
(*q) = BuyNode(data);
return 1;
}
if((*q)->data == data)
return 0;
else if((*q)->data > data)
return RecursionInsertBSTree(&(*q)->left, data);
else
return RecursionInsertBSTree(&(*q)->right, data);
}在二叉树中删除元素
思路：
非递归删除方法：
1.如果二叉搜索树不存在或者你要删除的元素不存在的话，直接返回0.
2.如果二叉树存在并且你要删除的元素存在的话，执行下面的操作：
a.如果要删除的节点只有右孩子
1.先判断要删除的节点有无双亲节点（当要删除的节点是根节点）
直接删除节点，然后将二叉搜索树置空。
2.如果要删除的节点有双亲节点的话。
如果要删除的节点在双亲节点的左边的话，将双亲节点的左子树指向要删除节点的右孩子。
如果要删除的节点在双亲节点的右边的话，将双亲节点的右子树指向要删除节点的右孩子。
b.如果要删除的节点只有左孩子
1.先判断要删除的节点有无双亲节点（当要删除的节点是根节点）
直接删除节点，然后将二叉搜索树置空。
2.如果要删除的节点有双亲节点的话。
如果要删除的节点在双亲节点的左边的话，将双亲节点的左子树指向要删除节点的左孩子。
如果要删除的节点在双亲节点的右边的话，将双亲节点的右子树指向要删除节点的左孩子。
c.如果要删除节点的左右孩子都存在的话
1.找到 要删除节点的右子树中最左边的节点。用child记录该节点，然后用parent记录child的双亲节点。
2.用child指向的节点元素替换要删除节点中的元素。
3.如果child在parent的左边的话，将parent的左指针域指向child的右孩子，否则的话parent的右指针域指向child的右孩子。
//删除二叉搜索树中的一个指定的节点
int DelFindTreeNode(FindTree **q, DataType data)
{
FindTree* cur = *q;//用来寻找要删除的位置
FindTree* parent = *q;//用来标记要插入位置的双亲节点
//如果树为空的话，直接返回
if(*q == NULL)
return 0;
//找你要删除的位置
while(cur)
{
//找到时退出
if((cur)->data == data)
break;
//如果要查的数据比根节点的数据小的话，向做查找，并用parent记录双亲节点
else if(cur->data < data)
{
parent = cur;
cur = cur->right;
}
//如果要查的数据比根节点的数据大的话，向做查找，并用parent记录双亲节点
else
{
parent = cur;
cur = cur->left;
}
}
//如果删除的节点只有左孩子
if(cur->left != NULL && cur->right == NULL)
{
//如果是根节点的话，直接删除
if(cur == *q)
{
free(cur);
cur = NULL;
*q = NULL;
}
//判断要删除的结点是双亲的左孩子时，将双亲的做指针域指向删除节点的左孩子
else if(cur == parent->left)
{
parent->left = cur->left;
free(cur);
cur = NULL;
}
//判断要删除的结点是双亲的右孩子时，将双亲的做指针域指向删除节点的左孩子
else if(cur == parent->right)
{
parent->right = cur->left;
free(cur);
cur = NULL;
}
}
//如果要删除的节点只有右孩子
else if(cur->right != NULL && cur->left == NULL)
{
//如果是根节点的话，直接删除
if(cur == *q)
{
free(cur);
cur = NULL;
*q = NULL;
}
//判断要删除的结点是双亲的左孩子时，将双亲的做指针域指向删除节点的右孩子
else if(cur == parent->left)
{
parent->left = cur->right;
free(cur);
cur = NULL;
}
//判断要删除的结点是双亲的右孩子时，将双亲的做指针域指向删除节点的右孩子
else if(cur == parent->right)
{
parent->right = cur->right;
free(cur);
cur = NULL;
}
}
//当删除节点的左右孩子都存在时
else
{
//找根节点右子树中最左边的节点（也就是替代节点）
FindTree *tmp = cur->right;
parent = tmp;
while(tmp->left)
{
parent = tmp;
tmp = tmp->left;
}
//如果替代节点在双亲节点的右边
//双亲节点指向替代节点的右边
if(parent->right == tmp)
parent->right = tmp->right;
//如果替代节点在双亲的左边
//将此节点的双亲节点的左指针域指向此节点的右子树
else
parent->left = tmp->right;
//然后将替代节点中的数据替换要删除中的数据
cur->data = tmp->data;
//释放替代节点
free(tmp);
tmp = NULL;
}
return 1;
}二叉搜索树的递归删除：
1.如果根节点为空的话，直接返回0.
2.如果根节点不为空的话，执行下面的操作：
a.如果你要删除的元素大于根节点的话，递归遍历根节点的右子树。
b.如果你要删除的元素小于根节点的话，递归遍历根节点的左子树
c.如果你要删除的元素等于根节点的话，执行下面的操作：
1.如果根节点只有左孩子的话，让根节点等于它的左孩子。
2.如果根节点只有右孩子的话，让根节点等于它的右孩子。
3.如果根节点的左右孩子都存在的话，找到根节点右子树中最左边的节点，然后用该节点中的元素替换根节点中的元素。最后删除替换节点。
//递归实现删除
int DelTreeNodeRecursion(FindTree **q, DataType data)
{
FindTree* cur = *q;//用来寻找要删除的位置
//如果树为空的话，直接返回
if(*q == NULL)
return 0;
//如果要删除的值小于根节点的值，那么向根节点的左边查找
if((*q)->data > data)
{
return DelTreeNodeRecursion(&(*q)->left, data);
}
//如果要删除的值大于根节点的值，那么向根结点的右边查找
else if((*q)->data < data)
{
return DelTreeNodeRecursion(&(*q)->right, data);
}
//当要删除的值等于根节点时
else
{
cur = *q;
//要删除的节点只有右孩子，那么根节点就等于它的右孩子
if((*q)->left == NULL)
{
(*q) = cur->right;
free(cur);
cur = NULL;
return 1;
}
//要删除的节点只有左孩子，那么根节点就等于它的右孩子
else if(cur->right == NULL)
{
(*q) = cur->left;
free(cur);
cur = NULL;
return 1;
}
//当要删除的节点的左右孩子都存在时，找到删除节点的右子树的最左边的节点（替代节点）
//并且将替代节点的 值赋给要删除的节点，然后再递归删除替代节点
else
{
cur = (*q)->right;
while((cur)->left)
{
cur = cur->left;
}
(*q)->data = cur->data;
return DelTreeNodeRecursion(&(*q)->right ,cur->data);
}
}
}其他的函数
//销毁二叉搜索树
void DestroyTree(FindTree **q)
{
FindTree *tmp = NULL;
//如果树为空的话，不需要销毁
if(*q == NULL)
return;
//当树不为空时使用后续遍历来销毁
else
{
DestroyTree(&(*q)->left);
DestroyTree(&(*q)->right);
tmp = *q;
free(tmp);
tmp = NULL;
}
}
//打印搜索二叉树
void PrintBTree(FindTree *cur)
{
if(cur == NULL)
return ;
else
{
PrintBTree(cur->left);
printf("%d", cur->data);
PrintBTree(cur->right);
}
}FindBTree.h
#ifndef _FINDBTREE_H_
#define _FINDBTREE_H_
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
typedef struct FindTree
{
DataType data;
struct FindTree *left;
struct FindTree *right;
}FindTree;
int RecursionFindTree(FindTree *q, DataType data);
int Find(FindTree *q, DataType data);
FindTree *BuyNode(DataType data);
int InsertTree(FindTree **q, DataType data);
int RecursionInsertBSTree(FindTree **q, DataType data);
void DestroyTree(FindTree **q);
int DelFindTreeNode(FindTree **q, DataType data);
int DelTreeNodeRecursion(FindTree **q, DataType data);
void PrintBTree(FindTree *cur);
#endif //_FINDBTREE_H_Main.c
#include"FindBTree.h"
void FindBTreeText()
{
int i = 0;
FindTree *q = NULL;
InsertTree(&q, 4);
InsertTree(&q, 1);
InsertTree(&q, 6);
InsertTree(&q, 9);
InsertTree(&q, 3);
InsertTree(&q, 5);
InsertTree(&q, 0);
InsertTree(&q, 7);
InsertTree(&q, 10);
RecursionInsertBSTree(&q, 11);
printf("二叉搜索树的非递归删除为:");
DelFindTreeNode(&q, 6);
PrintBTree(q);
printf("\n二叉搜索树的递归删除为:");
DelTreeNodeRecursion(&q, 7);
i = RecursionFindTree(q, 5);
PrintBTree(q);
DestroyTree(&q);
}
int main()
{
FindBTreeText();
return 0;
}二叉搜索树的应用
1.判断一个单词是否拼写正确
思路：用二叉搜索树的插入方式向二叉搜索树中插入一些字符串，然后再用二叉搜索树的查找方式查找该元素是否存在，如果该元素存在的话，代表；拼写的字符串是正确的，否则不正确。
Spell.h
#define _CRT_SECURE_NO_WARNINGS 1
#ifndef _SPELL_
#define _SPELL_
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef char* DataType;
typedef struct Word
{
DataType data;
struct Word *left;
struct Word *right;
}Word;
Word *BuyNode(DataType data);
int InsertWord(Word **Spell, DataType data);
int FindNode(Word *Spell, DataType data);
void DesTroyNode(Word **Spell);
#endif _SPELL_Spell.c
#include"Spell.h"
//创建一个节点
Word *BuyNode(DataType data)
{
Word *ret = (Word*)malloc(sizeof(Word));
if(ret == NULL)
{
assert(0);
}
ret->data = data;
ret->left = NULL;
ret->right = NULL;
return ret;
}
//向二叉搜索树中插入新的数据
int InsertWord(Word **Spell, DataType data)
{
Word *ret = *Spell;
Word *parent = *Spell;
//如果是空树的时候
if(*Spell == NULL)
{
*Spell = BuyNode(data);
}
//如果不是空数的话
else
{
//找出要插入的位置
while(ret)
{
if(strcmp(ret->data, data) == 0)
return 0;
else if(strcmp(ret->data, data) > 0)
{
parent = ret;
ret = ret->left;
}
else
{
parent = ret;
ret = ret->right;
}
}
//开始插入元素
if(strcmp(parent->data, data) > 0)
{
parent->left = BuyNode(data);
}
else
{
parent->right = BuyNode(data);
}
}
return 1;
}
//查找数据
int FindNode(Word *Spell, DataType data)
{
Word *ret = Spell;
assert(Spell);
//开始比较数据
while(ret)
{
if(strcmp(ret->data, data) == 0)
{
return 1;
}
else if(strcmp(ret->data, data) > 0)
{
ret = ret->left;
}
else
{
ret = ret->right;
}
}
return 0;
}
//销毁树
void DesTroyNode(Word **Spell)
{
Word *ret = *Spell;
if(NULL == *Spell)
return;
DesTroyNode(&ret->left);
DesTroyNode(&ret->right);
free(ret);
ret = NULL;
}2.实现一个简单的字典
和上面检查拼写单词是否正确 的方式一样，不同之处在结构体中不再是只可以存储一个字符串，而是可以存储两个字符串，一个字符串用来存放英语单词，另一个字符串用来存放该单词的汉语意思。
Dictionary.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef char* DataType;
typedef struct Dictionary
{
DataType En;
DataType Ch;
struct Dictionary *left;
struct Dictionary *right;
}Dictionary;
DataType FindTreeNode(Dictionary *Dic, DataType data);
void InsertTree(Dictionary **Dic, DataType en, DataType ch);
void DesTroyDic(Dictionary **q);
#endif //_DICTIONARY_Dictionary.c
#include"Dictionary.h"
Dictionary *BuyNewNode(DataType en, DataType ch)
{
Dictionary *ret = (Dictionary*)malloc(sizeof(Dictionary));
if(ret == NULL)
{
assert(0);
}
ret->Ch = ch;
ret->En = en;
ret->left = NULL;
ret->right = NULL;
return ret;
}
void InsertTree(Dictionary **Dic, DataType en, DataType ch)
{
Dictionary *ret = *Dic;
Dictionary *parent = *Dic;
//当树为空树时,直接插入元素
if(*Dic == NULL)
{
*Dic = BuyNewNode(en, ch);
}
//当树不为空的时候，查找它插入的位置
else
{
while(ret)
{
//如果数据已经存在的话，直接退出
if(strcmp(ret->En ,en) == 0)
{
return ;
}
else if(strcmp(ret->En ,en) > 0)
{
parent = ret;
ret = ret->left;
}
else
{
parent = ret;
ret = ret->right;
}
}
//如果根节点的数据大于，你要插入的数据时，将新的数据插入到左边
if(strcmp(parent->En, en) > 0)
{
parent->left = BuyNewNode(en, ch);
}
//如果根节点小的话，将新数据放在根节点的右边
else
{
parent->right = BuyNewNode(en, ch);
}
}
}
//查字典
DataType FindTreeNode(Dictionary *Dic, DataType data)
{
Dictionary *ret = 0;
assert(Dic);
ret = Dic;
//英译中
while(ret)
{
if(strcmp(ret->En, data) == 0)
return ret->Ch;
else if(strcmp(ret->En, data) > 0)
ret = ret->left;
else
ret = ret->right;
}
return NULL;
}
//销毁树
void DesTroyDic(Dictionary **q)
{
Dictionary *ret = *q;
if(NULL == *q)
return;
DesTroyDic(&ret->left);
DesTroyDic(&ret->right);
free(ret);
ret = NULL;
}Main.c
#include"Spell.h"
#include"Dictionary.h"
void SpellText()
{
char a[20];
Word *q = NULL;
InsertWord(&q, "apple");
InsertWord(&q, "pen");
InsertWord(&q, "am");
InsertWord(&q, "insert");
printf("请输入你要拼写的单词：");
scanf("%s", a);
if(FindNode(q, a))
printf("拼写正确\n");
else
printf("拼写错误\n");
DesTroyNode(&q);
}
void FindText()
{
char a[20];
int i = 0;
Dictionary *ret = NULL;
InsertTree(&ret, "apple", "苹果");
InsertTree(&ret, "pen", "铅笔");
InsertTree(&ret, "sos", "救命");
InsertTree(&ret, "peg", "猪");
printf("请输入你要查的英文：");
scanf("%s", a);
if(FindTreeNode(ret, a))
printf("%s\n", FindTreeNode(ret, a));
else
printf("没有找到\n");
DesTroyDic(&ret);
}
int main()
{
SpellText();
FindText();
return 0;
}