知识卡片

操作参考卡 · 5654.d.1.e.4.f · 生成模型:未记录

树节点插入只占未用孩子位置

理解等级:中级

bitree_ins_left(BiTree,BiTreeNode,const void*)和右侧版本在已知节点的空孩子位置新增一个叶子。对应孩子已存在则-1;node为NULL时只允许空树创建根,否则-1。分配成功并连入后size增一并返回0。

新节点保存data地址,左右孩子置NULL,不深复制数据,也不自动按值寻找插入位置。这是基本二叉树的定位后插入,不是二叉搜索树的比较查找。操作不提供把新节点塞到已有父子之间并自动重接整棵子树的能力;调用方需保证所给节点属于正确树且仍有效。

151与02856–02857 bitree_ins_left在node=NULL且空树时position=&root,否则要求left为空并position=&node->left。malloc失败返回-1而未改链接;成功先填data/left/right,再*position=new_node、size++、return0。

152与02857完整bitree_ins_right:node=NULL时只空树可插根,非NULL时要求right为空;position通过正确else选择。节点两孩子初始化NULL,成功再增加size,不自动执行键比较或旋转。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      bitree_ins_left 返回值 如果插入操作成功,返回0;否则返回-1。 描述 在tree所指定的二叉树中插入一个结点,使其成为node所指定结点的左子结点。如果node已经有一个左子结点,则bitree_ins_left返回-1。如果node为NULL,则新结点作为根结点插入。插入根结点时

    • · 查看原书依据

      root成员设置为新的结点使其成为根结点。最后更新size成员使其加1。 bitree_ins_left的时间复杂度为O(1),因为把结点插入二叉树中的所有步骤都能够在恒定的时间内完成。

    • · 查看原书依据

      right指针指向待插入的新结点。 bitree_ins_right的时间复杂度为O(1),因为插入操作的所有步骤都能在恒定的时间内完成。

    参考来源

    - 位置:《算法精解:C语言描述》第9章《二叉树的接口定义》(spine1287;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1254.html;u147-ch09-007)。 - 结论依据:147左右插入完整说明、02842–02843原型及02856–02857全部插入实现实读;函数不验证所属树边界明确,未执行。 - 原始内容:bitree_ins_left 返回值 如果插入操作成功,返回0;否则返回-1。 描述 在tree所指定的二叉树中插入一个结点,使其成为node所指定结点的左子结点。如果node已经有一个左子结点,则bitree_ins_left返回-1。如果node为NULL,则新结点作为根结点插入。插入根结点时 - 位置:《算法精解:C语言描述》第9章《bitree_ins_left》(spine1290;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1257.html;u151-ch09-007)。 - 结论依据:151与02856–02857 bitree_ins_left在node=NULL且空树时position=&root,否则要求left为空并position=&node->left。malloc失败返回-1而未改链接;成功先填data/left/right,再*position=new_node、size++、return0。 - 原始内容:root成员设置为新的结点使其成为根结点。最后更新size成员使其加1。 bitree_ins_left的时间复杂度为O(1),因为把结点插入二叉树中的所有步骤都能够在恒定的时间内完成。 - 位置:《算法精解:C语言描述》第9章《bitree_ins_right》(spine1291;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1258.html;u152-ch09-007)。 - 结论依据:152与02857完整bitree_ins_right:node=NULL时只空树可插根,非NULL时要求right为空;position通过正确else选择。节点两孩子初始化NULL,成功再增加size,不自动执行键比较或旋转。 - 原始内容:right指针指向待插入的新结点。 bitree_ins_right的时间复杂度为O(1),因为插入操作的所有步骤都能在恒定的时间内完成。