首页 > 其他分享 >创建一个二叉排序树(Binary Search Tree)

创建一个二叉排序树(Binary Search Tree)

时间:2023-09-29 17:44:32浏览次数:43  
标签:Binary Search right BSTNode Tree 结点 value NULL left

一、二叉排序树的定义

  1. 左子树所有结点的值均小于根结点的值
  2. 右子树所有结点的值均大于根节点的值
  3. 左子树和右子树也是二叉排序树

1.二叉排序树的结点结构

typedef struct BSTNode {
	/*二叉排序树的结点结构*/
	int value;
	struct BSTNode *left;
	struct BSTNode *right;
} BSTNode, *BST;

2.二叉排序树示例

二、向二叉排序树插入一个结点

void insert(BST T, int v) {
	/*二叉排序树上插入值为v的一个结点*/
	if (T != NULL) {
		if (T->value < v && T->right == NULL) {
			/*当前结点是合适的插入位置*/
			T->right = (BSTNode*)malloc(sizeof(BSTNode));
			T->right->value = v;
			T->right->left = NULL;
			T->right->right = NULL;
		} else if (T->value > v && T->left == NULL) {
			/*当前结点是合适的插入位置*/
			T->left = (BSTNode*)malloc(sizeof(BSTNode));
			T->left->value = v;
			T->left->left = NULL;
			T->left->right = NULL;
		} else if (T->value < v && T->right != NULL) {
			/*当前结点不是合适的插入位置,继续在右子树上寻找插入位置*/
			insert(T->right, v);
		} else if (T->value > v && T->left != NULL) {
			/*当前结点不是合适的插入位置,继续在右子树上寻找插入位置*/
			insert(T->left, v);
		}
	} 
}

三、运行结果

第一行输入节点数量
第二行输入每个节点的数据域
后三行输出先序、中序、后序遍历序列

四、完整C代码

点击查看代码
#include <stdio.h>
#include <stdlib.h>

typedef struct BSTNode {
	/*二叉排序树的结点结构*/
	int value;
	struct BSTNode *left;
	struct BSTNode *right;
} BSTNode, *BST;

void insert(BST T, int v);
void visit(BSTNode* node);
void preOrder(BST T);
void inOrder(BST T);
void postOrder(BST T);

int main(int argc, char* argv[]) {
	/*定义结点数量n和二叉排序树bst*/
	int n;
	BST bst;	

	/*向空二叉树T中插入n个结点*/
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int v;
		scanf("%d", &v);
		if (i != 0) {
			insert(bst, v);
		} else {
			/*利用第一个输入的值v初始化bst的根结点*/
			bst = (BST)malloc(sizeof(BSTNode));
			bst->left = NULL;
			bst->right = NULL;
			bst->value = v;
		}
	}

	/*先序遍历bst*/
	printf("preOrder  : ");
	preOrder(bst);
	printf("\n");

	/*中序遍历bst*/
	printf("inOrder   : ");
	inOrder(bst);
	printf("\n");
	
	/*后序遍历bst*/
	printf("postOrder : ");
	postOrder(bst);
	printf("\n");

	return 0;
}

void insert(BST T, int v) {
	/*二叉排序树上插入值为v的一个结点*/
	if (T != NULL) {
		if (T->value < v && T->right == NULL) {
			/*当前结点是合适的插入位置*/
			T->right = (BSTNode*)malloc(sizeof(BSTNode));
			T->right->value = v;
			T->right->left = NULL;
			T->right->right = NULL;
		} else if (T->value > v && T->left == NULL) {
			/*当前结点是合适的插入位置*/
			T->left = (BSTNode*)malloc(sizeof(BSTNode));
			T->left->value = v;
			T->left->left = NULL;
			T->left->right = NULL;
		} else if (T->value < v && T->right != NULL) {
			/*当前结点不是合适的插入位置,继续在右子树上寻找插入位置*/
			insert(T->right, v);
		} else if (T->value > v && T->left != NULL) {
			/*当前结点不是合适的插入位置,继续在右子树上寻找插入位置*/
			insert(T->left, v);
		}
	} 
}

void preOrder(BST T) {
	/*先序遍历BST*/
	if (T != NULL) {
		visit(T);
		preOrder(T->left);
		preOrder(T->right);
	}
}

void inOrder(BST T) {
	/*中序遍历BST*/
	if (T != NULL) {
		inOrder(T->left);
		visit(T);
		inOrder(T->right);
	}
}

void postOrder(BST T) {
	/*后序遍历BST*/
	if (T != NULL) {
		postOrder(T->left);
		postOrder(T->right);
		visit(T);
	}
}

void visit(BSTNode* node) {
	/*访问二叉排序树的某一个结点*/
	printf("%d ", node->value);
}

标签:Binary,Search,right,BSTNode,Tree,结点,value,NULL,left
From: https://www.cnblogs.com/gjsun/p/17737133.html

相关文章

  • G. wxhtzdy ORO Tree
    G.wxhtzdyOROTree前提知识:lca求最近公共祖先(倍增)因为或运算越多值就越大,好像跟上一个相反,所以满足单调不降要点1:利用数组来对每个点到其祖先节点的或和进行计算(倍增)要点2:分别对左右两边进行分析到lca点,这样确保无误要点3:因为满足单调不降,所以遇到大于的节点对左边才有意义......
  • qoj6735. Tree (The 1st Universal Cup. Stage 22: Shaanxi)
    https://qoj.ac/contest/1287/problem/6735考虑定一个根,然后把每个点的点权附属在父边权上,让每条边的边权变成一个pair。这样,一个符合条件的路径需要满足的条件是:路径内所有边的边权pair相同,以及路径根节点(lca)的颜色符合。对于当前树上每个边权相同的连通块分开考虑。对......
  • 根据一个数组,创建一个Segment Tree(线段树)
    线段树的特点线段树的优势线段树的构造过程(0,5)37:数组元素下标0~5的元素之和是37(0,2)21:数组元素下标0~2的元素之和是21线段树的基本数据结构(结点结构由五个分量组成)运行结果(C语言代码)递归的创建一颗线段树,然后中序、先序、后序遍历这个结点#include<stdio.h>#include<st......
  • 【UVA 536】Tree Recovery 题解(根据遍历序列还原二叉树)
    小瓦伦丁非常喜欢玩二叉树。她最喜欢的游戏是随机构建查找节点中带有大写字母的二叉树。这是她创作的一个例子:为了给后代记录她的树,她为每棵树写下了两个字符串:预订单遍历(根、左子树、右子树)和有序遍历(左子树、根、右子树。对于上面绘制的树,预序遍历是DBACEGF,有序遍历是ABCDEFG......
  • 上手ElasticSearch必须了解的核心概念
    ElasticSearch概述ElasticSearch(简称ES)是一个分布式的使用REST接口的搜索引擎,属于非关系型数据库。它是在lucene的基础上进行研发的,隐藏了lucene的复杂性,提供简单易用的RESTfulApi接口。ES的分片相当于lucene的索引。ES属于Elastic公司,该公司同时拥有Logstash及......
  • Merkle Tree 简介
    Merkle树(MerkleTree)是一种树状数据结构,通常用于验证大规模数据集的完整性和一致性。它的名字来源于其发明者RalphMerkle。Merkle树在密码学、分布式系统和区块链等领域得到广泛应用,尤其在区块链中,它用于验证交易和区块的完整性,确保数据不被篡改。下面是Merkle树的介绍:1.......
  • 逻辑树(LogicTree)和可视化树(VisualTree)
    遍历逻辑树和可视化树FrameworkElementLevel.(FrameworkElementType).(FrameworkElementName)[DataContextType]publicstaticclassTreeHelper{publicstaticstringgetTree(FrameworkElementcontainer){StringBuildersb=newStringBuilder();......
  • 基于vue制作搜索高亮popsearch组件
    ......
  • window下elasticsearch修改密码
    es默认是没有密码的,但是为了安全起见,线上正式环境还是要设置密码进入elasticsearch解压包目录中找到elasticsearch.YML文件,打开,直接在最后添加,这里记得,每个属性冒号后面都需要tab键一个空格xpack.security.enabled:truexpack.license.self_generated.type:basicxpack.security......
  • 在线直播系统源码,取CTreeCtrl控件选中节点的文字
    在线直播系统源码,取CTreeCtrl控件选中节点的文字 voidCAboutDlg::OnSelchangedTree1(NMHDR*pNMHDR,LRESULT*pResult) {NM_TREEVIEW*pNMTreeView=(NM_TREEVIEW*)pNMHDR;//TODO:Addyourcontrolnotificationhandlercodehere    MessageBox(m_tree1.GetIte......