IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 二叉排序树(二叉搜索树)的算法实现 -> 正文阅读

[数据结构与算法]二叉排序树(二叉搜索树)的算法实现

二叉排序树(二叉搜索树)的算法实现

二叉排序树有以下五个特征:
1.左子树非空,左子树上的所有结点的值都小于其根上的值
2.右子树非空,右子树上的所有结点的值都大于其跟上的值
3.按照中序遍历的方法可以得到一个有序的序列(从小到大)
4.二叉排序树上的任何一棵子树都是这样有序的
5.二叉排序树的查询效率是最高的
以下是二叉排序树的构造,插入结点,遍历(中序)的代码部分。

#include <iostream>
#include <string.h>
using namespace std;

typedef struct data{
	int first;
	char second[10];
}DATA,*LPDATA;

typedef struct binaryTreeNode
{
	DATA element;
	struct binaryTreeNode* Lchild;
	struct binaryTreeNode* Rchild;
}NODE,*LPNODE;

typedef struct binarySearchTree
{
	struct binaryTreeNode* root;
	int treeSize;
}BTREE,*LPBTREE;

//创建一个结点
LPNODE creatNode(DATA element)
{
	LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
	newNode->element = element;
	newNode->Lchild = NULL;
	newNode->Rchild = NULL;
	return newNode;
}

//创建一棵树
LPBTREE creatBinarySearchTree()
{
	LPBTREE tree = (LPBTREE)malloc(sizeof(BTREE));
	tree->root = NULL;
	tree->treeSize = 0; //树的容量
	return tree;
}

int size(LPBTREE tree)
{
	return tree->treeSize;
}

int empty(LPBTREE tree)
{
	if (tree->treeSize == 0)
		return 1;
	else
		return 0;
}

//插入结点
void insertNode(LPBTREE tree, DATA element)
{
	LPNODE moveNode = tree->root;
	LPNODE moveParent = NULL;
	//找到新结点的插入位置
	while (moveNode != NULL)
	{
		moveParent = moveNode;
		if (element.first < moveNode->element.first)  //插入的数据比当前结点小
		{
			moveNode = moveNode->Lchild;
		}
		else if (element.first>moveNode->element.first) //插入的数据比当前结点大
		{
			moveNode = moveNode->Rchild;
		}
		else  // 插入的数据和当前结点的大小一致 (用最新的相同数据把原来的数据覆盖)
		{
			strcpy(moveNode->element.second, element.second);  //比较的是关键字,内容是关键词和数据,就是上面char类型数组中的内容【关键字,内容】
			return;
		}
	}

	//插入新的结点 
	LPNODE newNode = creatNode(element);
	//插入的位置是移动结点父结点的位置后(左或右孩子的位置)
	if (tree->root == NULL)
	{
		tree->root = newNode;
	}
	else
	{
		if (moveParent->element.first > element.first)
		{
			moveParent->Lchild = newNode;
		}
		else
		{
			moveParent->Rchild = newNode;
		}
	}
}

//中序遍历
void printTree(LPNODE root)
{
	if (root != NULL)
	{
		printTree(root->Lchild);
		cout << root->element.first << "" << root->element.second << endl;
		printTree(root->Rchild);
	}
}

void printSearchTree(LPBTREE tree)
{
	printTree(tree->root);
}

void main()
{
	DATA Data[4] = { 23, "小红", 58, "小明", 67, "小亮", 88, "小张" };
	LPBTREE tree = creatBinarySearchTree();
	for (int i = 0; i < 4; i++)
	{
		insertNode(tree,Data[i]);
	}
	printSearchTree(tree);
	system("pause");
}

主要思路:
1.构造数据类型的结构体DATA,构造结点类型的结构体,构造二叉排序树类型的结构体。
他们之间的关系:二叉排序树的结构体确定数的根,结点类型的结构体是为了向书中添加结点,数据类型的结构体为了表示存储的数据

2 设计创建新结点的函数,目的是为了后面方便插入新的结点

3 设计创建二叉排序树的函数,目的是创建二叉排序树的根来确定一棵二叉排序树

4 设计结点插入函数,这时候首先得先找结点的插入位置,方法就是让新添加进来的结点的键值和二叉排序树中结点的键值进行比较,小的是左孩子,大的是右孩子。当找到位置了以后呢,就需要插入新的结点,插入新的结点是插入在所要插入位置的父亲结点的左孩子或右孩子上,这时候就需要设置一个标记量来记录之前移动指针的位置,这样能方便的找到目的父节点的位置。找到位置以后呢,还是判断大小来选择插入的是左孩子还是右孩。最后完成插入。

5 中序输出,利用递归中序输出的方法输出出来。

  数据结构与算法 最新文章
LeetCode 383 赎金信[数组] HERODING的Leet
matlab中fill函数的使用方法
动态规划总结篇一
LeetCode530 二叉搜索树的最小绝对差
单链表的增删改查
拓扑排序 golang实现
用栈实现队列的功能Java(leetcode)
两数相加
动态规划思路
希尔排序——C++实现
上一篇文章      下一篇文章      查看所有文章
加:2021-09-26 10:26:26  更:2021-09-26 10:28:59 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年12日历 -2021/12/4 21:28:25-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码