修正:前驱与后继操作有误,修正
二叉查找树是满足如下性质的二叉树:
- 设x为二叉树中的一个结点,如果y是x的左子树中的一个结点,则key[y]<=key[x]
- 如果y是x的右子树,则key[x]<=key[y]
二叉查找树的数据结构和操作定义如下:
/*file:biTree.h*/
#ifndef CHIYX_BITREE
#define CHIYX_BITREE
#ifndef NULL
#define NULL 0
#endif
typedef int DataType;
//二叉树的节点结构
typedef struct BiTreeNode {
DataType data;
struct BiTreeNode *parent;
struct BiTreeNode *left;
struct BiTreeNode *right;
}BiTreeNode, *BiTree;
//查找:返回第一个等于data域等于key的节点,不存在返回NULL
BiTreeNode *search(BiTree *biTree, DataType key);
//返回二叉树的最小节点,空树返回NULL
BiTreeNode *minImum(BiTree *biTree);
//返回二叉树的最大节点,空树返回NULL
BiTreeNode *maxImum(BiTree *biTree);
//返回节点x的后继节点,不存在后继(节点x为最大节点)返回NULL
BiTreeNode *successor(BiTreeNode *x);
//返回节点x的前驱节点,不存在前驱(节点x为最小节点)返回NULL
BiTreeNode *predecessor(BiTreeNode *x);
//将值data插入到二叉树中(生成一个值为data的节点)
void insertNode(BiTree *biTree, DataType data);
//删除一个值为data的节点
void deleteNode(BiTree *biTree, DataType data);
//中序遍历二叉树
void inorderTraversal(BiTree *biTree, void (*visitor)(BiTreeNode *node));
#endif
它的实现如下:
/*file:biTree.c*/
#include <stdlib.h>
#include "biTree.h"
//查找:返回第一个等于data域等于key的节点,不存在返回NULL
BiTreeNode *search(BiTree *biTree, DataType key) {
BiTreeNode *curNode = *biTree;
while (curNode != NULL && curNode->data != key) {
if (key < curNode->data) {
curNode = curNode->left;
} else {
curNode = curNode->right;
}
}
return curNode;
}
//返回二叉树的最小节点,空树返回NULL
BiTreeNode *minImum(BiTree *biTree) {
BiTreeNode *curNode = *biTree;
while (curNode != NULL && curNode->left != NULL) {
curNode = curNode->left;
}
return curNode;
}
//返回二叉树的最大节点,空树返回NULL
BiTreeNode *maxImum(BiTree *biTree) {
BiTreeNode *curNode = *biTree;
while (curNode != NULL && curNode->right != NULL) {
curNode = curNode->right;
}
return curNode;
}
//返回节点x的后继节点,不存在后继(节点x为最大节点)返回NULL
BiTreeNode *successor(BiTreeNode *x) {
if (x == NULL) return NULL;
//存在右子树,则后继节点为其右子树中最小的节点
if (x != NULL && x->right != NULL) {
return minImum(&(x->right));
}
while (x->parent != NULL && x->parent->right == x) {
x = x->parent;
}
return x->parent; //错误版本为 x, 此处应该返回父结点
}
//返回节点x的前驱节点,不存在前驱(节点x为最小节点)返回NULL
BiTreeNode *predecessor(BiTreeNode *x) {
if (x == NULL) return NULL;
//存在左子树,则后继节点为其左子树中最大的节点
if (x != NULL && x->left != NULL) {
return maxImum(&(x->left));
}
while (x->parent != NULL && x->parent->left == x) {
x = x->parent;
}
return x->parent; //错误版本为 x, 此处应该返回父结点
}
void insertNode(BiTree *biTree, DataType data) {
//创建节点
BiTreeNode *targetNode;
targetNode = (BiTreeNode *)malloc(sizeof(BiTreeNode));
//没有足够内存
if (targetNode == NULL) return;
targetNode->data = data;
targetNode->parent = NULL;
targetNode->left = NULL;
targetNode->right = NULL;
BiTreeNode *p, *y;
p = *biTree;
y = NULL;
while (p != NULL ) {
y = p;
if (targetNode->data < p->data) {
p = p->left;
} else {
p = p->right;
}
}
//空树,将新节点置为树根
if (y == NULL) {
*biTree = targetNode;
} else {
if (targetNode->data < y->data) {
y->left = targetNode;
} else {
y->right = targetNode;
}
}
targetNode->parent = y;
}
//删除一个值为data的节点
void deleteNode(BiTree *biTree, DataType data) {
//查找待删除的节点
BiTreeNode *targetNode, *x, *y;
targetNode = search(biTree, data);
if (targetNode == NULL) return;
//找出真正的删除节点,如果目标节点最多只有一个子树,则其为真正删除的节点
//否则其后继节点(最多只有一个子树,想想为什么)为真正删除的节点,然后将后继节点的值赋给目标节点
if (targetNode->left == NULL || targetNode->right == NULL) {
y = targetNode;
} else {
y = successor(targetNode);
}
if (y->left != NULL) {
x = y->left;
} else {
x = y->right;
}
if (x != NULL) {
x->parent = y->parent;
}
//如果y是根节点, 则根节点变为x
if (y->parent == NULL) {
*biTree = x;
} else {
if (y->parent->right == y) {
y->parent->right = x;
} else {
y->parent->left = x;
}
}
if (y != targetNode) {
targetNode->data = y->data;
}
//释放y占有的空间
free(y);
}
//中序遍历二叉树
void inorderTraversal(BiTree *biTree, void (*visitor)(BiTreeNode *node)) {
BiTreeNode *curNode;
curNode = *biTree;
if (curNode != NULL) {
//遍历左子树
inorderTraversal(&(curNode->left), visitor);
//访问节点
visitor(curNode);
//遍历右子树
inorderTraversal(&(curNode->right), visitor);
}
}
测试代码如下:
#include <stdio.h>
#include <stdlib.h>
#include "biTree.h"
#define N 10
void printNode(BiTreeNode *node);
int main(int argc, char *argv[]) {
BiTreeNode *root;
int i;
root = NULL;
int data[N] = {10, 23, 11, 98, 111, 87, 34, 11, 33, 8};
for (i = 0; i < N; i++) {
insertNode(&root, data[i]);
}
printf("before delete:\n");
inorderTraversal(&root, printNode);
printf("\n");
deleteNode(&root, 11);
deleteNode(&root, 8);
printf("after delete:\n");
inorderTraversal(&root, printNode);
printf("\n");
exit(0);
}
void printNode(BiTreeNode *node) {
printf("%d\t", node->data);
}
运行结果:
before delete:
8 10 11 11 23 33 34 87 98 111
after delete:
10 11 23 33 34 87 98 111
分享到:
相关推荐
数据结构 课程设计 二叉排序树查找C语言代码1 含测试序列.doc
用C++实现的最优二叉查找树,简单,明了,是数据结构里经典必学算法,初学者适用
二叉排序树用C语言实现,内含本人写的报告文档,仅供参考
1.实现二叉搜索树的基本操作 2.包括建立,查找,删除,显示 3.得到最长路径和最短路径,并能分别计算长度
findwords查找文件是否有某单词,这是一个二叉查找树的练习
在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者...
C语言 二叉平衡树实现学生管理系统,用文件保存学生信息,可以实现学生信息的显示、查找、插入、删除、保存等。
第一章 1.1数据结构课程设计要求。 1.1.1数据结构课程设计问题描述。 从键盘读入一组数据,建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作 。 1.1.2数据结构课程设计基本要求。 建立二叉排序树并对其...
/*用函数实现如下二叉排序树算法: (1) 插入新结点 (2) 前序、中序、后序遍历二叉树 (3) 中序遍历的非递归算法 (4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) (6) ...
这是一个完整的二叉排序树的例子,里面有二叉排序树的建立,插入,查找,等等。它是用c语言写的方便大多数的数据结构爱好者写习和使用
(2)掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现方法。 (3)掌握散列存储结构的思想,能选择合适散列函数,实现不同冲突处理方法的散列表的查找、建立。 (4)能运用线性表的查找方法...
2.1.5查找并删除元素模块设计方案………………………………………………………6 2.1.6主函数模块设计方案…………………………………………………………………7 3程序演示……………………………………………………...
使用范围:大学c语言数据结构课程设计 功能: 【基本要求】 1.用二叉链表作存储结构 (1)以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T; (2)对二叉排序树T作中序遍历,输出结果; (3)计算二叉排序...
此外,《数据结构基础(C语言版)(第2版)》还介绍了各种高级或特殊数据结构,如优先级队列、高效二叉查找树、多路查找树等。《数据结构基础(C语言版)(第2版)》对大多数算法都给出了计算时间在最优、最差情形下的复杂度...
此外,本书还介绍了各种高级或特殊数据结构,如优先级队列、高效二叉查找树、多路查找树等。本书对大多数算法都给出了计算时间在最优、最差情形下的复杂度分析。 本书不仅可以作为计算机及相关专业本科生“数据...
要求采用二叉排序树存放学生成绩,一门课程对应一棵二叉排序树; (4)成绩修改:若输入错误可进行修改; (5)统计分析:对某个班级学生的单科成绩进行统计,求出平均成绩;求出成绩处于指定分数段内的学生人数...
合肥工业大学数据结构 查找实验 编写算法实现下列问题的求解。 (1) 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素,并以二分查找的判定树来解释。 (2) 设计出在二叉排序树中插入结点的...
二叉排序树(又称二叉查找树):(1)若左子树不空,则左子树上所有节点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有节点均大于它的根结点的值;(3)它的左右子树分别为二叉排序树。 二叉平衡树:若...
折半查找、二叉排序树的建立、查找与删除、链式哈希表的建立与查找: 1————建立有序表———— 2————折半查找————— 3————建立二叉排序树—— 4————二叉排序树查找—— 5————二叉排序树...
01-001数据结构的概念和基本术语、抽象数据类型的表示与实现 01-002算法设计的要求、算法效率的度量 02-001线性表的类型定义 02-002线性表的顺序表示与实现、线性表的基本操作 02-003单链表的创建与操作、加工型...