知识卡片

结构图卡 · 5654.d.1.e.4.i · 生成模型:未记录

二叉树分开保存节点与根状态

理解等级:中级

本章BiTreeNode保存应用数据地址和左右孩子指针;BiTree容器保存节点总数、数据清理回调与根。compare预留给后续搜索结构,基本树操作不使用它。

结构图:

classDiagram
class BiTreeNode {
 void* data
 BiTreeNode* left
 BiTreeNode* right
}
class BiTree {
 int size
 int (*compare)(const void* a, const void* b)
 void (*destroy)(void* data)
 BiTreeNode* root
}
class TreeAPI["二叉树公开函数组(非类型)"] {
 bitree_init(BiTree* tree, destroy) void
 bitree_destroy(BiTree* tree) void
 bitree_ins_left(BiTree* tree, BiTreeNode* node, const void* data) int
 bitree_ins_right(BiTree* tree, BiTreeNode* node, const void* data) int
 bitree_rem_left(BiTree* tree, BiTreeNode* node) void
 bitree_rem_right(BiTree* tree, BiTreeNode* node) void
 bitree_merge(BiTree* out, BiTree* left, BiTree* right, const void* data) int
}
BiTree --> BiTreeNode : root
BiTreeNode --> BiTreeNode : left与right
TreeAPI ..> BiTree : 维护链接及size

init中的destroy按字段同型函数指针简写;本图不表示compare已经在init初始化,也没有从节点到父亲的隐含指针。

149及02856 bitree_init只写size=0、destroy=回调、root=NULL,不初始化compare。不得把这棵基本树直接当已具备有效比较策略的搜索树,也不能用init覆盖仍有节点的旧树当作资源清理。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      结构体BiTreeNode代表二叉树中的一个单独结点(见示例9-1)。如你所料,这个结构体由上面刚提到的3个成员组成。结构体BiTree代表二叉树这种数据结构(见示例9-1)。这个结构体包含4个成员:size表示树中结点的个数,compare成员在二叉树中暂时不会用到,而是等到其他数据类型继承自二叉

    • · 查看原书依据

      root成员置为NULL即可。 bitree_init的时间复杂度为O(1)级别的,因为初始化过程中的所有步骤都能够在恒定时间内完成。

    参考来源

    - 位置:《算法精解:C语言描述》第9章《二叉树的实现与分析》(spine1288;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1255.html;u148-ch09-010)。 - 结论依据:148完整正文与02854–02855全部bitree.h实读,BiTreeNode三字段、BiTree四字段与全部函数签名逐项核对,符合实际C结构关系。 - 原始内容:结构体BiTreeNode代表二叉树中的一个单独结点(见示例9-1)。如你所料,这个结构体由上面刚提到的3个成员组成。结构体BiTree代表二叉树这种数据结构(见示例9-1)。这个结构体包含4个成员:size表示树中结点的个数,compare成员在二叉树中暂时不会用到,而是等到其他数据类型继承自二叉 - 位置:《算法精解:C语言描述》第9章《bitree_init》(spine1288;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1255.html;u149-ch09-010)。 - 结论依据:149及02856 bitree_init只写size=0、destroy=回调、root=NULL,不初始化compare。不得把这棵基本树直接当已具备有效比较策略的搜索树,也不能用init覆盖仍有节点的旧树当作资源清理。 - 原始内容:root成员置为NULL即可。 bitree_init的时间复杂度为O(1)级别的,因为初始化过程中的所有步骤都能够在恒定时间内完成。