知识卡片
树节点插入只占未用孩子位置
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),因为插入操作的所有步骤都能在恒定的时间内完成。