思路：采用中序遍歷將二叉樹從小到大遍歷每一個結點，通過改變指針來實現雙向鏈表。
1 #include<stdio.h>
2 #include "stdafx.h"
3 #include<tchar.h>
4
5 struct BinaryTreeNode
6 {
7 int m_nValue;
8 BinaryTreeNode* m_pLeft;
9 BinaryTreeNode* m_pRight;
10 };
11 BinaryTreeNode* CreateBinaryTreeNode(int value)
12 {
13 BinaryTreeNode* pNode = new BinaryTreeNode();
14 pNode->m_nValue = value;
15 pNode->m_pLeft = NULL;
16 pNode->m_pRight = NULL;
17 }
18 void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
19 {
20 if(pParent != NULL)
21 {
22 pParent->m_pLeft = pLeft;
23 pParent->m_pRight = pRight;
24 }
25 }
26 void PrintTreeNode(BinaryTreeNode* pNode)
27 {
28 if(pNode != NULL)
29 {
30 printf("value of this node is: %d\n", pNode->m_nValue);
31
32 if(pNode->m_pLeft != NULL)
33 printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue);
34 else
35 printf("left child is null.\n");
36
37 if(pNode->m_pRight != NULL)
38 printf("value of its right child is: %d.\n",pNode->m_pRight->m_nValue);
39 else
40 printf("right child is null.\n");
41 }
42 else
43 {
44 printf("this node is null.\n");
45 }
46 printf("\n");
47 }
48 void PrintTree(BinaryTreeNode* pRoot)
49 {
50 PrintTreeNode(pRoot);
51
52 if(pRoot != NULL)
53 {
54 if(pRoot->m_pLeft != NULL)
55 PrintTree(pRoot->m_pLeft);
56
57 if(pRoot->m_pRight != NULL)
58 PrintTree(pRoot->m_pRight);
59 }
60 }
61 void DestroyTree(BinaryTreeNode* pRoot)
62 {
63 if(pRoot != NULL)
64 {
65 BinaryTreeNode* pLeft = pRoot->m_pLeft;
66 BinaryTreeNode* pRight = pRoot->m_pRight;
67
68 delete pRoot;
69 pRoot = NULL;
70
71 DestroyTree(pLeft);
72 DestroyTree(pRight);
73 }
74 }
75
76 void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList);
77
78
79 BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)
80 {
81 BinaryTreeNode *pLastNodeInList = NULL;
82 ConvertNode(pRootOfTree, &pLastNodeInList);
83
84 //pLastNodeInList指向鏈表的的尾結點，遍歷找到頭結點返回。
85 BinaryTreeNode *pHeadOfList = pLastNodeInList;
86 while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL)
87 pHeadOfList = pHeadOfList->m_pLeft;
88
89 return pHeadOfList;
90 }
91
92 //中序遍歷轉換過程，
93 //參數:處理當前結點， 當前鏈表最後一個結點(初始值為空)
94 void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)
95 {
96 if(pNode == NULL)
97 return;
98
99 BinaryTreeNode *pCurrent = pNode;
100
101 //遞歸處理左子樹
102 if(pCurrent->m_pLeft != NULL)
103 ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
104
105 //將當前鏈表的左指針指向已經轉換好的鏈表的最後一個位置
106 pCurrent->m_pLeft = *pLastNodeInList;
107
108 //將已經轉換好的鏈表的最後一個結點的右指針指向當前結點
109 if(*pLastNodeInList != NULL)
110 (*pLastNodeInList)->m_pRight = pCurrent;
111
112 //更新鏈表最後一個結點
113 *pLastNodeInList = pCurrent;
114
115 //遞歸處理當前結點的右子樹
116 if(pCurrent->m_pRight != NULL)
117 ConvertNode(pCurrent->m_pRight, pLastNodeInList);
118 }
119
120 //打印雙向鏈表
121 void PrintDoubleLinkedList(BinaryTreeNode* pHeadOfList)
122 {
123 BinaryTreeNode* pNode = pHeadOfList;
124
125 printf("The nodes from left to right are:\n");
126 while(pNode != NULL)
127 {
128 printf("%d\t", pNode->m_nValue);
129
130 if(pNode->m_pRight == NULL)
131 break;
132 pNode = pNode->m_pRight;
133 }
134 printf("\n");
135 }
136
137 void DestroyList(BinaryTreeNode* pHeadOfList)
138 {
139 BinaryTreeNode* pNode = pHeadOfList;
140 while(pNode != NULL)
141 {
142 BinaryTreeNode* pNext = pNode->m_pRight;
143
144 delete pNode;
145 pNode = pNext;
146 }
147 }
148
149 // 10
150 // / \
151 // 6 14
152 // /\ /\
153 // 4 8 12 16
154
155 int main()
156 {
157 BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
158 BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
159 BinaryTreeNode* pNode14 = CreateBinaryTreeNode(14);
160 BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
161 BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
162 BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12);
163 BinaryTreeNode* pNode16 = CreateBinaryTreeNode(16);
164
165 ConnectTreeNodes(pNode10, pNode6, pNode14);
166 ConnectTreeNodes(pNode6, pNode4, pNode8);
167 ConnectTreeNodes(pNode14, pNode12, pNode16);
168
169 PrintTree(pNode10);
170
171 BinaryTreeNode* pHeadOfList = Convert(pNode10);
172
173 printf("The nodes from left to right are:\n");
174 PrintDoubleLinkedList(pHeadOfList);
175 printf("\n");
176
177 DestroyList(pNode4);
178 }
