数据结构-二叉查找树

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

1. /********************************************************************************************************
2. *
3. *
4. * 设计二叉树的接口
5. * author：jindouliu2024@163.com
6. * date：2025.4.7
7. *
8. *
9. * Copyright (c)  2024-2025   jindouliu2024@163.com   All right Reserved
10. * ******************************************************************************************************/
12. #include<stdio.h>
13. #include <stdbool.h>
14. #include <stdlib.h>
15. #include"drawtree.h"
16. //指的是双向链表中的结点有效数据类型，用户可以根据需要进行修改
17. typedef int  DataType_t;
18. #if 0
19. //构造BSTree的结点,所有结点的数据类型应该是相同的
20. typedef struct BSTreeNode
21. {
22.         DataType_t                   data; //结点的数据域
23.         struct BSTreeNode        *lchild; //直接前驱的指针域
24.         struct BSTreeNode        *rchild; //直接后继的指针域
26. }BSTree_t;
28. #endif
29. //创建一个BSTree，应该有一个根结点，对根节点进行初始化
30. BSTnode_t * BSTree_Create(DataType_t data)
31. {
32.         //1.创建一个根结点并对根结点申请内存
33.         BSTnode_t *Root = (BSTnode_t *)calloc(1,sizeof(BSTnode_t));
34.         if (NULL == Root)
35.         {
36.                 perror("Calloc memory for Root is Failed");
37.                 exit(-1);
38.         }
40.         //2.对根结点进行初始化
41.         Root->data = data;
42.         Root->lchild = NULL;
43.         Root->rchild = NULL;
45.         //3.把根结点的地址返回即可
46.         return Root;
47. }
49. //创建新的节点，并对新节点进行初始化（数据域 + 指针域）
52. BSTnode_t * BSTree_NewNode(DataType_t data)
53. {
54.         //1.创建一个新结点并对新结点申请内存
55.         BSTnode_t *New = (BSTnode_t *)calloc(1,sizeof(BSTnode_t));
56.         if (NULL == New)
57.         {
58.                 perror("Calloc memory for NewNode is Failed");
59.                 return NULL;
60.         }
62.         //2.对新结点的数据域和指针域（2个）进行初始化
63.         New->data = data;
64.         New->lchild = NULL;
65.         New->rchild = NULL;
67.         return New;
68. }
69. //插入节点，比根节点小的放在左子树，比根节点大的放在右子树
70. bool BSTree_InsertNode(BSTnode_t * Root,DataType_t data)
71. {
72.         BSTnode_t *Proot = Root;
73.         //创建新节点
74.         BSTnode_t * New= BSTree_NewNode(data);
75.         //判断新节点创建是否成功
76.         if(NULL == New){
77.                 printf("BSTree create new node failed,do not join in \n ");
78.                 return false;
79.         }
80.         //根节点为空时，把新结点作为根节点
81.         if(Root == NULL){
82.                 Root = New;
83.         }
84.         //根节点不为空时
85.         else{
86.                 while(Proot){
87.                         if(New->data == Proot->data){
88.                                 printf("this value is exit,do not join in\n");
89.                                 return false;
90.                         }
91.                         else{
92.                                 if(New->data < Proot->data){
93.                                         if(Proot->lchild == NULL){
94.                                                 Proot->lchild = New;
95.                                                 break;
96.                                         }
98.                                         Proot = Proot->lchild;
99.                                 }
100.                                 else{
101.                                         if(Proot->rchild == NULL){
102.                                                 Proot->rchild = New;
103.                                                 break;
104.                                         }
105.                                         Proot = Proot->rchild;
107.                                 }
108.                         }
109.                 }
110.                
111.         }
112.         return true;
113. }
116. int BSTree_CalNode(BSTnode_t * Root)
117. {
118.         int cnt = 0;
119.         BSTnode_t *Proot = Root;
120.         while(Proot){
121.                 if(Proot->lchild){
122.                         cnt++;
123.                         Proot = Proot->lchild;
124.                 }
125.         }
126. }
128. int main(int argc, char const *argv[])
129. {
130.         //创建一个根结点
131.         BSTnode_t *p = BSTree_Create(10);
132.         BSTree_InsertNode(p,5);
133.         BSTree_InsertNode(p,19);
134.         BSTree_InsertNode(p,7);
135.         BSTree_InsertNode(p,13);
136.         BSTree_InsertNode(p,8);
137.         BSTree_InsertNode(p,4);
138.         BSTree_InsertNode(p,23);
139.         BSTree_InsertNode(p,11);
140.         draw(p);
141.         return 0;
142. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！