数据结构-二叉查找树

使用双向链表实现一个二叉树的增加节点的操作，要求左子树的值小于根节点的值，右子树的值大于根节点的值。

/********************************************************************************************************
*
*
* 设计二叉树的接口
* 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 int  DataType_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;
}