![]()
1 // 面试题8：二叉树的下一个结点
2 // 题目：给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？
3 // 树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。
4
5 #include <stdio.h>
6
7 struct BinaryTreeNode
8 {
9 int m_nValue;
10 BinaryTreeNode* m_pLeft;
11 BinaryTreeNode* m_pRight;
12 BinaryTreeNode* m_pParent;
13 };
14
15 BinaryTreeNode* GetNext(BinaryTreeNode* pNode)
16 {
17 if(pNode == nullptr)
18 return nullptr;
19
20 BinaryTreeNode* pNext = nullptr;
21 if(pNode->m_pRight != nullptr)
22 {
23 BinaryTreeNode* pRight = pNode->m_pRight;
24 while(pRight->m_pLeft != nullptr)
25 pRight = pRight->m_pLeft;
26
27 pNext = pRight;
28 }
29 else if(pNode->m_pParent != nullptr)
30 {
31 BinaryTreeNode* pCurrent = pNode;
32 BinaryTreeNode* pParent = pNode->m_pParent;
33 while(pParent != nullptr && pCurrent == pParent->m_pRight)
34 {
35 pCurrent = pParent;
36 pParent = pParent->m_pParent;
37 }
38
39 pNext = pParent;
40 }
41
42 return pNext;
43 }
44
45 // ==================== 辅助代码用来构建二叉树 ====================
46 BinaryTreeNode* CreateBinaryTreeNode(int value)
47 {
48 BinaryTreeNode* pNode = new BinaryTreeNode();
49 pNode->m_nValue = value;
50 pNode->m_pLeft = nullptr;
51 pNode->m_pRight = nullptr;
52 pNode->m_pParent = nullptr;
53
54 return pNode;
55 }
56
57 void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
58 {
59 if(pParent != nullptr)
60 {
61 pParent->m_pLeft = pLeft;
62 pParent->m_pRight = pRight;
63
64 if(pLeft != nullptr)
65 pLeft->m_pParent = pParent;
66 if(pRight != nullptr)
67 pRight->m_pParent = pParent;
68 }
69 }
70
71 void PrintTreeNode(BinaryTreeNode* pNode)
72 {
73 if(pNode != nullptr)
74 {
75 printf("value of this node is: %d
", pNode->m_nValue);
76
77 if(pNode->m_pLeft != nullptr)
78 printf("value of its left child is: %d.
", pNode->m_pLeft->m_nValue);
79 else
80 printf("left child is null.
");
81
82 if(pNode->m_pRight != nullptr)
83 printf("value of its right child is: %d.
", pNode->m_pRight->m_nValue);
84 else
85 printf("right child is null.
");
86 }
87 else
88 {
89 printf("this node is null.
");
90 }
91
92 printf("
");
93 }
94
95 void PrintTree(BinaryTreeNode* pRoot)
96 {
97 PrintTreeNode(pRoot);
98
99 if(pRoot != nullptr)
100 {
101 if(pRoot->m_pLeft != nullptr)
102 PrintTree(pRoot->m_pLeft);
103
104 if(pRoot->m_pRight != nullptr)
105 PrintTree(pRoot->m_pRight);
106 }
107 }
108
109 void DestroyTree(BinaryTreeNode* pRoot)
110 {
111 if(pRoot != nullptr)
112 {
113 BinaryTreeNode* pLeft = pRoot->m_pLeft;
114 BinaryTreeNode* pRight = pRoot->m_pRight;
115
116 delete pRoot;
117 pRoot = nullptr;
118
119 DestroyTree(pLeft);
120 DestroyTree(pRight);
121 }
122 }
123
124 // ====================测试代码====================
125 void Test(char* testName, BinaryTreeNode* pNode, BinaryTreeNode* expected)
126 {
127 if(testName != nullptr)
128 printf("%s begins: ", testName);
129
130 BinaryTreeNode* pNext = GetNext(pNode);
131 if(pNext == expected)
132 printf("Passed.
");
133 else
134 printf("FAILED.
");
135 }
136
137 // 8
138 // 6 10
139 // 5 7 9 11
140 void Test1_7()
141 {
142 BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
143 BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
144 BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
145 BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
146 BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
147 BinaryTreeNode* pNode9 = CreateBinaryTreeNode(9);
148 BinaryTreeNode* pNode11 = CreateBinaryTreeNode(11);
149
150 ConnectTreeNodes(pNode8, pNode6, pNode10);
151 ConnectTreeNodes(pNode6, pNode5, pNode7);
152 ConnectTreeNodes(pNode10, pNode9, pNode11);
153
154 Test("Test1", pNode8, pNode9);
155 Test("Test2", pNode6, pNode7);
156 Test("Test3", pNode10, pNode11);
157 Test("Test4", pNode5, pNode6);
158 Test("Test5", pNode7, pNode8);
159 Test("Test6", pNode9, pNode10);
160 Test("Test7", pNode11, nullptr);
161
162 DestroyTree(pNode8);
163 }
164
165 // 5
166 // 4
167 // 3
168 // 2
169 void Test8_11()
170 {
171 BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
172 BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
173 BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
174 BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
175
176 ConnectTreeNodes(pNode5, pNode4, nullptr);
177 ConnectTreeNodes(pNode4, pNode3, nullptr);
178 ConnectTreeNodes(pNode3, pNode2, nullptr);
179
180 Test("Test8", pNode5, nullptr);
181 Test("Test9", pNode4, pNode5);
182 Test("Test10", pNode3, pNode4);
183 Test("Test11", pNode2, pNode3);
184
185 DestroyTree(pNode5);
186 }
187
188 // 2
189 // 3
190 // 4
191 // 5
192 void Test12_15()
193 {
194 BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
195 BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
196 BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
197 BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
198
199 ConnectTreeNodes(pNode2, nullptr, pNode3);
200 ConnectTreeNodes(pNode3, nullptr, pNode4);
201 ConnectTreeNodes(pNode4, nullptr, pNode5);
202
203 Test("Test12", pNode5, nullptr);
204 Test("Test13", pNode4, pNode5);
205 Test("Test14", pNode3, pNode4);
206 Test("Test15", pNode2, pNode3);
207
208 DestroyTree(pNode2);
209 }
210
211 void Test16()
212 {
213 BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
214
215 Test("Test16", pNode5, nullptr);
216
217 DestroyTree(pNode5);
218 }
219
220 int main(int argc, char* argv[])
221 {
222 Test1_7();
223 Test8_11();
224 Test12_15();
225 Test16();
226 }
