算法系列15天速成 第十一天 树操作(上)（算法系列15天速成 第十一天 树操作(上)）

先前我们讲的都是“线性结构”，他的特征就是“一个节点最多有一个”前驱“和一个”后继“。那么我们今天讲的树会是怎样的呢？

我们可以对”线性结构“改造一下，变为”一个节点最多有一个"前驱“和”多个后继“。哈哈，这就是我们今天说的”树“。

一： 树

我们思维中的”树“就是一种枝繁叶茂的形象，那么数据结构中的”树“该是怎么样呢？对的，他是一种现实中倒立的树。

1：术语

其实树中有很多术语的，这个是我们学习树形结构必须掌握的。

<1> 父节点，子节点，兄弟节点

这个就比较简单了，b和c的父节点就是a，反过来说就是b和c是a的子节点。b和c就是兄弟节点。

<2> 结点的度

其实”度“就是”分支数“，比如a的分支数有两个“b和c",那么a的度为2。

<3> 树的度

看似比较莫名其妙吧，他和”结点的度“的区别就是，树的度讲究大局观，乃树中最大的结点度，其实也就是2。

<4> 叶结点，分支结点

叶结点就是既没有左孩子也没有右孩子结点，也就是结点度为0。分支节点也就是if的else的条件咯。

<5> 结点的层数

这个很简单，也就是树有几层。

<6> 有序树，无序树

有序树我们先前也用过，比如“堆”和“二叉排序树”，说明这种树是按照一定的规则进行排序的，else条件就是无序树。

<7> 森林

现实中，很多的树形成了森林，那在数据结构中，我们把上图的“a”节点砍掉，那么b，c子树合一起就是森林咯。

2: 树的表示

树这个结构的表示其实有很多种，常用的也就是“括号”表示法。
比如上面的树就可以表示为：(a(b(d),(e)),(c(f),(g)))

二： 二叉树

在我们项目开发中，很多地方都会用到树，但是多叉树的处理还是比较纠结的，所以俺们本着“大事化小，小事化了“的原则

把”多叉树“转化为”二叉树“，那么问题就简化了很多。

1： ”二叉树“和”树“有什么差异呢？

第一点: 树的度没有限制，而“二叉树”最多只能有两个，不然也就不叫二叉树了，哈哈。
第二点：树中的子树没有左右划分，很简单啊，找不到参照点，二叉树就有参照物咯。

2： 二叉树的类型

二叉树中有两种比较完美的类型，“完全二叉树”和“满二叉树”。

<1> 满二叉树

除叶子节点外，所有节点的度都为2，文章开头处的树就是这里的“满二叉树”。

<2> 完全二叉树

必须要满足两个条件就即可： 干掉最后一层，二叉树变为“满二叉树”。

最后一层的叶节点必须是“从左到右”依次排开。

我们干掉文章开头处的节点“f和”g",此时还是“完全二叉树”，但已经不是“满二叉树”了，你懂的。

3： 二叉树的性质

二叉树中有5点性质非常重要，也是俺们必须要记住的。

<1> 二叉树中，第i层的节点最多有2(i-1)个。

<2> 深度为k的二叉树最多有2k-1个节点。

<3> 二叉树中，叶子节点树为n1个，度为2的节点有n2个，那么n1=n2+1。

<4> 具有n个结点的二叉树深度为（log2 n）+1层。

<5> n个结点的完全二叉树如何用顺序存储，对于其中的一个结点i，存在以下关系，

2*i是结点i的父结点。

i/2是结点i的左孩子。

(i/2)+1是结点i的右孩子。

4： 二叉树的顺序存储

同样的存储方式也有两种，“顺序存储”和“链式存储”。

<1> 顺序存储

说实话，树的存储用顺序结构比较少，因为从性质定理中我们都可以看出只限定为“完全二叉树”，那么如果二叉树不是

“完全二叉树”，那我们就麻烦了，必须将其转化为“完全二叉树”，将空的节点可以用“#”代替，图中也可看出，为了维护

性质定理5的要求，我们牺牲了两个”资源“的空间。

<2> 链式存储

上面也说了，顺序存储会造成资源的浪费，所以嘛，我们开发中用的比较多的还是“链式存储”，同样“链式存储”

也非常的形象，非常的合理。

一个结点存放着一个“左指针”和一个“右指针”，这就是二叉链表。

如何方便的查找到该结点的父结点，可以采用三叉链表。

5: 常用操作

一般也就是“添加结点“，“查找节点”，“计算深度”，“遍历结点”，“清空结点”

<1> 这里我们就用二叉链表来定义链式存储模型

复制代码 代码如下:

#region 二叉链表存储结构
/// <summary>
/// 二叉链表存储结构
/// </summary>
/// <typeparam name="t"></typeparam>
public class chaintree<t>
{
public t data;

public chaintree<t> left;

public chaintree<t> right;
}
#endregion

<2> 添加结点

要添加结点，我们就要找到添加结点的父结点，并且根据指示插入到父结点中指定左结点或者右结点。

复制代码 代码如下:

#region 将指定节点插入到二叉树中
/// <summary>
/// 将指定节点插入到二叉树中
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
/// <param name="node"></param>
/// <param name="direction">插入做左是右</param>
/// <returns></returns>
public chaintree<t> bintreeaddnode<t>(chaintree<t> tree, chaintree<t> node, t data, direction direction)
{
if (tree == null)
return null;

if (tree.data.equals(data))
{
switch (direction)
{
case direction.left:
if (tree.left != null)
throw new exception("树的左节点不为空，不能插入");
else
tree.left = node;

break;
case direction.right:
if (tree.right != null)
throw new exception("树的右节点不为空，不能插入");
else
tree.right = node;

break;
}
}

bintreeaddnode(tree.left, node, data, direction);
bintreeaddnode(tree.right, node, data, direction);

return tree;
}
#endregion

<3> 查找节点

二叉树中到处都散发着递归思想，很能锻炼一下我们对递归的认识，同样查找也是用到了递归思想。

复制代码 代码如下:

#region 在二叉树中查找指定的key
/// <summary>
///在二叉树中查找指定的key
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
/// <param name="data"></param>
/// <returns></returns>
public chaintree<t> bintreefind<t>(chaintree<t> tree, t data)
{
if (tree == null)
return null;

if (tree.data.equals(data))
return tree;

return bintreefind(tree, data);
}
#endregion

<4> 计算深度

这个问题纠结了我二个多小时，原因在于没有深刻的体会到递归，其实主要思想就是递归左子树和右子树，然后得出较大的一个。

复制代码 代码如下:

#region 获取二叉树的深度
/// <summary>
/// 获取二叉树的深度
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
/// <returns></returns>
public int bintreelen<t>(chaintree<t> tree)
{
int leftlength;
int rightlength;

if (tree == null)
return 0;

//递归左子树的深度
leftlength = bintreelen(tree.left);

//递归右子书的深度
rightlength = bintreelen(tree.right);

if (leftlength > rightlength)
return leftlength + 1;
else
return rightlength + 1;
}
#endregion

<5> 遍历结点

二叉树中遍历节点的方法还是比较多的，有“先序”，“中序”，“后序”，“按层”，其实这些东西只可意会，不可言传，真的很难在口头

上说清楚，需要反复的体会递归思想。

先序：先访问根，然后递归访问左子树，最后递归右子树。（dlr模式）

中序：先递归访问左子树，在访问根，最后递归右子树。（ldr模式）

后序：先递归访问左子树，然后递归访问右子树，最后访问根。（lrd模式）

按层：这个比较简单，从上到下，从左到右的遍历节点。

复制代码 代码如下:

#region 二叉树的先序遍历
/// <summary>
/// 二叉树的先序遍历
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
public void bintree_dlr<t>(chaintree<t> tree)
{
if (tree == null)
return;

//先输出根元素
console.write(tree.data + "\t");

//然后遍历左子树
bintree_dlr(tree.left);

//最后遍历右子树
bintree_dlr(tree.right);
}
#endregion

#region 二叉树的中序遍历
/// <summary>
/// 二叉树的中序遍历
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
public void bintree_ldr<t>(chaintree<t> tree)
{
if (tree == null)
return;

//优先遍历左子树
bintree_ldr(tree.left);

//然后输出节点
console.write(tree.data + "\t");

//最后遍历右子树
bintree_ldr(tree.right);
}
#endregion

#region 二叉树的后序遍历
/// <summary>
/// 二叉树的后序遍历
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
public void bintree_lrd<t>(chaintree<t> tree)
{
if (tree == null)
return;

//优先遍历左子树
bintree_lrd(tree.left);

//然后遍历右子树
bintree_lrd(tree.right);

//最后输出节点元素
console.write(tree.data + "\t");
}
#endregion

#region 二叉树的按层遍历
/// <summary>
/// 二叉树的按层遍历
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
public void bintree_level<t>(chaintree<t> tree)
{
if (tree == null)
return;

//申请保存空间
chaintree<t>[] treelist = new chaintree<t>[length];

int head = 0;
int tail = 0;

//存放数组
treelist[tail] = tree;

//循环链中计算tail位置
tail = (tail + 1) % length;

while (head != tail)
{
var tempnode = treelist[head];

head = (head + 1) % length;

//输出节点
console.write(tempnode.data + "\t");

//如果左子树不为空,则将左子树存于数组的tail位置
if (tempnode.left != null)
{
treelist[tail] = tempnode.left;

tail = (tail + 1) % length;
}

//如果右子树不为空，则将右子树存于数组的tail位置
if (tempnode.right != null)
{
treelist[tail] = tempnode.right;

tail = (tail + 1) % length;
}
}
}
#endregion

<6> 清空二叉树

虽然c#里面有gc，但是我们能自己释放的就不麻烦gc了，同样清空二叉树节点，我们用到了递归，说实话，这次练习让我喜欢

上的递归，虽然xxx的情况下，递归的不是很好，但是递归还是很强大的。

复制代码 代码如下:

#region 清空二叉树
/// <summary>
/// 清空二叉树
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
public void bintreeclear<t>(chaintree<t> tree)
{
//递的结束点，归的起始点
if (tree == null)
return;

bintreeclear(tree.left);
bintreeclear(tree.right);

//在归的过程中，释放当前节点的数据空间
tree = null;
}
#endregion

最后上一下总的代码

1. usingsystem;
2. usingsystem.collections.generic;
3. usingsystem.linq;
4. usingsystem.text;
8. namespacechaintree
9. {
10. publicclassprogram
11. {
12. staticvoidmain(string[]args)
13. {
14. chaintreemanagermanager=newchaintreemanager();
16. //插入节点操作
17. chaintree<string>tree=createroot();
19. //插入节点数据
20. addnode(tree);
22. //先序遍历
23. console.writeline("\n先序结果为：\n");
24. manager.bintree_dlr(tree);
26. //中序遍历
27. console.writeline("\n中序结果为：\n");
28. manager.bintree_ldr(tree);
30. //后序遍历
31. console.writeline("\n后序结果为：\n");
32. manager.bintree_lrd(tree);
34. //层次遍历
35. console.writeline("\n层次结果为：\n");
36. manager.length=100;
37. manager.bintree_level(tree);
39. console.writeline("\n树的深度为："+manager.bintreelen(tree)+"\n");
41. console.readline();
43. }
45. #region生成根节点
46. ///<summary>
47. ///生成根节点
48. ///</summary>
49. ///<returns></returns>
50. staticchaintree<string>createroot()
51. {
52. chaintree<string>tree=newchaintree<string>();
54. console.writeline("请输入根节点，方便我们生成树\n");
56. tree.data=console.readline();
58. console.writeline("根节点生成已经生成\n");
60. returntree;
61. }
62. #endregion
64. #region插入节点操作
65. ///<summary>
66. ///插入节点操作
67. ///</summary>
68. ///<paramname="tree"></param>
69. staticchaintree<string>addnode(chaintree<string>tree)
70. {
71. chaintreemanagermananger=newchaintreemanager();
73. while(true)
74. {
75. chaintree<string>node=newchaintree<string>();
77. console.writeline("请输入要插入节点的数据：\n");
79. node.data=console.readline();
81. console.writeline("请输入要查找的父节点数据：\n");
83. varparentdata=console.readline();
85. if(tree==null)
86. {
87. console.writeline("未找到您输入的父节点，请重新输入。");
88. continue;
89. }
91. console.writeline("请确定要插入到父节点的：1左侧，2右侧");
93. directiondirection=(direction)enum.parse(typeof(direction),console.readline());
95. tree=mananger.bintreeaddnode(tree,node,parentdata,direction);
97. console.writeline("插入成功，是否继续？1继续，2退出");
99. if(int.parse(console.readline())==1)
100. continue;
101. else
102. break;
103. }
105. returntree;
106. }
107. #endregion
108. }
110. #region插入左节点或者右节点
111. ///<summary>
112. ///插入左节点或者右节点
113. ///</summary>
114. publicenumdirection{left=1,right=2}
115. #endregion
117. #region二叉链表存储结构
118. ///<summary>
119. ///二叉链表存储结构
120. ///</summary>
121. ///<typeparamname="t"></typeparam>
122. publicclasschaintree<t>
123. {
124. publictdata;
126. publicchaintree<t>left;
128. publicchaintree<t>right;
129. }
130. #endregion
132. ///<summary>
133. ///二叉树的操作帮助类
134. ///</summary>
135. publicclasschaintreemanager
136. {
137. #region按层遍历的length空间存储
138. ///<summary>
139. ///按层遍历的length空间存储
140. ///</summary>
141. publicintlength{get;set;}
142. #endregion
144. #region将指定节点插入到二叉树中
145. ///<summary>
146. ///将指定节点插入到二叉树中
147. ///</summary>
148. ///<typeparamname="t"></typeparam>
149. ///<paramname="tree"></param>
150. ///<paramname="node"></param>
151. ///<paramname="direction">插入做左是右</param>
152. ///<returns></returns>
153. publicchaintree<t>bintreeaddnode<t>(chaintree<t>tree,chaintree<t>node,tdata,directiondirection)
154. {
155. if(tree==null)
156. returnnull;
158. if(tree.data.equals(data))
159. {
160. switch(direction)
161. {
162. casedirection.left:
163. if(tree.left!=null)
164. thrownewexception("树的左节点不为空，不能插入");
165. else
166. tree.left=node;
168. break;
169. casedirection.right:
170. if(tree.right!=null)
171. thrownewexception("树的右节点不为空，不能插入");
172. else
173. tree.right=node;
175. break;
176. }
177. }
179. bintreeaddnode(tree.left,node,data,direction);
180. bintreeaddnode(tree.right,node,data,direction);
182. returntree;
183. }
184. #endregion
186. #region获取二叉树指定孩子的状态
187. ///<summary>
188. ///获取二叉树指定孩子的状态
189. ///</summary>
190. ///<typeparamname="t"></typeparam>
191. ///<paramname="tree"></param>
192. ///<paramname="direction"></param>
193. ///<returns></returns>
194. publicchaintree<t>bintreechild<t>(chaintree<t>tree,directiondirection)
195. {
196. chaintree<t>childnode=null;
198. if(tree==null)
199. thrownewexception("二叉树为空");
201. switch(direction)
202. {
203. casedirection.left:
204. childnode=tree.left;
205. break;
206. casedirection.right:
207. childnode=tree.right;
208. break;
209. }
211. returnchildnode;
212. }
214. #endregion
216. #region获取二叉树的深度
217. ///<summary>
218. ///获取二叉树的深度
219. ///</summary>
220. ///<typeparamname="t"></typeparam>
221. ///<paramname="tree"></param>
222. ///<returns></returns>
223. publicintbintreelen<t>(chaintree<t>tree)
224. {
225. intleftlength;
226. intrightlength;
228. if(tree==null)
229. return0;
231. //递归左子树的深度
232. leftlength=bintreelen(tree.left);
234. //递归右子书的深度
235. rightlength=bintreelen(tree.right);
237. if(leftlength>rightlength)
238. returnleftlength+1;
239. else
240. returnrightlength+1;
241. }
242. #endregion
244. #region判断二叉树是否为空
245. ///<summary>
246. ///判断二叉树是否为空
247. ///</summary>
248. ///<typeparamname="t"></typeparam>
249. ///<paramname="tree"></param>
250. ///<returns></returns>
251. publicboolbintreeisempty<t>(chaintree<t>tree)
252. {
253. returntree==null?true:false;
254. }
255. #endregion
257. #region在二叉树中查找指定的key
258. ///<summary>
259. ///在二叉树中查找指定的key
260. ///</summary>
261. ///<typeparamname="t"></typeparam>
262. ///<paramname="tree"></param>
263. ///<paramname="data"></param>
264. ///<returns></returns>
265. publicchaintree<t>bintreefind<t>(chaintree<t>tree,tdata)
266. {
267. if(tree==null)
268. returnnull;
270. if(tree.data.equals(data))
271. returntree;
273. returnbintreefind(tree,data);
274. }
275. #endregion
277. #region清空二叉树
278. ///<summary>
279. ///清空二叉树
280. ///</summary>
281. ///<typeparamname="t"></typeparam>
282. ///<paramname="tree"></param>
283. publicvoidbintreeclear<t>(chaintree<t>tree)
284. {
285. //递的结束点，归的起始点
286. if(tree==null)
287. return;
289. bintreeclear(tree.left);
290. bintreeclear(tree.right);
292. //在归的过程中，释放当前节点的数据空间
293. tree=null;
294. }
295. #endregion
297. #region二叉树的先序遍历
298. ///<summary>
299. ///二叉树的先序遍历
300. ///</summary>
301. ///<typeparamname="t"></typeparam>
302. ///<paramname="tree"></param>
303. publicvoidbintree_dlr<t>(chaintree<t>tree)
304. {
305. if(tree==null)
306. return;
308. //先输出根元素
309. console.write(tree.data+"\t");
311. //然后遍历左子树
312. bintree_dlr(tree.left);
314. //最后遍历右子树
315. bintree_dlr(tree.right);
316. }
317. #endregion
319. #region二叉树的中序遍历
320. ///<summary>
321. ///二叉树的中序遍历
322. ///</summary>
323. ///<typeparamname="t"></typeparam>
324. ///<paramname="tree"></param>
325. publicvoidbintree_ldr<t>(chaintree<t>tree)
326. {
327. if(tree==null)
328. return;
330. //优先遍历左子树
331. bintree_ldr(tree.left);
333. //然后输出节点
334. console.write(tree.data+"\t");
336. //最后遍历右子树
337. bintree_ldr(tree.right);
338. }
339. #endregion
341. #region二叉树的后序遍历
342. ///<summary>
343. ///二叉树的后序遍历
344. ///</summary>
345. ///<typeparamname="t"></typeparam>
346. ///<paramname="tree"></param>
347. publicvoidbintree_lrd<t>(chaintree<t>tree)
348. {
349. if(tree==null)
350. return;
352. //优先遍历左子树
353. bintree_lrd(tree.left);
355. //然后遍历右子树
356. bintree_lrd(tree.right);
358. //最后输出节点元素
359. console.write(tree.data+"\t");
360. }
361. #endregion
363. #region二叉树的按层遍历
364. ///<summary>
365. ///二叉树的按层遍历
366. ///</summary>
367. ///<typeparamname="t"></typeparam>
368. ///<paramname="tree"></param>
369. publicvoidbintree_level<t>(chaintree<t>tree)
370. {
371. if(tree==null)
372. return;
374. //申请保存空间
375. chaintree<t>[]treelist=newchaintree<t>[length];
377. inthead=0;
378. inttail=0;
380. //存放数组
381. treelist[tail]=tree;
383. //循环链中计算tail位置
384. tail=(tail+1)%length;
386. while(head!=tail)
387. {
388. vartempnode=treelist[head];
390. head=(head+1)%length;
392. //输出节点
393. console.write(tempnode.data+"\t");
395. //如果左子树不为空,则将左子树存于数组的tail位置
396. if(tempnode.left!=null)
397. {
398. treelist[tail]=tempnode.left;
400. tail=(tail+1)%length;
401. }
403. //如果右子树不为空，则将右子树存于数组的tail位置
404. if(tempnode.right!=null)
405. {
406. treelist[tail]=tempnode.right;
408. tail=(tail+1)%length;
409. }
410. }
411. }
412. #endregion
414. }
415. }

我们把文章开头的“二叉树”的节点输入到我们的结构中，看看遍历效果咋样。