数据结构排序二叉树(下)

哎,调了几天深度学习模型,今天来更新排序二叉树

前言

一、排序二叉树的结构定义

二、在排序二叉树添加数据

三、定义创建排序二叉树函数

四、查找一棵二叉排序树中的结点x的所在层数

五、删除二叉排序树中T关键字x的节点

六、查找二叉排序树中的所有小于key的关键字

七、已知二叉排序中每个节点值为整形,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的

八.总结与验证

---

前言

排序二叉树就这几个习题了,但实际上还有更难得几道习题,因为实现起来真的难,而且在使用中也难用到所以就给大家几道简单的例子,帮助大家来熟悉.

---

一、排序二叉树的结构定义

typedef int ElemType;
//二叉排序树左>根>右,树中没有重复值
//二叉排序树的数据结构
typedef struct BSTNode {
	ElemType data;//数据节点类型为int
	struct BSTNode* lchild;
	struct BSTNode* rchild;
}BSTNode,*BSTree;

其实就是二叉树的数据结构只是对树中节点数据有约束.

二、在排序二叉树添加数据

//插入节点函数
void insertNode(BSTree& T, ElemType e) {
	if (T == NULL) {//找到合适的位置插入节点
		BSTNode* pNode = (BSTNode*)malloc(sizeof(BSTNode));
		assert(pNode);
		pNode->data = e;
		pNode->lchild = NULL;
		pNode->rchild = NULL;
		T = pNode;//别忘了链接上
	}
	else if (T->data > e) {//插入左子树
		insertNode(T->lchild, e);
	}
	else if (T->data < e) {//插入右子树
		insertNode(T->rchild, e);
	}
}

由于二叉树左>根>右所以在构建二叉树使需要满足要求.

算法思想:运用递归思想,将待插入数据与当前节点比较如果小于当前节点数据表明插入数据应插在当前节点的左子树,反之当如果插入数据比当前的节点数据大,则表明插入数据应插到当前数据的右子树,直到遇到空节点表示找到插入位置,申请节点插入即可.

三、定义创建排序二叉树函数

//定义创建二叉排序树函数
BSTNode* creatBSTree() {
	BSTNode* T = NULL;
	ElemType enternum = 999999;//999999表示退出输入
	printf("请输入序列(以999999作为结束标志):");
	while (scanf("%d", &enternum) && enternum != 999999) {
		insertNode(T, enternum);
	}
	return T;
}

就依次插入节点就可以了.

四、查找一棵二叉排序树中的结点x的所在层数

//例1:查找一棵二叉排序树中的结点x的所在层数
int nodelevel(BSTree T, int level,ElemType x) {
	if (T == NULL) {//没找到返回0
		return 0;
	}
	else if (T->data > x) {//左子树寻找
		return nodelevel(T->lchild, level+1, x);
	}
	else if (T->data < x) {//右子树寻找
		return nodelevel(T->rchild, level+1, x);
	}
	else {
		return level;//返回层次
	}
}

算法思想:采用递归的形式,但传参时传入一个层数,找到返回即可,注意这里层数是值传递,不是址传递.

五、删除二叉排序树中T关键字x的节点

//例2:删除二叉排序树中T关键字x的节点
//算法思想:首先找到节点x此时就要分情况讨论(1)节点既没有左孩子又没有右孩子,直接删去节点并将指针制空;
//(2)节点只有左孩子(或只有右孩子),指针指向左孩子(右孩子)并删除节点;
//(3)节点既有左孩子又有右孩子,此时有两种处理方案1.找到左子树的最大节点将右孩子链接到最大节点的右指针
//2.找到右子树的最小节点,将左孩子链接到最小节点的左指针
void deleteOperation(BSTree& T) {
	if (T == NULL) return;
	if (T->lchild == NULL && T->rchild == NULL) {
		free(T);
		T = NULL;
	}
	else if (T->lchild != NULL && T->rchild == NULL) {
		BSTNode* tmp = T;
		T = T->lchild;
		free(tmp);
		tmp = NULL;
	}
	else if (T->lchild == NULL && T->rchild != NULL) {
		BSTNode* tmp = T;
		T = T->rchild;
		free(tmp);
		tmp = NULL;
	}
	else {//既有左孩子又有右孩子
		BSTNode* pMaxnode = T->lchild;
		while (pMaxnode->rchild != NULL) {
			pMaxnode = pMaxnode->rchild;
		}
		pMaxnode->rchild = T->rchild;
		BSTNode* tmp = T;
		T = T->lchild;
		free(tmp);
		tmp = NULL;
	}
}
//查找并删除节点
void deletenode(BSTree &T,ElemType x) {
	if (T != NULL) {
		if (T->data == x) {
			deleteOperation(T);
		}
		else if (T->data < x) {
			deletenode(T->rchild, x);
		}
		else {
			deletenode(T->lchild, x);
		}
	}

}

这个算法还有一个思想就是找到左子树最大的节点复制到删除节点上,递归在左子树删除左子树最大节点.

字有点丑见谅.

六、查找二叉排序树中的所有小于key的关键字

//例3:查找二叉排序树中的所有小于key的关键字
void getSmallerkey(BSTree T, ElemType key) {
	if (T != NULL) {
		getSmallerkey(T->lchild, key);
		if (T->data < key) {
			printf("%d ", T->data);
			getSmallerkey(T->rchild, key);
		}
	}
}

七、已知二叉排序中每个节点值为整形,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的

//例4:已知二叉排序中每个节点值为整形,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的节点
//定义递归删除树函数
void deleteFunc(BSTree& T) {//递归删除树
	if (T != NULL) {
		deleteFunc(T->lchild);
		deleteFunc(T->rchild);
		free(T);
		T = NULL;
	}
}
//定义删除小于x节点的函数(采用先序遍历的思想)
void deleteSmallernode(BSTree &T,ElemType x) {
	if (T != NULL) {
		if (T->data == x) {//根节点等于x说明左子树都小于x递归删除
			deleteFunc(T->lchild);
		}
		else if (T->data < x) {//根节点小于x左子树均小于x,删除根节点在递归删除右子树小于x的节点
			deleteFunc(T->lchild);
			BSTNode* tmp = T;
			T = T->rchild;
			free(tmp);
			tmp = NULL;
			deleteSmallernode(T, x);
		}
		else {//根节点大于x递归删除左子树小于x的节点
			deleteSmallernode(T->lchild, x);
		}
	}
}

八.总结与验证

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
typedef int ElemType;
//二叉排序树左>根>右,树中没有重复值
//二叉排序树的数据结构
typedef struct BSTNode {
	ElemType data;//数据节点类型为int
	struct BSTNode* lchild;
	struct BSTNode* rchild;
}BSTNode,*BSTree;
//插入节点函数
void insertNode(BSTree& T, ElemType e) {
	if (T == NULL) {//找到合适的位置插入节点
		BSTNode* pNode = (BSTNode*)malloc(sizeof(BSTNode));
		assert(pNode);
		pNode->data = e;
		pNode->lchild = NULL;
		pNode->rchild = NULL;
		T = pNode;//别忘了链接上
	}
	else if (T->data > e) {//插入左子树
		insertNode(T->lchild, e);
	}
	else if (T->data < e) {//插入右子树
		insertNode(T->rchild, e);
	}
}
//定义创建二叉排序树函数
BSTNode* creatBSTree() {
	BSTNode* T = NULL;
	ElemType enternum = 999999;//999999表示退出输入
	printf("请输入序列(以999999作为结束标志):");
	while (scanf("%d", &enternum) && enternum != 999999) {
		insertNode(T, enternum);
	}
	return T;
}
//中序遍历二叉排序树
void inorderTraverse(BSTree T) {
	if (T != NULL) {
		inorderTraverse(T->lchild);
		printf("%d ", T->data);
		inorderTraverse(T->rchild);
	}
}
//先序遍历二叉排序树
void preorderTraverse(BSTree T) {
	if (T != NULL) {
		printf("%d ", T->data);
		preorderTraverse(T->lchild);
		preorderTraverse(T->rchild);
	}
}
//遍历二叉排序树(先,中)
void Traverse(BSTree T) {//这函数主要是用来验证
	printf("中序遍历结果:");
	inorderTraverse(T);
	printf("\n");
	printf("先序遍历结果:");
	preorderTraverse(T);
	printf("\n");
}
//例1:查找一棵二叉排序树中的结点x的所在层数
int nodelevel(BSTree T, int level,ElemType x) {
	if (T == NULL) {//没找到返回0
		return 0;
	}
	else if (T->data > x) {//左子树寻找
		return nodelevel(T->lchild, level+1, x);
	}
	else if (T->data < x) {//右子树寻找
		return nodelevel(T->rchild, level+1, x);
	}
	else {
		return level;//返回层次
	}
}
//例2:删除二叉排序树中T关键字x的节点
//算法思想:首先找到节点x此时就要分情况讨论(1)节点既没有左孩子又没有右孩子,直接删去节点并将指针制空;
//(2)节点只有左孩子(或只有右孩子),指针指向左孩子(右孩子)并删除节点;
//(3)节点既有左孩子又有右孩子,此时有两种处理方案1.找到左子树的最大节点将右孩子链接到最大节点的右指针
//2.找到右子树的最小节点,将左孩子链接到最小节点的左指针
void deleteOperation(BSTree& T) {
	if (T == NULL) return;
	if (T->lchild == NULL && T->rchild == NULL) {
		free(T);
		T = NULL;
	}
	else if (T->lchild != NULL && T->rchild == NULL) {
		BSTNode* tmp = T;
		T = T->lchild;
		free(tmp);
		tmp = NULL;
	}
	else if (T->lchild == NULL && T->rchild != NULL) {
		BSTNode* tmp = T;
		T = T->rchild;
		free(tmp);
		tmp = NULL;
	}
	else {//既有左孩子又有右孩子
		BSTNode* pMaxnode = T->lchild;
		while (pMaxnode->rchild != NULL) {
			pMaxnode = pMaxnode->rchild;
		}
		pMaxnode->rchild = T->rchild;
		BSTNode* tmp = T;
		T = T->lchild;
		free(tmp);
		tmp = NULL;
	}
}
//查找并删除节点
void deletenode(BSTree &T,ElemType x) {
	if (T != NULL) {
		if (T->data == x) {
			deleteOperation(T);
		}
		else if (T->data < x) {
			deletenode(T->rchild, x);
		}
		else {
			deletenode(T->lchild, x);
		}
	}

}
//例3:查找二叉排序树中的所有小于key的关键字
void getSmallerkey(BSTree T, ElemType key) {
	if (T != NULL) {
		getSmallerkey(T->lchild, key);
		if (T->data < key) {
			printf("%d ", T->data);
			getSmallerkey(T->rchild, key);
		}
	}
}
//例4:已知二叉排序中每个节点值为整形,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的节点
//定义递归删除树函数
void deleteFunc(BSTree& T) {//递归删除树
	if (T != NULL) {
		deleteFunc(T->lchild);
		deleteFunc(T->rchild);
		free(T);
		T = NULL;
	}
}
//定义删除小于x节点的函数(采用先序遍历的思想)
void deleteSmallernode(BSTree &T,ElemType x) {
	if (T != NULL) {
		if (T->data == x) {//根节点等于x说明左子树都小于x递归删除
			deleteFunc(T->lchild);
		}
		else if (T->data < x) {//根节点小于x左子树均小于x,删除根节点在递归删除右子树小于x的节点
			deleteFunc(T->lchild);
			BSTNode* tmp = T;
			T = T->rchild;
			free(tmp);
			tmp = NULL;
			deleteSmallernode(T, x);
		}
		else {//根节点大于x递归删除左子树小于x的节点
			deleteSmallernode(T->lchild, x);
		}
	}
}
int main() {
	//创建一棵二叉排序树
	//8 5 4 7 9 10 999999
	BSTree T = creatBSTree();
	Traverse(T);
	printf("\n");
	int a = 10;
	printf("数据节点为%d的节点所在层次:%d\n", a,nodelevel(T, 1, a));
	printf("删除数据节点前树的结构\n");
	Traverse(T);
	deletenode(T, 5);
	printf("删除数据节点后树的结构\n");
	Traverse(T);
	printf("比8小的数据节点有:");
	getSmallerkey(T, 8);
	printf("\n");
	int b = 8;
	printf("删除比%d小的所有节点前\n",b);
	Traverse(T);
	deleteSmallernode(T, b);
	printf("删除比%d小的所有节点后\n", b);
	Traverse(T);
	return 0;
}

兄弟们马上要到图啦,最有意思的一部分要到啦.加油哦