一直觉得自己算法和数据结构方面很欠缺,最近放寒假在家里没事,看见网上的这道题目,所以就编写了下,就当作给今年找工作练练手吧,随便也提高下自己这方面的知识。
题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。
比如将二元查找树
转换成双向链表 4=6=8=10=12=14=16
题目来源:
http://zhedahht.blog.163.com/blog/static/254111742007127104759245/
链接中的解决方法其实已经说的很清楚了,并且用C实现了,我只不过是依葫芦画瓢用Java实现了一把。具体解决方案如下:(直接从以上链接中复制的)
当我们到达某一结点准备调整以该结点为根结点的子树时,先调整其左子树将左子树转换成一个排好序的左子链表,再调整其右子树转换右子链表。最近链接左子链表的最右结点(左子树的最大结点)、当前结点和右子链表的最左结点(右子树的最小结点)。从树的根结点开始递归调整所有结点。
package tree;
/**
* 代表树中的单个结点
* @author DHC
*
*/
public class Node {
public Node(int str) {
content = str;
}
private int content;
private Node left;
private Node right;
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public int getContent() {
return content;
}
public void setContent(int content) {
this.content = content;
}
public void setRight(Node right) {
this.right = right;
}
}
package tree;
/**
* 代表有结点形成的树,要将其变为双向链表
* @author DHC
*
*/
public class Tree {
public static Node rootNode = new Node(10);
static {
Node node6 = new Node(6);
Node node4 = new Node(4);
Node node8 = new Node(8);
Node node14 = new Node(14);
Node node12 = new Node(12);
Node node16 = new Node(16);
rootNode.setLeft(node6);
rootNode.setRight(node14);
node6.setLeft(node4);
node6.setRight(node8);
node14.setLeft(node12);
node14.setRight(node16);
}
public Node getRootNode () {
return rootNode;
}
}
package tree;
/**
* 将树转变为双向链表
* @author DHC
*
*/
public class TreeToList {
private Node convert(Node rootNode, boolean isRight) {
if (rootNode == null) {
return null;
}
Node leftNode = rootNode.getLeft();
Node rightNode = rootNode.getRight();
// 左右节点为空
if (leftNode != null) {
Node leftResultNode = convert(leftNode, false);
if (leftResultNode != null) {
rootNode.setLeft(leftResultNode);
leftResultNode.setRight(rootNode);
}
}
if (rightNode != null) {
Node rightResultNode = convert(rightNode, true);
if (rightResultNode != null) {
rightResultNode.setLeft(rootNode);
rootNode.setRight(rightResultNode);
}
}
Node tempNode = rootNode;
if (isRight) {
if (leftNode != null) {
tempNode = leftNode;
}
} else {
if (rightNode != null) {
tempNode = rightNode;
}
}
return tempNode;
}
public static void main(String[] args) {
TreeToList treeToList = new TreeToList();
treeToList.convert(Tree.rootNode, true);
System.out.println(Tree.rootNode.getLeft().getLeft().getLeft().getContent());
System.out.println(Tree.rootNode.getLeft().getLeft().getContent());
System.out.println(Tree.rootNode.getLeft().getContent());
System.out.println(Tree.rootNode.getContent());
System.out.println(Tree.rootNode.getRight().getContent());
System.out.println(Tree.rootNode.getRight().getRight().getContent());
System.out.println(Tree.rootNode.getRight().getRight().getRight().getContent());
}
}
- 大小: 5.6 KB
分享到:
相关推荐
二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4...
微软面试题第一题 直接就可以运行 不过二元查找树 不知道怎么自动生成 所以硬生生地一个个敲出来的 为了学习二元树的就不用下了
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表 要求不能创建任何新的节点,只调整指针的指向 微软面试题
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...
JAVA实现链表_双向链表
用Java定义一个双向链表,实现链表的基本操作: 初始化、获取头结点、添加新元素、删除链表元素、 获取链表元素、查找链表元素、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空链表。
排序树 变成双向链表排序树
通过java实现的双向链表,及反转功能,可能对面试有用哦
二叉排序树变成双向循环链表,二叉排序树变成双向循环链表,二叉排序树变成双向循环链表
这个是某公司的一道题,是把二叉查找树 转为双向链表的,我用程序实现了。希望对你有帮助!
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为...
用java实现双向链表的完整操作,主要用到内部类实现。
微软面试题,输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。适合新手入门结构清晰易懂
用双向起泡排序法对带头结点的双向链表按升序进行排序
把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表...
在双向链表上实现快速排序的递归算法 输入的形式:元素个数、元素都为整型。 输入值范围:元素个数为非负正整数,需要排序的元素都为整型。 输出的形式:排序前的元素序列和排序后的元素序列。 程序的功能:对用户...
操作包括: 1. 在头部添加结点 2. 在尾部添加结点 3. 遍历 4. 逆置 5. 删除
双端链表和双向链表Java代码
操作系统c++编程实现安全型双向链表,线程的创建,利用线程对链表进行增删改操作,并检验结果是否正确
http://msdn.microsoft.com/en-us/library/95z04bas(v=VS.71).aspx 双向链表