package datastructure;
public class SearchTree {
public static void main(String args[]){
SearchTree tree=new SearchTree();
tree.inOrderTreeWalk();
}
private TreeNode root;
public SearchTree(){
TreeNode t15=new TreeNode(15);
TreeNode t6=new TreeNode(6);
TreeNode t18=new TreeNode(18);
TreeNode t3=new TreeNode(3);
TreeNode t7=new TreeNode(7);
TreeNode t17=new TreeNode(17);
TreeNode t20=new TreeNode(20);
TreeNode t2=new TreeNode(2);
TreeNode t4=new TreeNode(4);
TreeNode t13=new TreeNode(13);
TreeNode t9=new TreeNode(9);
this.root=t15;
t15.left=t6;
t6.p=t15;
t15.right=t18;
t18.p=t15;
t6.left=t3;
t3.p=t6;
t6.right=t7;
t7.p=t6;
t18.left=t17;
t17.p=t18;
t18.right=t20;
t20.p=t18;
t3.left=t2;
t2.p=t3;
t3.right=t4;
t4.p=t3;
t7.right=t13;
t13.p=t7;
t13.left=t9;
t9.p=t13;
}
public void inOrderTreeWalk(){
inOrderTreeWalk(this.root);
}
public void inOrderTreeWalk(TreeNode x){
if(x!=null){
inOrderTreeWalk(x.left);
System.out.println(x.key);
inOrderTreeWalk(x.right);
}
}
public TreeNode recursiveTreeSearch(int k){
return recursiveTreeSearch(this.root,k);
}
public TreeNode recursiveTreeSearch(TreeNode x,int k){
if(x==null || k==x.key)
return x;
if(k<x.key)
return recursiveTreeSearch(x.left,k);
else
return recursiveTreeSearch(x.right,k);
}
public TreeNode iterativeTreeSearch(int k){
return iterativeTreeSearch(this.root,k);
}
public TreeNode iterativeTreeSearch(TreeNode x,int k){
while(x!=null && k!=x.key){
if(k<x.key)
x=x.left;
else
x=x.right;
}
return x;
}
public TreeNode minimum(){
return minimum(this.root);
}
public TreeNode minimum(TreeNode x){
while(x.left!=null)
x=x.left;
return x;
}
public TreeNode maxmum(){
return maxmum(this.root);
}
public TreeNode maxmum(TreeNode x){
while(x.right!=null)
x=x.right;
return x;
}
public TreeNode treeSuccessor(TreeNode x){
if(x.right!=null)
return minimum(x.right);
TreeNode y=x.p;
while(y!=null && x==y.right){
x=y;
y=y.p;
}
return y;
}
public void treeInsert(TreeNode z){
TreeNode y=null;
TreeNode x=this.root;
while(x!=null){
y=x;
if(z.key<x.key)
x=x.left;
else
x=x.right;
}
z.p=y;
if(y==null){
this.root=z;
}
else{
if(z.key<y.key)
y.left=z;
else
y.right=z;
}
}
public TreeNode treeDelete(TreeNode z){
TreeNode y,x;
if(z.left==null || z.right==null){
y=z;
}
else{
y=treeSuccessor(z);
}
if(y.left!=null){
x=y.left;
}
else
x=y.right;
if(x!=null)
x.p=y.p;
if(y.p==null){
this.root=x;
}
else if(y==y.p.left){
y.p.left=x;
}
else{
y.p.right=x;
}
if (y!=z){
z.key=y.key;
}
return y;
}
}
class TreeNode{
public int key;
public TreeNode p;
public TreeNode left;
public TreeNode right;
public TreeNode(int key){
this.key=key;
}
public TreeNode(int key,TreeNode p,TreeNode left,TreeNode right){
this.key=key;
this.p=p;
this.left=left;
this.right=right;
}
}
分享到:
相关推荐
主要介绍了一个c语言版的二叉查找树实现,二叉查找树,支持的操作包括:SERACH、MINIMUM、MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT、DELETE,大家参考使用吧
给定一个二叉搜索树和其中的一个节点,在 BST 中找到该节点的有序后继。 节点 p 的后继是最小键大于 p.val 的节点。 笔记: 如果给定节点在树中没有有序后继,则返回 null。 保证树的值是唯一的。 执行 : /** * ...
详细的红黑树C++模板实现,调试后运行正确。 template class RBTree { private: static node<T> *nil;//哨兵,静态成员,被整个RBTree类所共有 node<T> *root; RBTree(const RBTree&);//禁止复制构造 RBTree ...
后继ML 继任者ML致力于发展标准ML语言,同时又保持其简洁优雅的设计。 相关的工作是。 请注意,该存储库曾经被称为Proposed-Definition-of-Successor-ML ,但已重命名为Successor-ML 。 Github将自动重定向旧的URL,...
不错的查找速度,较灵活的插入和删除 开放寻址法散列表 theta(1/(1-alpha)) 优秀的查找速度,对删除操作支持不好 完全散列 theta(1) 极好的查找速度,建表慢,一旦建好,不支持对表结构改变 树 普通二叉树 search, ...
Handler后面的successor表示的是由一条链组成,并且持有自己的...首先我们需要定义一个接口,之后的处理人都要实现这个接口,因为是个链表,使用我们要指定后继,因为Java的多态所以我们只需要使用PriceHandler就好了。
根据本文的参数训练后继不确定性模型。 这将以张量板格式将训练信息输出到名为log的子目录中。 要获取测试成绩,请运行 python3 /path/to/log_folder output_file.txt 最终分数将输出到output_file.txt,测试进度将...
6. JAX-WS:Spring通过JAX-WS为远程Web服务提供支持(the successor of JAX-RPC, as introduced in Java EE 5 and Java 6)。 7. JMS:远程访问通过类JmsInvokerServiceExporter和JmsInvokerProxyFactoryBean使用JMS的...
在Tesser fMRI数据上实现SR模型的代码这是用于在Tesser实验中的行为和神经影像数据上实现后继表示(SR)模型的存储库。 您可以找到有关Tesser的更多信息。 用于读取行为数据和模拟的所有代码库都应位于tesser下...
开源项目-centrifugal-centrifugo.zip,Centrifugo – open-source real-time messaging server in Go, the successor of Centrifuge (originally written in Python)
Handler:定义处理请求的接口,并且实现后继链(successor)public abstract class Handler {public class
EUV Lithography—The Successor to Optical Lithography?
OpenPDF is an open source Java library for PDF files OpenPDF is a Java library for creating and editing PDF files with a LGPL and MPL open source license. OpenPDF is the LGPL/MPL open source successor...
资料结构/演算法 程式 可参考题目(验证程式正确性) 二分搜索 排序问题 Heap LinkedList LinkedList Stack Queue (用array实作) Queue (用list实作) Simple Graph Simple Graph topologicalSort (用indegree的方法实...
开源项目-wal-g-wal-g.zip,Wal-G, PostgreSQL archival and restoration tool (Successor to Wal-E)
Java had the support for developing GUI applications since its version 1.0 using the AWT (Abstract Windows Toolkit). Later AWT was replaced by Swing, which gave a little better user experience, but ...
Java had the support for developing GUI applications since its version 1.0 using the AWT (Abstract Windows Toolkit). Later AWT was replaced by Swing, which gave a little better user experience, but ...
安装linux工具源码 (UUI) Universal USB Installer ?...This Open Source tool falls under the GNU General Public License Version 2 Source Code is made available at time of download, from the official UUI ...