4.6 設計一個算法，找出二叉查找樹中指定結點的“下一個”結點（也即中序后繼）。可以假定每個結點都含有指向父節點的連接。

思路：

有兩種情況：1）如果該結點存在右子樹，則中序后繼即為右子樹中最小的結點。

　　　　　　2）如果該結點不存在右子樹，則后繼結點為使得所給結點在其祖先結點的左子樹上的第一個祖先結點，因此一直找父節點，知道找到一個父節點使得該結點在左子樹上。

C++實現代碼：

#include<iostream> #include<new> using namespace std;struct BinarySearchTree {int elem;BinarySearchTree *parent;BinarySearchTree *left;BinarySearchTree *right;BinarySearchTree(int x):elem(x),parent(NULL),left(NULL),right(NULL) {} };void insert(BinarySearchTree *&root,int z) {BinarySearchTree *y=new BinarySearchTree(z);if(root==NULL){root=y;return;}else if(root->left==NULL&&z<root->elem){root->left=y;y->parent=root;return;}else if(root->right==NULL&&z>root->elem){root->right=y;y->parent=root;return;}if(z<root->elem)insert(root->left,z);elseinsert(root->right,z); }void createBST(BinarySearchTree *&root) {int arr[10]= {29,4,6,1,8,3,0,78,23,89};for(auto a:arr)insert(root,a); }void inorder(BinarySearchTree *root) {if(root){inorder(root->left);cout<<root->elem<<" ";inorder(root->right);} }BinarySearchTree* findMin(BinarySearchTree *root) {if(root==NULL||!root->left)return root;while(root->left){root=root->left;}return root; }BinarySearchTree* findMax(BinarySearchTree *root) {if(root==NULL||!root->right)return root;while(root->right){root=root->right;}return root; }BinarySearchTree* findProcessor(BinarySearchTree *root,BinarySearchTree* x) {if(x->left)return findMax(x->left);BinarySearchTree *y=x->parent;while(y&&y->left==x){x=y;y=x->parent;}return y; }BinarySearchTree* findSuccessor(BinarySearchTree *x) {if(x->right)return findMin(x->right);BinarySearchTree *y=x->parent;while(y&&y->right==x){x=y;y=x->parent;}return y; }int main() {BinarySearchTree *root=NULL;createBST(root);inorder(root); }

?

轉載于:https://www.cnblogs.com/wuchanming/p/4148139.html

總結

以上是生活随笔為你收集整理的careercup-树与图 4.6的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。