问题:
给一个二叉查找树(BST),找出第 k 大的值。比如:
该图中,第3大的值是10.
分析:
我们可以通过类似中序遍历的方法把BST从大到小排序,然后,就可以得到第 k 大的值了。代码如下:
public class NthNode {
// k refers to the counter. it is a global variable.
static int k = 0;
//get the nth largest value in BST
public void getNthnode(Node root, int n) {
if (root == null) return;
getNthnode(root.rightChild, n);
k++;
if (k == n) {
System.out.print(root.toString());
}
getNthnode(root.leftChild, n);
}
public static void main(String[] args) {
Node a = new Node(8);
Node b = new Node(3);
Node c = new Node(10);
Node d = new Node(1);
Node e = new Node(6);
Node f = new Node(14);
Node g = new Node(4);
Node h = new Node(7);
Node i = new Node(13);
a.leftChild = b;
a.rightChild = c;
b.leftChild = d;
b.rightChild = e;
c.rightChild = f;
e.rightChild = g;
e.rightChild = h;
f.leftChild = i;
//the third largest value in BST
new NthNode().getNthnode(a, 3);
}
}
class Node {
Node leftChild = null;
Node rightChild = null;
int value;
Node(int value) {
this.value = value;
}
public String toString() {
return value + "";
}
}
转载请注明出处:http://blog.csdn.net/beiyeqingteng
分享到:
相关推荐
数据结构课堂上的作业,C++实现二叉查找树中查找第n大元素,已通过检测
在学习算法过程中自己的代码实现,与大家分享交流。版权所有:miracledan
二叉查找树c 源码
用C++实现的最优二叉查找树,简单,明了,是数据结构里经典必学算法,初学者适用
1、 定义二叉查找树的类。 2、 实验验证如下算法的正确性、各种功能及指标: 1)实现二叉查找树结构; 2) 实现二叉查找树的查找、插入和删除等算法;
findwords查找文件是否有某单词,这是一个二叉查找树的练习
这个程序实现了二叉查找树的删除,增加,先序遍历,后序遍历,中序遍历,还有一些非递归和层次遍历!
二叉查找树
二叉查找树的最大最小以及任意数查找
c++实现的二叉查找树,代码简陋,大家互相学习即可
二叉查找树实现简单的信息检索
自己动手实现的一个二叉查找排序树的类BinSortTree,实现数据的插入,查找,删除,层序遍历,中序遍历等操作,熟悉数据结构的朋友都知道,根据二叉排序树的定义,中序遍历后得到的序列就是按照从小到大的顺序排列的...
二叉查找树的实现。包括树的平衡以及树节点的删除。以及树的广度优先遍历,深度优先遍历。
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
二叉查找树的常用操作,含C++代码,找工作的时候可以放在手机里看。
使用C++实现最优二叉查找树,对正在学习算法的同学应该挺有帮助的
二叉查找树 二分搜索树(英语:Binary Search Tree),也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树。满足以下几个条件: 若它的左子树不为空,左子树上所有节点的值都小于它的根节点。 若它的右子树...
这是一个二叉查找树,实现了以下操作:插入结点、构造二叉树、删除结点、查找、 查找最大值、查找最小值、查找指定结点的前驱和后继。上述所有操作时间复杂度均为o(h),其中h是树的高度 注释很详细,具体内容就看...