關(guān)鍵是找前驅(qū)后繼的思想理解了就好

//! 查找某個結(jié)點的前驅(qū)或后繼結(jié)點（要求結(jié)點要有parent指針） //! 前驅(qū)結(jié)點定義：中序遍歷中的前一個結(jié)點，而不是二叉樹結(jié)構(gòu)中的上一個母結(jié)點 Node *BinarySearchTreesZH::predecessor(Node *node) {if (node == nullptr){return node;}//! 前驅(qū)結(jié)點是左子樹中的最右結(jié)點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(即沒有前驅(qū)結(jié)點) 或 node->parent ->right = node（即前驅(qū)結(jié)點是node->parent）//! 無論哪種 直接返回parent都可以return node->parent;} } //! 查找某個結(jié)點的后繼結(jié)點（要求結(jié)點要有parent指針） //! 后繼結(jié)點定義：中序遍歷中的后一個結(jié)點 Node *BinarySearchTreesZH::successor(Node *node) {if (node == nullptr){return node;}//! 前驅(qū)結(jié)點是右子樹中的最左結(jié)點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(即沒有前驅(qū)結(jié)點) 或 node->parent ->left = node（即前驅(qū)結(jié)點是node->parent）//! 無論哪種 直接返回parent都可以return node->parent;} }

總結(jié)

以上是生活随笔為你收集整理的2021-10-11 寻找二叉树结点的前驱或后继结点（用到parent指针）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。