算法题-二叉树转双向链表

元始天尊

1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
     10
    / \
   6  14
  / \ / \
4  8 12 16
转换成双向链表
4=6=8=10=12=14=16。

首先我们定义的二元查找树 节点的数据结构如下：

1. struct BSTreeNode
   
2. {
   
3.     int m_nValue; // value of node
   
4.     BSTreeNode *m_pLeft; // left child of node
   
5.     BSTreeNode *m_pRight; // right child of node
   
6. };

复制代码

我的解法

1. #include <stdio.h>
   
2. 
   
3. struct BSTreeNode
   
4. {
   
5.     int m_nValue;
   
6.     BSTreeNode* m_pLeft;//prev
   
7.     BSTreeNode* m_pRight;//next
   
8. };
   
9. 
   
10. BSTreeNode* addnode(int value,BSTreeNode* left=NULL,BSTreeNode* right=NULL)
    
11. {
    
12.     BSTreeNode* newone=new BSTreeNode;
    
13.     newone->m_pLeft=NULL;
    
14.     newone->m_pRight=NULL;
    
15.     newone->m_nValue=value;
    
16.     if(left)
    
17.     {
    
18.         newone->m_pLeft=left;
    
19.     }
    
20.     if(right)
    
21.     {
    
22.         newone->m_pRight=right;
    
23.     }
    
24.     return newone;
    
25. }
    
26. 
    
27. BSTreeNode* prevone=NULL;
    
28. 
    
29. void findone(BSTreeNode* curone)//中序遍历
    
30. {
    
31.     if(curone->m_pLeft)
    
32.     {
    
33.         findone(curone->m_pLeft);
    
34.     }
    
35. 
    
36.     prevone->m_pRight=curone;
    
37.     curone->m_pLeft=prevone;
    
38.     prevone=curone;
    
39. 
    
40.     if(curone->m_pRight)
    
41.     {
    
42.         findone(curone->m_pRight);
    
43.     }
    
44. }
    
45. 
    
46. void deletelist(BSTreeNode* head)
    
47. {
    
48.     if(head->m_pRight)
    
49.     {
    
50.         deletelist(head->m_pRight);
    
51.     }
    
52.     delete head;
    
53. }
    
54. 
    
55. void showlist(BSTreeNode* head)
    
56. {
    
57.     while(head->m_pRight)
    
58.     {
    
59.         printf("%d ",head->m_pRight->m_nValue);
    
60.         head=head->m_pRight;
    
61.     }
    
62.     printf("\n");
    
63. }
    
64. 
    
65. int main(int argc, char* argv[])
    
66. {
    
67.     BSTreeNode* head=addnode(-1);
    
68.     head->m_pLeft=NULL;
    
69.     prevone=head;
    
70. 
    
71.     BSTreeNode* root=addnode(10,addnode(6,addnode(4),addnode(8)),addnode(14,addnode(12),addnode(16)));
    
72.     findone(root);
    
73. 
    
74.     prevone->m_pRight=NULL;
    
75.     showlist(head);
    
76. 
    
77.     return 0;
    
78. }

复制代码

0xAA55

每次都是我来排版。。。