首页 > 代码库 > 二叉查找树转换为顺序的双向链表
二叉查找树转换为顺序的双向链表
如题将二叉查找树转换为排序的双向链表，要求输入一棵二叉查找树，输出为一个排好序的双向链表，要求不能创建新的节点，只能改变指针的指向。
这个问题的考察点涉及到二叉查找树的概念，以及如何建立二叉查找树，双向链表的概念，以及二叉查找树和排序的双向链表的转换。
二叉查找树又称为有序二叉树，是指一颗空树或者具有以下性质的二叉树：
- 若任意节点的左子树不为空，则左子树上所有节点的值均小于等于根节点的值；
- 若任意节点的右子树不为空，则右子树上所有节点的值均大于等于根节点的值；
- 任意节点的左右子树也分别为二叉查找树；
- 没有键值相等的节点；
二叉查找树对任何节点x，其左子树中的关键字最大不超过key[x]，其右子树中的关键字最小不小于key[x]，不同的二叉查找树可以表示同一组值，在有关查找树的操作中，大部分操作的最坏情况运行时间与树的高度成正比。
对于本题要将二叉查找树转换为排序的双向链表，可以从递归的思想来考虑，为了将整棵树转换为顺序双向链表则可以将问题分解为，把左子树转换为顺序的双向链表，把右子树转换为顺序的双向链表，同时需要注意交换节点指针。
head为二叉查找树的key最小的节点min(root) tail为二叉查找树的key最大的节点max(root) root为二叉查找树的根节点 treeToLinkedList(head, tail, root) { treeToLinkedList(head, max(root.left), root.left) treeToLinkedList(min(root.right), tail, root.right) } |
具体实现如下：
public class TreeToList<Key extends Comparable<Key>> { private Node root; private class Node { Key key; Node left; Node right; Node(Key key) { this.key = key; } } /* 向二叉查找树中插入元素，用于构建二叉查找树 */ public void put(Key key) { root = put(root, key); //System.out.println(root.key + " " + root.left + " " + root.right); } private Node put(Node x, Key key) { /* 如果要插入的根节点为空则直接创建一个新节点作为根节点 */ if (x == null) { return new Node(key); } int cmp = key.compareTo(x.key); /* 如果要插入的节点key小于根节点的key则需要将key插入到 * 根节点的左子树，如果大于根节点的key则需要将key插入到 * 根节点的右子树，否则直接返回 */ if (cmp < 0) { x.left = put(x.left, key); } else if (cmp > 0) { x.right = put(x.right, key); } else { return null; } return x; } public Key min() { return min(root).key; } /* 获取二叉查找树中key最小的节点 */ private Node min(Node x) { /* 如果x的左子树为空则x作为根节点即为二叉查找树中key最小的节点， * 如果x的左子树不为空则需要递归在x的左子树中查找key最小的节点*/ if (x == null) { return null; } if (x.left == null) { return x; } return min(x.left); } public Key max() { return max(root).key; } /* 获取二叉查找树中key最大的节点 */ private Node max(Node x) { if (x == null) { return null; } if (x.right == null) { return x; } return max(x.right); } public void treeToList() { treeToList(min(root), max(root), root); Node tmp = min(root); while (tmp != null) { System.out.print(tmp.key + "->"); tmp = tmp.right; } System.out.println(); tmp = max(root); while (tmp != null) { System.out.print(tmp.key + "->"); tmp =tmp.left; } } /* 将二叉查找树转换为顺序的双向链表，head为以x为根节点的二叉查找树中key * 最小的节点，tail为以x为根节点的二叉查找树中key最大的节点 */ private void treeToList(Node head, Node tail, Node x) { if (x == null) { head = null; tail = null; return; } Node lmax = max(x.left); Node rmin = min(x.right); treeToList(head, lmax, x.left); treeToList(rmin, tail, x.right); if (lmax != null) { lmax.right = x; x.left = lmax; } if (rmin != null) { rmin.left = x; x.right = rmin; } } public static void main(String[] args) { TreeToList<Integer> ttl = new TreeToList<Integer>(); int[] array = {10, 6, 14, 4, 8, 12, 16}; for (int i = 0; i < array.length; i++) { ttl.put(array[i]); } System.out.println("min: " + ttl.min() + " max: " + ttl.max()); ttl.treeToList(); }}
二叉查找树转换为顺序的双向链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。