“bst.h”头文件声明了相关函数
#pragma once
#ifndef BST_H
#define BST_H
#include <stdio.h>
#include <stdlib.h>
typedef int elementype;
typedef struct BSTNode {
BSTNode* lchild, * rchild;
elementype data;
}BSTNode,*BSTree;
int Insert_node(BSTNode** btree, int num); //插入结点(递归)
int Insert_node2(BSTNode** btree, int num); //插入结点(非递归)
BSTree create_bst(int* num, int len); //创建二叉树调用递归插入
BSTree create_bst2(int* num, int len); //调用非递归插入
BSTNode* search(BSTree* bst, int num); //搜索算法
bool Delet(BSTree* bst, int num); //删除算法
bool delet1(BSTNode* t, BSTNode* p, bool rl); //删除算法的辅助算法
void maxminnode(BSTree t); //练习册上的例题的解法
elementype maxnode(BSTree t);
elementype minnode(BSTree t);
#endif
“create_tree.cpp"主要是树的创建和结点插入算法
#include "bst.h"
int Insert_node(BSTNode** btree, int num) { //递归插入
if ((*btree) == NULL) {
(*btree) = (BSTNode*)malloc(sizeof(BSTNode));
(*btree)->data = num;
(*btree)->lchild = (*btree)->rchild = NULL;
}
else if ((*btree)->data == num)return false;
else if ((*btree)->data > num) {
return Insert_node(&((*btree)->lchild), num);
}
else if ((*btree)->data < num) {
return Insert_node(&((*btree)->rchild), num);
}
}
int Insert_node2(BSTNode** btree, int num) { //非递归插入
if ((*btree) == NULL) {
(*btree) = (BSTNode*)malloc(sizeof(BSTNode));
(*btree)->data = num;
(*btree)->lchild = (*btree)->rchild = NULL;
return true;
}
else {
BSTNode** p; //初始化一个二级指针
p = btree; //用p遍历整个树
while ((*p) != NULL) {
if (num == (*p)->data) return false; //如果
else if (num < (*p)->data) p = &((*p)->lchild); //如果值小于结点的值,那么向左子树移动
else if (num > (*p)->data) p = &((*p)->rchild); //大于则向右子树移动
}
(*p) = (BSTNode*)malloc(sizeof(BSTNode)); //取到左右子树为空时那么插入结点,左子树指针的值为NULL,但是这个指针本身是存在的
(*p)->data = num;
(*p)->lchild = (*p)->rchild = NULL;
}
}
BSTree create_bst(int* num, int len) { //调用递归创建
BSTNode* p = NULL;
for (int i = 0; i < len; i++) Insert_node(&p, num[i]);
return p;
}
BSTree create_bst2(int* num, int len) { //非递归创建
BSTNode* p = NULL;
for (int i = 0; i < len; i++) Insert_node2(&p, num[i]);
return p;
}
BSTNode* search(BSTree* bst, int num) { //这里是非递归写法,num为搜索的数字
BSTNode* p = (*bst);
while (p != NULL && p->data != num) { //注意逻辑表达式的顺序,先要判断指针是否为空,不为空才能访问数据
if (num < p->data) p = p->lchild;
else if (num > p->data) p = p->rchild;
}
return p;
}
void maxminnode(BSTree t) {
if (t->lchild != NULL) printf("%d ", maxnode(t->lchild));
if (t->rchild != NULL) printf("%d ", minnode(t->rchild));
}
elementype minnode(BSTNode* t) {
while (t->lchild != NULL) t = t->lchild;
return t->data;
}
elementype maxnode(BSTNode* t) {
while (t->rchild != NULL) t = t->rchild;
return t->data;
}
“delet.cpp”删除结点的算法
#include "bst.h"
int Insert_node(BSTNode** btree, int num) { //递归插入
if ((*btree) == NULL) {
(*btree) = (BSTNode*)malloc(sizeof(BSTNode));
(*btree)->data = num;
(*btree)->lchild = (*btree)->rchild = NULL;
}
else if ((*btree)->data == num)return false;
else if ((*btree)->data > num) {
return Insert_node(&((*btree)->lchild), num);
}
else if ((*btree)->data < num) {
return Insert_node(&((*btree)->rchild), num);
}
}
int Insert_node2(BSTNode** btree, int num) { //非递归插入
if ((*btree) == NULL) {
(*btree) = (BSTNode*)malloc(sizeof(BSTNode));
(*btree)->data = num;
(*btree)->lchild = (*btree)->rchild = NULL;
return true;
}
else {
BSTNode** p; //初始化一个二级指针
p = btree; //用p遍历整个树
while ((*p) != NULL) {
if (num == (*p)->data) return false; //如果
else if (num < (*p)->data) p = &((*p)->lchild); //如果值小于结点的值,那么向左子树移动
else if (num > (*p)->data) p = &((*p)->rchild); //大于则向右子树移动
}
(*p) = (BSTNode*)malloc(sizeof(BSTNode)); //取到左右子树为空时那么插入结点,左子树指针的值为NULL,但是这个指针本身是存在的
(*p)->data = num;
(*p)->lchild = (*p)->rchild = NULL;
}
}
BSTree create_bst(int* num, int len) { //调用递归创建
BSTNode* p = NULL;
for (int i = 0; i < len; i++) Insert_node(&p, num[i]);
return p;
}
BSTree create_bst2(int* num, int len) { //非递归创建
BSTNode* p = NULL;
for (int i = 0; i < len; i++) Insert_node2(&p, num[i]);
return p;
}
BSTNode* search(BSTree* bst, int num) { //这里是非递归写法,num为搜索的数字
BSTNode* p = (*bst);
while (p != NULL && p->data != num) { //注意逻辑表达式的顺序,先要判断指针是否为空,不为空才能访问数据
if (num < p->data) p = p->lchild;
else if (num > p->data) p = p->rchild;
}
return p;
}
void maxminnode(BSTree t) {
if (t->lchild != NULL) printf("%d ", maxnode(t->lchild));
if (t->rchild != NULL) printf("%d ", minnode(t->rchild));
}
elementype minnode(BSTNode* t) {
while (t->lchild != NULL) t = t->lchild;
return t->data;
}
elementype maxnode(BSTNode* t) {
while (t->rchild != NULL) t = t->rchild;
return t->data;
}
“main.cpp”部分代码的测试
#include "bst.h"
int main(void) {
int num[] = { 6,2,9,5,7,10,4};
BSTree bst=create_bst2(num, sizeof(num) / sizeof(int));
Delet(&bst, 6);
maxminnode(bst);
}