package cn.edu.cqupt.mircrosoft100;
/*
* 1.把二元查找树转变成排序的双向链表(树)
题目:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。
10
/ /
6 14
/ / / /
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16
*
*
*/
public class BSTreeNode {
private Integer value;
private BSTreeNode left;
private BSTreeNode right;
private BSTreeNode Llist;
static BSTreeNode head;
static BSTreeNode temp;
/*
* 插入节点
*/
public void add(int insertValue)
{
if(null==value)
value=insertValue;
else if(insertValue<=value)
{
if(null==left)
{
left = new BSTreeNode();
left.setValue(insertValue);
}
else
left.add(insertValue);
}
else
{
if(null==right)
{
right = new BSTreeNode();
right.setValue(insertValue);
}
else
right.add(insertValue);
}
}
/*
* 中序遍历打印二叉树
*/
public void list()
{
if(null==this.value)
return;
if(null!=left)
left.list();
System.out.println(value);
if(null!=right)
right.list();
}
/*
* 中序遍历链表
*/
public BSTreeNode convertToLinkList()
{
if(null!=left)
left.convertToLinkList();
addNodeToList(this);
if(null!=right)
right.convertToLinkList();
return null;
}
/*
*
* 添加节点到双向链表尾部
*/
public void addNodeToList(BSTreeNode node)
{
node.left=temp;
if(null!=temp)
{
temp.right=node;
}
else
{
head=node;
}
temp=node;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public BSTreeNode getLeft() {
return left;
}
public void setLeft(BSTreeNode left) {
this.left = left;
}
public BSTreeNode getRight() {
return right;
}
public void setRight(BSTreeNode right) {
this.right = right;
}
public static void main(String args[])
{
BSTreeNode tree = new BSTreeNode();
tree.add(10);
tree.add(6);
tree.add(8);
tree.add(4);
tree.add(16);
tree.add(12);
tree.add(14);
tree.add(2);
tree.list();
tree.convertToLinkList();
BSTreeNode node = tree.head;
System.out.println("Linklist:");
while(null!=node)
{
System.out.println(node.getValue());
node = node.getRight();
}
}
}
分享到:
相关推荐
这个是某公司的一道题,是把二叉查找树 转为双向链表的,我用程序实现了。希望对你有帮助!
二叉排序树变成双向循环链表,二叉排序树变成双向循环链表,二叉排序树变成双向循环链表
二叉搜索树 转为 双向链表, 导入eclipse时要改包名package classOne; BST To Double LinkedList change package name,
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 包含二叉树的建立,测试输出。。可直接运行。。
树的大部分操作需要从上至下一层层的查找树的节点,对于一棵满树,大约有一半的节点处于最底层(最底层节点数 = 其它层节点数的和 + 1),故节点操作大约有一半需要找到最底层节点,大约有四分之一的节点处于倒数第...
二叉排序树。用二叉链表作存储结构。...(3)计算二叉排序树T查找成功的平均查找长度,输出结果; (4)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序 历(执行操作2);否则输出信息“无x”。
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为...
二元查找树转变成排序...输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 普通的二叉树也可以转换成双向链表,只不过不是排序的 思路: 1. 与中序遍历相同 2. 采用...
36. 二叉搜索树与双向链表题目描述输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。解题思路private TreeNode pre = null;
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表 要求不能创建任何新的节点,只调整指针的指向 微软面试题
此程序包含三元组、循环链表以及二叉查找树的算法实现。
java基础面试题二叉搜索树与双向链表本资源系百度网盘分享地址
题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点,只能调整树中结点指针的指向。 ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = ...
二叉搜索树与双向链表01
二叉树转换为双向链表 通过随机创建二叉排序树测试二叉树转换为双向链表是否正确 http://blog.csdn.net/ssuchange/article/details/17383625
二叉排序树(二叉链表、引用).cpp
二叉搜索树与双向链表.md
对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素
C语言实现二叉排序树构造 查找删除节点 中序遍历 已调试好