当前位置：首页 > news >正文

C-数据结构-树状存储的基本实现

news 2025/7/19 0:40:27

/*
理解和记忆递归的关键在于把握递归的本质和函数调用的过程。递归函数在每次调用时会把当前状态压入调用栈，直到满足终止条件后开始回溯。理解基准条件和递归步骤：每个递归函数都需要有基准条件（如节点为空时返回），并在每一步中递归调用自身处理子问题。

*/
main.c

#include<stdio.h>
#include<stdlib.h>#define NAMESIZE	32struct score_st
{int id;char name[NAMESIZE];int math;int chinese;
};struct node_st
{struct score_st data;struct node_st *l,*r;
};print_s(struct score_st *d)
{printf("%d %s %d %d\n",d->id,d->d.name,d->math,d->chinese);
}int insert(struct node_st **root,struct score_st *data)
{struct node_st *node;if(*root == NULL){node = malloc(sizeof(*node));if(node == NULL)return -1;node->data = *data;node->l = NULL;node->r = NULL;*root = node;return 0;}if(data->id <= (*root)->data.id)return insert(&(*root)->l,data);elsereturn insert(&(*root)->r,data);
}
struct score_st *find(struct node_st *root,int id)
{if(root == NULL)return NULL;if(id == root->data.id)return &root->data;if(id < root->data.id)return find(root->l,id);elsereturn find(root->r,id);
}
void draw_(struct node_st *root,in level)
{int i;if(root == NULL)return ;draw_(root->t,level+1);for(i = 0;i<level;i++)printf("    ");print_s(&root->data);draw_(root->l,level+1);
}
void draw(struct node_st *root)
{draw_(root,0);
}int main()
{int arr[] = {1,2,3,7,6,5,9,8,4};int i;struct score_st tmp,*datap;struct node_st *tree = NULL;for(i = 0;i<sizeof(arr)/sizeof(*arr);i++){tmp.id = arr[i];snprintf(tmp.name,NAMESIZE,"stu%d",arr[i]);tmp.math = rand()%100;tmp.chinese = rand()%100;insert(&tree,&tmp);}draw(tree);#if 0int tmpid = 2;datap = find(tree,tmpid);if(datap == NULL)printf("can not find the id %d\n",tmpid);elseprint_s(datap);
#endifexit(0);
}

补充说明1

为了理解二级指针的一级目标，我们需要明确指针和二级指针的概念。

指针和二级指针

指针：一个指针变量保存了另一个变量的地址。通过指针，我们可以访问或修改这个变量的值。例如，int *p 是一个指向整数的指针变量。
二级指针：一个二级指针变量保存了另一个指针变量的地址。通过二级指针，我们可以访问或修改这个指针变量的值。例如，int **pp 是一个指向指针变量的指针。

二级指针的一级目标

一级目标是指二级指针所指向的那个指针变量。

举个具体的例子，假设我们有以下定义：

int a = 10;       // 普通变量
int *p = &a;      // 指向变量 a 的指针
int **pp = &p;    // 指向指针 p 的指针

在这个例子中：

p 是一个指向 a 的指针。
pp 是一个指向 p 的指针。

我们可以这样理解：

pp 保存了 p 的地址。
*pp 解析出 pp 所指向的内容，即 p。
**pp 解析出 *pp 所指向的内容，即 a 的值。
当然可以！以下是一个图形示例来说明 *aa = b 的含义：

假设：

aa 是一个指向指针的指针。
a 是一个指针，它最初指向一个地址。
b 是另一个指针，指向另一个地址。

初始状态：

+------+    +------+    +------+
|  aa  | -> |  a   | -> |  x   |  (假设 x 是 a 所指向的值)
+------+    +------+    +------++------+    +------+
|  b   | -> |  y   |  (假设 y 是 b 所指向的值)
+------+    +------+

执行 *aa = b 后的状态：

+------+    +------+
|  aa  | -> |  b   | -> |  y   |  (aa 现在指向 b，而 b 仍然指向 y)
+------+    +------+

这样做后，aa 所指向的指针 a 不再指向原来的地址，而是指向了 b 所指向的地址。

以下是更详细的图示：

初始状态：

aa -> a -> [地址1: x]
b -> [地址2: y]

执行 *aa = b 后：

aa -> b -> [地址2: y]

这意味着，aa 原本指向的指针 a，现在指向了 b，即 a 的地址已经被 b 的地址覆盖。

希望这个图形示例能帮助你更好地理解 *aa = b 的含义。如果还有其他问题，请随时告诉我！

补充说明2

你提到的情况是正确的。A 不出栈的原因是递归调用还没有完成。为了更清楚地解释递归调用的过程，让我们重新逐步分析每一个递归调用和返回的过程，并使用栈来跟踪函数调用。

示例二叉树

假设有如下二叉树：

      A/ \B   C/ \D   E

使用栈模拟执行过程

我们以栈的方式逐步模拟 draw 函数调用 draw_ 的过程。

初始状态：
- 栈为空。
- 调用 draw(root)，进入 draw_(root, 0)。
处理根节点 A：
- 调用 draw_(A, 0)。
- 栈：[ draw_(A, 0) ]
递归处理右子树 C：
- 调用 draw_(C, 1)。
- 栈：[ draw_(A, 0), draw_(C, 1) ]
处理 C 节点：
- 右子树为空，返回。
- 打印 C（缩进 4 空格）。
- 左子树为空，返回。
- 返回 draw_(A, 0)。
- 栈：[ draw_(A, 0) ]
输出：
```
    C
```
打印根节点 A：
- 打印 A（无缩进）。
- 栈：[ draw_(A, 0) ]
输出：
```
    C
A
```
递归处理左子树 B：
- 调用 draw_(B, 1)。
- 栈：[ draw_(A, 0), draw_(B, 1) ]
处理 B 节点：
- 调用 draw_(E, 2)（递归处理右子树）。
- 栈：[ draw_(A, 0), draw_(B, 1), draw_(E, 2) ]
处理 E 节点：
- 右子树为空，返回。
- 打印 E（缩进 8 空格）。
- 左子树为空，返回。
- 返回 draw_(B, 1)。
- 栈：[ draw_(A, 0), draw_(B, 1) ]
输出：
```
    C
AE
```
打印 B 节点：
- 打印 B（缩进 4 空格）。
- 栈：[ draw_(A, 0), draw_(B, 1) ]
输出：
```
    C
AEB
```
递归处理左子树 D：
- 调用 draw_(D, 2)。
- 栈：[ draw_(A, 0), draw_(B, 1), draw_(D, 2) ]
处理 D 节点：
- 右子树为空，返回。
- 打印 D（缩进 8 空格）。
- 左子树为空，返回。
- 返回 draw_(B, 1)。
- 栈：[ draw_(A, 0), draw_(B, 1) ]
输出：