careercup-树与图 4.6
2024-10-19 00:25:31
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);
else
insert(root->right,z);
} void createBST(BinarySearchTree *&root)
{
int arr[]= {,,,,,,,,,};
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);
}
最新文章
- java实现面向对象和javaScript基于对象的区别&;java垃圾回收机制和其他编程语言的比较
- 【转】android中ListView的定位:使用setSelectionFromTop实现ListView的position的保持
- maven插件
- Loadrunner,将http请求返回的中文结果打印出来
- ASP.NET MVC SSO单点登录设计与实现(转载)
- 统计学 nested_design 嵌套设计
- PowerDesigner建表
- MYI 文件内容
- Win7下Solr4.10.1和TomCat8的安装
- Storyboard中使用UIscrollView添加约束的开发总结
- Python3.6下scrapy框架的安装
- Messenger在MVVM模式中的应用
- FloatingActionButton FAB 悬浮按钮
- 关于LED效率,这4点你应该知道
- [Spring] Aspect Oriented Programming with Spring | AOP | 切面 | 切点
- VS插件VisualSVN v5.2.3.0 破解文件
- (C/C++学习笔记) 十二. 指针
- Git Bash主题配置
- java 实现输出姓和名
- PHP 字符串补0