算法题24 二叉树的中序遍历之二叉搜索树转排序双向链表

题目

　　输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

分析

　　二叉搜索树的左孩子比父节点的值小，右孩子比父节点的值大，通过中序遍历即可得到一个排序的队列。在遍历的过程中调整节点指针的指向就可以将它转换成一个排序的双向链表了

　　此前曾分析过二叉树的中序遍历的非递归方法。借此直接转化为求排序双向链表的方法

代码

 1 TreeNode* BinaryTreeConvert2(TreeNode* root)
 2 {
 3     if (!root)
 4     {
 5         throw std::exception("this is an empty tree!");
 6     }
 7 
 8     stack<TreeNode*> s_tree;
 9     TreeNode* node=root,*pre_node=NULL,*head=NULL;
10     while (node||!s_tree.empty())
11     {
12         while (node)
13         {
14             s_tree.push(node);
15             node=node->pLeft;
16         }
17 
18         node=s_tree.top();
19         s_tree.pop();
20 
21         /*
22          *将中序遍历的输出变为指针调整
23         */
24         //cout<<node->value<<endl;
25         //指定双向链表的头节点
26         if(!head)
27             head=node;
28 
29         //前后指针
30         node->pLeft=pre_node;
31         if (pre_node)
32         {
33             pre_node->pRight=node;
34         }
35         //记录前一个节点
36         pre_node=node;
37 
38 
39         node=node->pRight;
40     }
41 
42     return head;
43 }

创建一个新的双向链表

 1 DListNode* BinaryTreeConvert(TreeNode* root)
 2 {
 3     if (!root)
 4     {
 5         throw std::exception("this is an empty tree!");
 6     }
 7 
 8     stack<TreeNode*> s_tree;
 9     stack<DListNode*> s_list;
10     TreeNode* node=root;
11     DListNode *head=NULL,*tail=NULL;
12     DListNode *list_node=NULL,*pre_node=NULL;
13     while (node||!s_tree.empty())
14     {
15         while (node)
16         {
17             s_tree.push(node);
18             node=node->pLeft;
19         }
20 
21         node=s_tree.top();
22         s_tree.pop();
23 
24         /*
25          *将中序遍历的输出变为双向链表节点创建以及指针调整
26         */
27         //cout<<node->value<<endl;
28         list_node=new DListNode();
29         list_node->value=node->value;
30         list_node->pNext=NULL;
31         list_node->pPre=NULL;
32 
33         //指定双向链表的头节点
34         if(!head)
35             head=list_node;
36 
37         //前后指针
38         list_node->pPre=pre_node;
39         if (pre_node)
40         {
41             pre_node->pNext=list_node;
42         }
43 
44         pre_node=list_node;
45 
46 
47         node=node->pRight;
48     }
49 
50     return head;
51 }