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();
}
}
}
分享到:
相关推荐
将二叉搜索树转换为双向链表,可以利用中序遍历实现。遍历过程中,将当前节点的右指针指向前一个节点,前一个节点的左指针指向当前节点。这样,遍历结束后,所有节点形成了一个有序的双向链表。在Java代码中,定义...
二叉搜索树转换为双向链表.28.打印字符串中所有字符的排列29.数组中出现次数超过一半的数字.30.找出最小的K个数31.连续子数组的最大和.32.从1到整数n中1出现的次数.33.把数组中的数排成一个最小的数.3
树转成双向链表的操作,通常是将二叉搜索树按照中序遍历的结果转换成一个有序的双向链表,便于连续访问。 综上所述,掌握Java语言实现二叉树的各种操作对于理解和运用数据结构及算法至关重要,这些操作在实际编程中...
《实战应用Java算法分析与设计》视频教程深入浅出地讲解了链表、二叉树、哈夫曼树、图以及动态规划等核心数据结构与算法,并通过Java语言实现这些理论知识的应用。本文将对这一系列视频中的知识点进行总结,旨在帮助...
书中对单链表、双向链表、链接表等数据结构的定义、实现及其对比进行了深入讨论。 第四章聚焦于栈与队列的数据结构,讨论了它们的定义、抽象数据类型、存储实现以及应用示例,比如进制转换、括号匹配检测和迷宫求解...
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、...
27. 二叉搜索树转换为双向链表:考察对二叉搜索树和双向链表的理解。 28. 打印字符串中所有字符的排列:考察字符串和数组的排列算法。 29. 数组中出现次数超过一半的数字:考察排序算法以及投票算法。 30. 找出...
文件可能涉及将BST转换为有序双向链表,这是一个常见的操作,可以通过中序遍历实现。 5. **CloneComplexList.java**:这涉及到克隆复杂链表,即链表节点中包含指向其他节点的引用,不仅仅是简单的前驱和后继关系。...
- **二叉查找树遍历**: 对于二叉查找树,通常使用中序遍历得到有序序列。 总的来说,Java Map接口及其子类提供了一种灵活且高效的存储和检索键值对的方式。通过深入理解Map的内部原理和不同子类的特性,我们可以...
红黑树是一种自平衡二叉查找树,它确保了任何节点到其每个叶子节点的所有路径都具有相同的黑色节点数,从而保证了树的高度平衡。在HashMap中,当链表长度超过一定阈值时,会将链表转换为红黑树,以利用二分查找的...
- 二叉搜索树转换为双向链表:这是一个深度优先搜索(DFS)的应用问题,需要通过递归遍历树结构来转换为双向链表。 - 打印字符串中所有字符的排列:这是一个经典的回溯算法问题,需要列出字符串中所有可能的排列...
在查找和排序章节中,读者可以学习到顺序查找、折半查找和各种查找树的实现,包括二叉查找树、AVL树、B-树以及哈希表。排序部分则包含了插入排序、折半插入排序、希尔排序等排序算法的基本概念和实现。 整本书籍是...
24. 二叉搜索树转换为双向链表:这是一个树结构到链表结构的转换问题,需要使用中序遍历来实现。 25. 打印字符串中所有字符的排列:这需要使用回溯算法来遍历所有可能的排列组合。 《剑指Offer》中的题目覆盖了...
链表有单向链表、双向链表和循环链表等多种形式,适合动态增加或删除元素。 3. **栈**:栈是一种后进先出(LIFO)的数据结构,常用于函数调用、表达式求值等场景。Java中,`java.util.Stack`类提供了栈的操作。 4....
- **二叉查找树**:介绍二叉查找树的定义,以及二叉查找树的基本操作。 - **AVL树**:解释AVL树的概念,以及AVL树的平衡调整方法。 - **B-树**:介绍B-树的结构特点,以及B-树的插入和删除操作。 - **哈希** - ...
- 二叉搜索树转换为双向链表:考察二叉树的遍历和链表操作。 除了上述内容,书中还讨论了编程语言特性,如: - O(1)时间删除链表节点:考察对链表数据结构的深入理解和对特殊操作的处理方法。 - 判断一个栈是否是...