数据结构-二叉查找树
使用双向链表实现一个二叉树的增加节点的操作，要求左子树的值小于根节点的值，右子树的值大于根节点的值。/********************************************************************************************************
*
*
* 设计二叉树的接口
* author：jindouliu2024@163.com
* date：2025.4.7
*
*
* Copyright (c)2024-2025 jindouliu2024@163.com All right Reserved
* ******************************************************************************************************/
#include<stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include"drawtree.h"
//指的是双向链表中的结点有效数据类型，用户可以根据需要进行修改
typedef intDataType_t;
#if 0
//构造BSTree的结点,所有结点的数据类型应该是相同的
typedef struct BSTreeNode
{
DataType_t data; //结点的数据域
struct BSTreeNode *lchild; //直接前驱的指针域
struct BSTreeNode *rchild; //直接后继的指针域
}BSTree_t;
#endif
//创建一个BSTree，应该有一个根结点，对根节点进行初始化
BSTnode_t * BSTree_Create(DataType_t data)
{
//1.创建一个根结点并对根结点申请内存
BSTnode_t *Root = (BSTnode_t *)calloc(1,sizeof(BSTnode_t));
if (NULL == Root)
{
perror("Calloc memory for Root is Failed");
exit(-1);
}
//2.对根结点进行初始化
Root->data = data;
Root->lchild = NULL;
Root->rchild = NULL;
//3.把根结点的地址返回即可
return Root;
}
//创建新的节点，并对新节点进行初始化（数据域 + 指针域）
BSTnode_t * BSTree_NewNode(DataType_t data)
{
//1.创建一个新结点并对新结点申请内存
BSTnode_t *New = (BSTnode_t *)calloc(1,sizeof(BSTnode_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
//2.对新结点的数据域和指针域（2个）进行初始化
New->data = data;
New->lchild = NULL;
New->rchild = NULL;
return New;
}
//插入节点，比根节点小的放在左子树，比根节点大的放在右子树
bool BSTree_InsertNode(BSTnode_t * Root,DataType_t data)
{
BSTnode_t *Proot = Root;
//创建新节点
BSTnode_t * New= BSTree_NewNode(data);
//判断新节点创建是否成功
if(NULL == New){
printf("BSTree create new node failed,do not join in \n ");
return false;
}
//根节点为空时，把新结点作为根节点
if(Root == NULL){
Root = New;
}
//根节点不为空时
else{
while(Proot){
if(New->data == Proot->data){
printf("this value is exit,do not join in\n");
return false;
}
else{
if(New->data < Proot->data){
if(Proot->lchild == NULL){
Proot->lchild = New;
break;
}
Proot = Proot->lchild;
}
else{
if(Proot->rchild == NULL){
Proot->rchild = New;
break;
}
Proot = Proot->rchild;
}
}
}
}
return true;
}
int BSTree_CalNode(BSTnode_t * Root)
{
int cnt = 0;
BSTnode_t *Proot = Root;
while(Proot){
if(Proot->lchild){
cnt++;
Proot = Proot->lchild;
}
}
}
int main(int argc, char const *argv[])
{
//创建一个根结点
BSTnode_t *p = BSTree_Create(10);
BSTree_InsertNode(p,5);
BSTree_InsertNode(p,19);
BSTree_InsertNode(p,7);
BSTree_InsertNode(p,13);
BSTree_InsertNode(p,8);
BSTree_InsertNode(p,4);
BSTree_InsertNode(p,23);
BSTree_InsertNode(p,11);
draw(p);
return 0;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]