【IT笔试面试题整理】二叉搜索树转换为双向链表

【试题描述】将二叉搜索树转换为双向链表

对于二叉搜索树，可以将其转换为双向链表，其中，节点的左子树指针在链表中指向前一个节点，右子树指针在链表中指向后一个节点。

思路一：

采用递归思想，对于二叉搜索树，将左、右子树分别转换为双向链表，左子树转换所得链表的头结点即整个树的头结点，左子树转换所得链表的尾节点与根节点相邻；右子树转换所得链表的尾节点即整个树的尾节点，右子树转换所得链表的头结点与根节点相邻。

 1     private static Node last;

 2     public static Node treeToList(Node tree)

 3     {

 4         Node head;

 5         // 若树为空，返回空

 6         if (tree == null)

 7             return null;

 8

 9         // 若无左子树，则该根节点为链表的头结点

10         if (tree.left == null)

11             head = tree;

12         // 若有左子树，递归调用转换函数将左子树转换为双向链表

13         // 左子树转换所得链表的头结点是整个树的头结点

14         // 左子树链表的尾结点与根节点相邻

15         else

16         {

17             head = treeToList(tree.left);

18             tree.left = last;

19             last.right = tree;

20         }

21         //若无右子树，则该根节点为链表的尾结点

22         if (tree.right == null)

23             last = tree;

24         //若有右子树，递归调用转换函数将右子树转换为双向链表

25         //右子树转换所得链表的尾结点是整个树的尾结点

26         //右子树链表的头结点与根节点相邻

27         else

28         {

29             tree.right = treeToList(tree.right);

30             tree.right.left = tree;

31         }

32         return head;

33

34     }

思路二：

我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

 1     // /////////////////////////////////////////////////////////////////////

 2     // Covert a sub binary-search-tree into a sorted double-linked list

 3     // Input: pNode - the head of the sub tree

 4     // pLast - the tail of the double-linked list

 5     // /////////////////////////////////////////////////////////////////////

 6     private static Node pLast;

 7

 8     public static void treeToList(Node pNode)

 9     {

10         if (pNode == null)

11             return;

12         Node pCurrent = pNode;

13

14         // Convert the left sub-tree

15         if (pCurrent.left != null)

16             treeToList(pCurrent.left);

17

18         // Put the current node into the double-linked list

19         pCurrent.left = pLast;

20

21         if (pLast != null)

22             pLast.right = pCurrent;

23

24         pLast = pCurrent;

25         // Convert the right sub-tree

26         if (pCurrent.right != null)

27             treeToList(pCurrent.right);

28     }

29

30     // /////////////////////////////////////////////////////////////////////

31     // Covert a binary search tree into a sorted double-linked list

32     // Input: pHead - the head of tree

33     // Output: the head of sorted double-linked list

34     // /////////////////////////////////////////////////////////////////////

35     public static Node convertTree(Node root)

36     {

37         treeToList(root);

38

39         // Get the head of the double-linked list

40         Node pHead = pLast;

41         while (pHead != null && pHead.left != null)

42             pHead = pHead.left;

43

44         return pHead;

45

46     }

巴特西

【IT笔试面试题整理】二叉搜索树转换为双向链表

最新文章

热门文章