二叉搜索树-创新互联
文章目录
创新互联是一家专注于成都网站设计、成都网站建设、外贸网站建设与策划设计,汾西网站建设哪家好?创新互联做网站,专注于网站建设十载,网设计领域的专业建站公司;建站业务涵盖:汾西等地区。汾西做网站价格咨询: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://pwwzsj.com/article/jpesd.html