c - 如何创建指向二叉树节点的链表?
问题描述
我有一个创建二叉树的函数,对于树中的每个节点,我需要将一个节点添加到一个单独的链表中,该链表指向二叉树中的节点。
我创建二叉树的功能:
typedef struct myTree _node;
void INSERT(_node *(*tree), _node *item) {
if (!(*tree)) {
*tree = item;
return;
}
if (item->val < (*tree)->val) {
INSERT(&(*tree)->left, item);
}
else if (item->val > (*tree)->val) {
INSERT(&(*tree)->right);
}
}
我的主要功能:
int main(void) {
int i;
int *balanced;
_node *current, *root;
root = NULL;
for (i = 0; i < size; i++) {
current = (_node *)malloc(sizeof(_node));
current->left = current->right = NULL;
current->val = balanced[i];
INSERT(&root, current);
}
return 0;
}
为简单起见,我省略了部分主要功能。
我的想法是我想以pre,in和post顺序打印出树的内容,以及遍历链表并打印每个链表节点指向的树中节点的值。
我只有几个月的时间学习 C,所以我不是很先进。
解决方案
就像您的插入函数在树上递归一样,遍历树也是递归的。有两种方法可以做到这一点:特定方式和通用方式。让我们看看两者。
具体方式只是在遇到值时打印它们。它解决了这个特定问题:打印值。如果您必须进行树遍历来做不止一件事,则必须复制代码,这通常是一件坏事。
另一方面,代码更简单,更容易理解。让我们看一下有序的情况(其他两个你可以自己做;它们非常相似):
void print_in_order (const struct myTree * tree) {
// if we're in a null node, do nothing
if (!tree) return;
// otherwise, do the left subtree, then the current node, then the right subtree
// non-existent subtrees will be handled by the above check, so don't check twice
print_in_order(tree -> left);
printf("%d\n", tree -> val);
print_in_order(tree -> right);
}
另一方面,如果您的程序出于各种目的进行树遍历,则通用方法是一种更好的方法。这个想法是您将要在每个节点上完成的实际任务(在这种情况下,打印它)封装在一个单独的函数中:
void print_node (const struct myTree * node) {
printf("%d\n", node -> val);
}
然后编写一个函数,将该函数作为参数,并在每个节点上按照相应的顺序调用它。让我们按顺序进行:
void apply_in_order (const struct myTree * tree,
void (* callback)(const struct myTree *)) {
// this is the same as before...
if (!tree) return;
apply_in_order(tree -> left, callback);
// ...except that, instead of doing a specific thing, we call the callback on each node
callback(tree);
apply_in_order(tree -> right, callback);
}
现在,您只需调用此函数 asapply_in_order(tree, print_node);
并获得与上述相同的行为。但是下次你需要编写一个遍历树的函数时,你只需要每个节点的东西;其余的已经完成。
推荐阅读
- html - Wrap a sentence into 3 rows at an exact point in a sentence
- sql-server - 如何从中提取“stackoverflow.com”?
- powershell - 如何在PowerShell输出中打印文件夹和文件名
- python - wide_to_long Valueerror : id 变量需要唯一标识每一行
- javascript - 为什么反应 i18next 不起作用?没有错误
- java - 在 Java 中面临迟到、不足和总小时数的问题
- javascript - 如何防止表单条带验证
- python - 运行时错误 - 远期汇率计算
- html - 居中无间隙的图像和文本
- jboss - 无法访问 ear 子部署中的 .ear/lib jar