2021-10-11 寻找二叉树结点的前驱或后继结点（用到parent指针）

关键是找前驱后继的思想理解了就好

//! 查找某个结点的前驱或后继结点（要求结点要有parent指针） //! 前驱结点定义：中序遍历中的前一个结点，而不是二叉树结构中的上一个母结点 Node *BinarySearchTreesZH::predecessor(Node *node) {if (node == nullptr){return node;}//! 前驱结点是左子树中的最右结点if (node->left != nullptr){node = node->left;while (node->right != nullptr){node = node->right;}return node;}else{while (node->parent != nullptr && node->parent->right != node){node = node->parent;}//! 此时到这里有两种可能//! node->parent = nullptr(即没有前驱结点) 或 node->parent ->right = node（即前驱结点是node->parent）//! 无论哪种 直接返回parent都可以return node->parent;} } //! 查找某个结点的后继结点（要求结点要有parent指针） //! 后继结点定义：中序遍历中的后一个结点 Node *BinarySearchTreesZH::successor(Node *node) {if (node == nullptr){return node;}//! 前驱结点是右子树中的最左结点if (node->right != nullptr){node = node->right;while (node->left != nullptr){node = node->left;}return node;}else{while (node->parent != nullptr && node->parent->left != node){node = node->left;}//! 此时到这里有两种可能//! node->parent = nullptr(即没有前驱结点) 或 node->parent ->left = node（即前驱结点是node->parent）//! 无论哪种 直接返回parent都可以return node->parent;} }

总结

以上是生活随笔为你收集整理的2021-10-11 寻找二叉树结点的前驱或后继结点（用到parent指针）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。