[C++系列] 算法与数据结构 day03 二叉树,算法
in C/C++ with 0 comment

[C++系列] 算法与数据结构 day03 二叉树,算法

in C/C++ with 0 comment

基于二叉链表的有序二叉树

基于二叉链表的有序二叉树

问题

BSTBinary Search Tree的缩写,译为二叉搜索树,或有序二叉树,是二叉树的一种,它的定义如下:
1)或者是一棵空树;
2)或者是具有下列性质的二叉树:
I) 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
II) 若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
III)左、右子树也分别为二叉排序树;
BST在查找一个结点或插入一个结点时,具有极大的优势,速度非常快。是一种基础性数据结构,广泛应用于更加抽象的集合、关联数组等数据结构。
1.2 方案

BST的基本操作包括:
1) 创建结点,新生成一个结点用于向BST中添加。
2) 增加结点,在BST中加入一个数据元素。
3) 删除结点,在BST中删除一个数据元素。
4) 查找结点,在BST中查找指定的数据是否存在,如果存在则得到其地址。
5) 修改结点,对BST中指定的数据进行修改。
6) 清除一棵树

1.3 步骤

实现此案例需要按照如下步骤进行。
步骤一:定义BST结点结构

在C语言中:
1)定义一个变量data,用来模拟BST中的数据。
2)定义一个指针left,用于指向该结点的左孩子。
3)定义一个指针right,用于指向该结点的右孩子。
4)这三方面的信息共同描述一个BST结点,可将它们封装在一起。
代码如下:

typedef int DataType;
struct Node{
DataType data;
struct Node *left;
struct Node *right;
};

步骤二:创建结点

首先,向操作系统申请一块存储空间。
然后,存储数据域数据
最后,将左孩子和右孩子指针赋值为空。
代码如下所示:

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct Node{
DataType data;
struct Node *left;
struct Node *right;
};
//创建一个节点
struct Node* createNode(DataType d)
{
struct Node *pn = (struct Node*)malloc(sizeof(struct Node));
pn->data = d;
pn->left = pn->right = NULL;
return pn;
}

步骤三:增加结点

首先,判断要插入的结点是否存在。
然后,判断根结点是否为空。
1)若根结点不为空,则当要插入的结点数据大于根结点的数据时,插入右子树;否则插入左子树。
2)若根结点为空,则将新加入的结点添加到根结点处。
代码如下所示:

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct Node{
DataType data;
struct Node *left;
struct Node *right;
};
//创建一个节点
struct Node* createNode(DataType d)
{
struct Node *pn = (struct Node*)malloc(sizeof(struct Node));
pn->data = d;
pn->left = pn->right = NULL;
return pn;
}
//讲一个节点插入到一个树中
void insert(struct Node** root, struct Node* pn) {
if (pn == NULL) return;
//树为空
if (*root == NULL) {*root = pn; return;}
//树不为空
if (pn->data > (*root)->data) {
insert(&(*root)->right, pn);
}else {
insert(&(*root)->left, pn);
}
}

步骤四:删除结点

首先,查找要删除的结点,若不存在,则直接返回。
然后,若要被删除的结点没有左子树,则作如下处理:
1)要被删除的结点的双亲结点不存在时,则表明要删除根结点,此时只需将要删除结点的右孩子结点变成根结点即可。
2)要被删除的结点是其双亲结点的左孩子时,将要删除结点的右子树变成双亲结点的左孩子即可。
3) 要被删除的结点是其双亲结点的右孩子时,将要删除结点的右子树变成双亲结点的右孩子即可。
4)释放要被删除结点所占的存储空间。
最后,若要被删除的结点有左子树,则作如下处理:
1)在要删除结点的左子树中查找最右下的结点。
2)如果最右下结点的双亲结点与被删除结点是同一结点,则将最右下结点的双亲结点的左孩子变为最右下结点的左孩子。
3)如果最右下结点的双亲结点与被删除结点不是同一结点,则将最右下结点的双亲结点的右孩子变为最右下结点的左孩子。
4)将最右下结点的数据复制到要删除结点内。
5)释放最右下结点所占的存储空间。
代码如下:

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct Node{
DataType data;
struct Node *left;
struct Node *right;
};
//创建一个节点
struct Node* createNode(DataType d)
{
struct Node *pn = (struct Node*)malloc(sizeof(struct Node));
pn->data = d;
pn->left = pn->right = NULL;
return pn;
}
//讲一个节点插入到一个树中
void insert(struct Node** root, struct Node* pn) {
if (pn == NULL) return;
//树为空
if (*root == NULL) {*root = pn; return;}
//树不为空
if (pn->data > (*root)->data) {
insert(&(*root)->right, pn);
}else {
insert(&(*root)->left, pn);
}
}
//在二叉排序树t中删去关键字为k的结点
void delete(struct Node** root, DataType k)
{
struct Node* p, *f, *s, *q;
p=*root;
f=NULL;
while(p)//查找关键字为k的待删结点p
{
if(p->data==k ) break; //找到则跳出循环
f=p; //f指向p结点的双亲结点
if(p->data>k)
p=p->left;
else
p=p->right;
}
if(p==NULL) return; //若找不到,返回原来的二叉排序树
if(p->left==NULL) //p无左子树
{
if(f==NULL)
*root=p->right; //p是原二叉排序树的根
else if(f->left==p) //p是f的左孩子
f->left=p->right; //将p的右子树链到f的左链上
else //p是f的右孩子
f->right=p->right; //将p的右子树链到f的右链上
free(p);
}
else //p有左子树
{
q=p;
s=p->left;
while(s->right) //在p的左子树中查找最右下结点
{
q=s;
s=s->right;
}
if(q==p)
q->left=s->left; //将s的左子树链到q上
else
q->right=s->left;
p->data=s->data; //将s的值赋给p
free(s);
}
}
上述代码中,以下代码:
while(p)//查找关键字为k的待删结点p
{
if(p->data==k ) break; //找到则跳出循环
f=p; //f指向p结点的双亲结点
if(p->data>k)
p=p->left;
else
p=p->right;
}
if(p==NULL) return; //若找不到,返回原来的二叉排序树
设置循环查找要删除的结点,若不存在,则直接返回。
上述代码中,以下代码:
if(p->left==NULL) //p无左子树
{
if(f==NULL)
*root=p->right; //p是原二叉排序树的根
else if(f->left==p) //p是f的左孩子
f->left=p->right; //将p的右子树链到f的左链上
else //p是f的右孩子
f->right=p->right; //将p的右子树链到f的右链上
free(p);
}

是若要被删除的结点没有左子树时的情形,其中指针p指向要被删除的结点,指针f指向被删除的结点的双亲结点。

if(f==NULL)
*root=p->right; //p是原二叉排序树的根

表示要被删除的结点的双亲结点不存在时,要删除根结点。

else if(f->left==p) //p是f的左孩子
f->left=p->right; //将p的右子树链到f的左链上
表示要被删除的结点是其双亲结点的左孩子时,将要删除结点的右子树变成双亲结点的左孩子即可。
else //p是f的右孩子
f->right=p->right; //将p的右子树链到f的右链上
表示要被删除的结点是其双亲结点的右孩子时,将要删除结点的右子树变成双亲结点的右孩子即可。
上述代码中,以下代码:
else //p有左子树
{
q=p;
s=p->left;
while(s->right) //在p的左子树中查找最右下结点
{
q=s;
s=s->right;
}
if(q==p)
q->left=s->left; //将s的左子树链到q上
else
q->right=s->left;
p->data=s->data; //将s的值赋给p
free(s);
}
是若要被删除的结点有左子树时的情形,其中指针p指向要被删除的结点,指针s指向最右下结点,指针q指向最右下结点的双亲结点。
s=p->left;
while(s->right) //在p的左子树中查找最右下结点
{
q=s;
s=s->right;
}

是在要删除结点的左子树中查找最右下的结点。
if(q==p)
q->left=s->left; //将s的左子树链到q上
表示如果最右下结点的双亲结点q与被删除结点p是同一结点,则将最右下结点的双亲结点q的左孩子q->left变为最右下结点s的左孩子s->left。
else
q->right=s->left;
表示如果最右下结点的双亲结点q与被删除结点p不是同一结点,则将最右下结点的双亲结点q的右孩子q->right变为最右下结点s的左孩子s->left。
步骤五:查找结点

首先,判断根结点是否为空,若是则直接返回NULL。
然后,在根结点不为空的情况下,若要查找的数据大于根结点数据,遍历右子树查找。
下一步,在根结点不为空的情况下,若要查找的数据小于根结点数据,遍历左子树查找。
最后,在根结点不为空的情况下,若要查找的数据等于根结点数据,则返回根结点。
代码如下:

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct Node{
DataType data;
struct Node *left;
struct Node *right;
};
//创建一个节点
struct Node* createNode(DataType d)
{
struct Node *pn = (struct Node*)malloc(sizeof(struct Node));
pn->data = d;
pn->left = pn->right = NULL;
return pn;
}
//讲一个节点插入到一个树中
void insert(struct Node** root, struct Node* pn) {
if (pn == NULL) return;
//树为空
if (*root == NULL) {*root = pn; return;}
//树不为空
if (pn->data > (*root)->data) {
insert(&(*root)->right, pn);
}else {
insert(&(*root)->left, pn);
}
}
//在二叉排序树t中删去关键字为k的结点
void delete(struct Node** root, DataType k)
{
struct Node* p, *f, *s, *q;
p=*root;
f=NULL;
while(p)//查找关键字为k的待删结点p
{
if(p->data==k ) break; //找到则跳出循环
f=p; //f指向p结点的双亲结点
if(p->data>k)
p=p->left;
else
p=p->right;
}
if(p==NULL) return; //若找不到,返回原来的二叉排序树
if(p->left==NULL) //p无左子树
{
if(f==NULL)
*root=p->right; //p是原二叉排序树的根
else if(f->left==p) //p是f的左孩子
f->left=p->right; //将p的右子树链到f的左链上
else //p是f的右孩子
f->right=p->right; //将p的右子树链到f的右链上
free(p);
}
else //p有左子树
{
q=p;
s=p->left;
while(s->right) //在p的左子树中查找最右下结点
{
q=s;
s=s->right;
}
if(q==p)
q->left=s->left; //将s的左子树链到q上
else
q->right=s->left;
p->data=s->data; //将s的值赋给p
free(s);
}
}
//查找一个树
struct Node* find(struct Node* root, DataType d){
if(root == NULL)
return NULL;
if(d > root->data) //查找右子树
return find(root->right,d);
else if(d < root->data) //查找左子树
return find(root->left,d);
else
return root;
}

步骤六:修改结点

首先,使用步骤四的方法查找到要修改的结点。
然后,将要修改的结点数据修改为指定数据。
代码如下:

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct Node{
DataType data;
struct Node *left;
struct Node *right;
};
//创建一个节点
struct Node* createNode(DataType d)
{
struct Node *pn = (struct Node*)malloc(sizeof(struct Node));
pn->data = d;
pn->left = pn->right = NULL;
return pn;
}
//讲一个节点插入到一个树中
void insert(struct Node** root, struct Node* pn) {
if (pn == NULL) return;
//树为空
if (*root == NULL) {*root = pn; return;}
//树不为空
if (pn->data > (*root)->data) {
insert(&(*root)->right, pn);
}else {
insert(&(*root)->left, pn);
}
}
//在二叉排序树t中删去关键字为k的结点
void delete(struct Node** root, DataType k)
{
struct Node* p, *f, *s, *q;
p=*root;
f=NULL;
while(p)//查找关键字为k的待删结点p
{
if(p->data==k ) break; //找到则跳出循环
f=p; //f指向p结点的双亲结点
if(p->data>k)
p=p->left;
else
p=p->right;
}
if(p==NULL) return; //若找不到,返回原来的二叉排序树
if(p->left==NULL) //p无左子树
{
if(f==NULL)
*root=p->right; //p是原二叉排序树的根
else if(f->left==p) //p是f的左孩子
f->left=p->right; //将p的右子树链到f的左链上
else //p是f的右孩子
f->right=p->right; //将p的右子树链到f的右链上
free(p);
}
else //p有左子树
{
q=p;
s=p->left;
while(s->right) //在p的左子树中查找最右下结点
{
q=s;
s=s->right;
}
if(q==p)
q->left=s->left; //将s的左子树链到q上
else
q->right=s->left;
p->data=s->data; //将s的值赋给p
free(s);
}
}
//查找一个树
struct Node* find(struct Node* root, DataType d){
if(root == NULL)
return NULL;
if(d > root->data) //查找右子树
return find(root->right,d);
else if(d < root->data) //查找左子树
return find(root->left,d);
else
return root;
}
//修改树中结点的值
void modify(struct Node* root, DataType oldData, DataType newData)
{
struct Node* p;
p = find(root, oldData);
p->data = newData;
}
1.4 完整代码

本案例的完整代码如下所示:
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct Node{
DataType data;
struct Node *left;
struct Node *right;
};
//创建一个节点
struct Node* createNode(DataType d)
{
struct Node *pn = (struct Node*)malloc(sizeof(struct Node));
pn->data = d;
pn->left = pn->right = NULL;
return pn;
}
//讲一个节点插入到一个树中
void insert(struct Node** root, struct Node* pn) {
if (pn == NULL) return;
//树为空
if (*root == NULL) {*root = pn; return;}
//树不为空
if (pn->data > (*root)->data) {
insert(&(*root)->right, pn);
}else {
insert(&(*root)->left, pn);
}
}
//在二叉排序树t中删去关键字为k的结点
void delete(struct Node** root, DataType k)
{
struct Node* p, *f, *s, *q;
p=*root;
f=NULL;
while(p)//查找关键字为k的待删结点p
{
if(p->data==k ) break; //找到则跳出循环
f=p; //f指向p结点的双亲结点
if(p->data>k)
p=p->left;
else
p=p->right;
}
if(p==NULL) return; //若找不到,返回原来的二叉排序树
if(p->left==NULL) //p无左子树
{
if(f==NULL)
*root=p->right; //p是原二叉排序树的根
else if(f->left==p) //p是f的左孩子
f->left=p->right; //将p的右子树链到f的左链上
else //p是f的右孩子
f->right=p->right; //将p的右子树链到f的右链上
free(p);
}
else //p有左子树
{
q=p;
s=p->left;
while(s->right) //在p的左子树中查找最右下结点
{
q=s;
s=s->right;
}
if(q==p)
q->left=s->left; //将s的左子树链到q上
else
q->right=s->left;
p->data=s->data; //将s的值赋给p
free(s);
}
}
//查找一个树
struct Node* find(struct Node* root, DataType d){
if(root == NULL)
return NULL;
if(d > root->data) //查找右子树
return find(root->right,d);
else if(d < root->data) //查找左子树
return find(root->left,d);
else
return root;
}
//修改树中结点的值
void modify(struct Node* root, DataType oldData, DataType newData)
{
struct Node* p;
p = find(root, oldData);
p->data = newData;
}
//清除一颗树
void clears(struct Node **root) {
if (*root == NULL) return;
clears(&(*root)->left);
clears(&(*root)->right);
free(*root);
*root = NULL;
}
//打印一颗树
void print(struct Node* root) {
if (root == NULL) return;
printf("%d ", root->data);
print(root->left);
print(root->right);
}
int main() {
struct Node* root = NULL;
insert(&root, createNode(10));
insert(&root, createNode(5));
insert(&root, createNode(3));
insert(&root, createNode(2));
insert(&root, createNode(1));
insert(&root, createNode(4));
insert(&root, createNode(7));
insert(&root, createNode(6));
insert(&root, createNode(9));
insert(&root, createNode(8));
insert(&root, createNode(15));
print(root);
printf("\n");
printf("%d\n", find(root, 5)->data);
delete(&root, 10);
print(root);
return 0;
}
Responses