二叉搜索树-创新互联

文章目录

创新互联是一家专注于成都网站设计、成都网站建设、外贸网站建设与策划设计,汾西网站建设哪家好?创新互联做网站,专注于网站建设十载,网设计领域的专业建站公司;建站业务涵盖:汾西等地区。汾西做网站价格咨询:13518219792

二叉搜索树

规律：

下面实现一个二叉搜索树：

先给定一个数组里面存入数据，然后用其中数据创建一个树，最后将其中数据按中序遍历打印

一、思路

二、具体接口函数

1.数据

2.声明二叉搜索树的节点 

3.创建二叉搜索树的节点

4.声明二叉搜索树

5.创建二叉搜索树

6.插入节点

7.打印树的节点

8.打印树

9.主函数

结果：

总结

---

二叉搜索树 规律： 1、每一个节点带有数据和一个关键字 2、如果插入节点比当前节点关键字大，则放在当前节点右边，反之放左边 3、二叉搜索树的任意一个子树仍是二叉搜索树 

---

下面实现一个二叉搜索树：

先给定一个数组里面存入数据，然后用其中数据创建一个树，最后将其中数据按中序遍历打印

一、思路

二、具体接口函数 1.数据

// 封装数据：数据需要关键字
typedef struct data
{
	int first;		// 关键字
	char second[20];// 数据
}DATA,*LPDATA;

2.声明二叉搜索树的节点 

typedef struct binaryTreeNode
{
	DATA element; // 元素/数据
	struct binaryTreeNode* LChild; // 左子树
	struct binaryTreeNode* RChild; // 右子树
}NODE, * LPNODE;

3.创建二叉搜索树的节点

LPNODE createNode1(DATA data) // 上面typedef了是*LPNODE，所以直接返回值是LPNODE
{
	LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
	// 下面相当于初始化
	newNode->element = data;
	newNode->LChild = newNode->RChild = NULL;
	return newNode;
}
// 或者：
NODE* createNode2(DATA data)	// 上面typedef了是NODE，所以返回值是NODE*
{
	NODE* newNode = (NODE*)malloc(sizeof(NODE));
	newNode->element = data;
	newNode->LChild = newNode->RChild = NULL;
	return newNode;
}

4.声明二叉搜索树

typedef struct binarySearchTree
{
	struct binaryTreeNode* root; // 节点的指针表示整棵树 - 根节点
	int treeSize;
}BTREE,*LPBTREE;

5.创建二叉搜索树

LPBTREE createbinarySearchTree1()
{
	// 创建 + 置空，相当于初始化
	LPBTREE tree = (LPBTREE)malloc(sizeof(BTREE));
	tree->root = NULL;	
	tree->treeSize = 0;
	return tree;
}

6.插入节点

void insertNode(LPBTREE tree, DATA data)
{
	LPNODE moveNode = tree->root;
	LPNODE moveParentNode = NULL;
	while (moveNode!=NULL) // 找要插入的位置，当为NULL时表示找到
	{
		moveParentNode = moveNode;
		if (data.first< moveNode->element.first) // 新数据< 树里的原数据
		{
			moveNode = moveNode->LChild;
		}
		else if (data.first >moveNode->element.first)// 新数据 >树里的原数据
		{
			moveNode = moveNode->RChild;
		}
		else // 当要比较的数据和原数据相同，则将新数据覆盖进去
		{	// 由于我们写的是char类型的数据，所以要用字符串比较strcpy
			strcpy(moveNode->element.second, data.second);
			return;
		}
	}
	// 找到NULL后，开始插入，首先先创建节点
	NODE* newNode = createNode2(data);
	// 插入位置：移动节点的父节点（即NULL的上一个节点）
	if (tree->root == NULL)
	{ // 根节点为空，则新节点直接作为根节点
		tree->root = newNode;
	}
	else
	{
		if (moveParentNode->element.first >data.first)
		{	// 父节点的数据>新节点，将新节点插在父节点的左边
			moveParentNode->LChild = newNode;
		}
		else
		{	// 反之右边
			moveParentNode->RChild = newNode;
		}
	}
}

下面采用中序遍历的方法测试 7.打印树的节点

void printTree(LPNODE root)
{	
	if (root != NULL)
	{
		printTree(root->LChild);
		printf("%d\t%s\n", root->element.first, root->element.second);
		printTree(root->RChild);
	}
}	

8.打印树

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

不能二者连在一起用

9.主函数

int main()
{    
    // 创建数组
	DATA arr[7] = { 100,"张山",50,"里斯",180,"王五",40,"陈留",
                     55,"邦奇",190,"KAN",175,"chen" };
	BTREE* tree = createbinarySearchTree2();// 创建树
	for(int i=0;i<7;i++)
	{
		insertNode(tree, arr[i]); // 连接树
	}
	printSearchTree(tree);// 打印树
	return 0; 
}

结果：

---

总结

二叉搜索树的基本实现

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章标题：二叉搜索树-创新互联
文章出自：http://cdkjz.cn/article/jpesd.html