樣例

樹的中序遍歷：1 2 3 4 5 6 7 ，轉換后雙向鏈表的遍歷：1 2 3 4 5 6 7

java代碼

/*** @Description:搜索二叉樹轉換為雙向鏈表* @Author: lizhouwei* @CreateDate: 2018/4/7 10:45* @Modify by:* @ModifyDate:*/ public class Chapter2_15 {public DoubleNode treeToDubleNode(Tree tree) {//用隊列存放將樹的中序遍歷Queue<Tree> trees = new LinkedList<Tree>();//中序遍歷recInOrder(tree, trees);//構造雙向鏈表tree = trees.poll();DoubleNode head = new DoubleNode(tree.vlaue);DoubleNode pre = head;DoubleNode cur = null;while (!trees.isEmpty()) {tree = trees.poll();cur = new DoubleNode(tree.vlaue);pre.next = cur;cur.pre = pre;pre = cur;}return head;}public void recInOrder(Tree tree, Queue<Tree> trees) {if (tree == null) {return;}recInOrder(tree.left, trees);trees.offer(tree);recInOrder(tree.right, trees);}//打印樹public void recInOrder(Tree tree) {if (tree == null) {return;}recInOrder(tree.left);System.out.print(tree.vlaue + " ");recInOrder(tree.right);}//測試public static void main(String[] args) {Chapter2_15 chapter = new Chapter2_15();Tree root = new Tree(4);root.left = new Tree(2);root.right = new Tree(6);root.left.left = new Tree(1);root.left.right = new Tree(3);root.right.left = new Tree(5);root.right.right = new Tree(7);chapter.recInOrder(root);DoubleNode head = chapter.treeToDubleNode(root);Link.printDLink(head);} }class Tree {public int vlaue;public Tree left;public Tree right;public Tree(int vlaue) {this.vlaue = vlaue;}}

轉載于:https://www.cnblogs.com/lizhouwei/p/8732666.html

總結

以上是生活随笔為你收集整理的《程序员代码面试指南》第二章 链表问题 搜索二叉树转换为双向链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。