题目:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
中序遍历,遍历的过程生成双向链表。
先实现双线链表,然后实现二叉查找树。
class Node {
private int value;
private Node pre = null;
private Node next = null;
private Node prior = null;
public Node(int value) {
this.value = value;
prior = this;
}
public void insert(int value) {
Node node = new Node(value);
prior.next = node;
node.pre = prior;
prior = node;
}
public void print() {
Node node = this;
Node n = null;
while (node != null) {
n = node;
System.out.print(node.value + " ");
node = node.next;
}
System.out.println("-----");
while (n != null) {
System.out.print(n.value + " ");
n = n.pre;
}
}
}
public class BiSearchTree {
private BiSearchTree LeftTree = null;
private BiSearchTree RightTree = null;
private int data;
public BiSearchTree(int data) {
this.data = data;
}
public void insert(int element) {
BiSearchTree tree = this;
BiSearchTree insert_node = new BiSearchTree(element);
BiSearchTree pre = null;
boolean left = true;
while (tree != null) {
pre = tree;
if (tree.data > element) {
left = true;
tree = tree.LeftTree;
} else {
left = false;
tree = tree.RightTree;
}
}
if (left) {
pre.LeftTree = insert_node;
} else {
pre.RightTree = insert_node;
}
}
public void exchange2Link() {
BiSearchTree node = this;
BiSearchTree parent = null;
Stack stack = new Stack();
Node twoDirLinkList = new Node(Integer.MAX_VALUE);
do {
while (node != null) {
stack.push(node);
node = node.LeftTree;
}
BiSearchTree opNode = (BiSearchTree) stack.pop();
twoDirLinkList.insert(opNode.data);
System.out.print(opNode.data + " ");
node = opNode.RightTree;
} while (!stack.IsEmpty() || node != null);
twoDirLinkList.print();
}
public static void main(String[] args) {
// int[] data = {5,2,3,7,4,1,8,6};
// int[] data = {10,5,12,4,7,2,14,12,9};
int[] data = { 10, 5, 12, 4, 7 };
BiSearchTree tree = new BiSearchTree(data[0]);
for (int i = 1; i < data.length; i++) {
tree.insert(data[i]);
}
}
}
分享到:
相关推荐
微软面试题第一题 直接就可以运行 不过二元查找树 不知道怎么自动生成 所以硬生生地一个个敲出来的 为了学习二元树的就不用下了
二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4...
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表 要求不能创建任何新的节点,只调整指针的指向 微软面试题
把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表...
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为...
微软面试题,输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。适合新手入门结构清晰易懂
把二叉查找树转变成排序的双向链表 例如: 转换成双向链表 4=6=8=10=12=14=16 struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // ...
把二元查找树转变成排序的双向链表 设计包含min函数的栈。
程序员面试题精选 100 题(01)-把二元查找树转变成排序的 双向链表 题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点, 只调整指针的指向。 程序员面试题精选 100 题...
1.把二元查找树转变成排序的双向链表 2.设计包含min 函数的栈。 等等
数据结构算法设计笔试面试题100题内含C语言解析。 (01)把二元查找树转变成排序的双向链表 (02)设计包含min函数的栈 ...
1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 8 12 16 转换成双向链表 4...
算法永远是王道(含微软面试100题) (把二元查找树转变成排序的双向链表;设计包含min函数的栈;求子数组的最大和;在二元树中找出和为某一值的所有路径;查找最小的k个元素等)
1.把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=...
由第三方作者花费大量时间收集并整理散落在茫茫网络中的面经,并从中精选出若干具有代表性的技术类的面试题展开讨论,希望能给读者带来...把二元查找树转变成排序的双向链表 设计包含min函数的栈 把字符串转换成整数
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 algorithm.lru LRUCache: 基于JavaLinkedHashMap实现的 LRU 算法 algorithm.consistentHashing ConsistentHash: 一致性Hash算法 algorithm.cap ...
把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向...
1.2.1. 把二元查找树转变成排序的双向链表.................................................... 8 1.2.2. 下排每个数都是先前上排那十个数在下排出现的次数 ..........................11 1.2.3. 设计包含 min ...
双向链表是另一种形式的链式结构,双向链表的结点中有两个指针域,其一指向直接后继,另一指向直接前趋。双向链表克服了单链表的单向性的缺点。 前驱方向 后继方向 双向链表也可以有循环表,链表中存在两个...
这样的表称为双向链表。 在线性链表中,各数据元素结点的存储空间可以是不连续的,且各数据元素的存储顺序与逻辑顺序可以不一致。在线性链表中进行插入与删除,不需要移动链表中的元素。 线性单链表中,HEAD称为头...