careercup-树与图 4.6

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的全部内容，希望文章能够帮你解决所遇到的问题。

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