数据结构之---树

秒速五厘米 2022-09-23 08:10 220阅读 0赞

作者：egg

邮箱：xtfggef@gmail.com

微博：[http://weibo.com/xtfggef][http_weibo.com_xtfggef]

博客：[http://blog.csdn.net/zhangerqing][http_blog.csdn.net_zhangerqing]（转载请说明出处）

我们接着上一篇数据结构继续讲解。本章系数据结构之树与二叉树，从这章开始，我们就要介绍非线性结构了，这些内容理解起来比线性表稍难一些，我尽量写的通俗一些，如果读的过程中有任何问题，请按上述方式联系我！

一、树

树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。本章重点讨论二叉树的存储表示及其各种运算，并研究一般树和森林与二叉树的转换关系，最后介绍树的应用实例。

二、二叉树

二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。关于更多概念，请大家自己上网查询，我们这里将用代码实现常见的算法。更多的概念，请访问：http://student.zjzk.cn/course\_ware/data\_structure/web/SHU/shu6.2.3.1.htm。

1、二叉树的建立

首先，我们采用广义表建立二叉树（关于广义表的概念，请查看百科的介绍：http://baike.baidu.com/view/203611.htm）

我们建立一个字符串类型的广义表作为输入：

**String  expression = "A(B(D(,G)),C(E,F))";与该广义表对应的二叉树为：------广义表----二叉树的表示方法**

![1366533767_1515.jpg][]

写代码前，我们通过观察二叉树和广义表，先得出一些结论：

*  每当遇到字母，将要创建节点  
    
 *  每当遇到“（”，表面要创建左孩子节点
 *  每当遇到“，”，表明要创建右孩子节点
 *  每当遇到“）”，表明要返回上一层节点
 *  广义表中“（”的数量正好是二叉树的层数

根据这些结论，我们基本就可以开始写代码了。首先建议一个节点类（这也属于一种自定义的数据结构）。

**\[java\]**  [view plain][]   [copy][view plain]

1.  **package** com.xtfggef.algo.tree;  
2.    
3.  **public** **class** Node \{  
4.    
5.      **private** **char** data;  
6.      **private** Node lchild;  
7.      **private** Node rchild;  
8.    
9.      **public** Node()\{  
10.           
11.     \}  
12.     **public** **char** getData() \{  
13.         **return** data;  
14.     \}  
15.   
16.     **public** **void** setData(**char** data) \{  
17.         **this**.data = data;  
18.     \}  
19.   
20.     **public** Node getRchild() \{  
21.         **return** rchild;  
22.     \}  
23.   
24.     **public** **void** setRchild(Node rchild) \{  
25.         **this**.rchild = rchild;  
26.     \}  
27.   
28.     **public** Node getLchild() \{  
29.         **return** lchild;  
30.     \}  
31.   
32.     **public** **void** setLchild(Node lchild) \{  
33.         **this**.lchild = lchild;  
34.     \}  
35.   
36.     **public** Node(**char** ch, Node rchild, Node lchild) \{  
37.         **this**.data = ch;  
38.         **this**.rchild = rchild;  
39.         **this**.lchild = lchild;  
40.     \}  
41.   
42.     **public** String toString() \{  
43.         **return** "" + getData();  
44.     \}  
45. \}

根据广义表创建二叉树的代码如下：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **public** Node createTree(String exp) \{  
2.          Node\[\] nodes = **new** Node\[3\];  
3.          Node b, p = **null**;  
4.          **int** top = -1, k = 0, j = 0;  
5.          **char**\[\] exps = exp.toCharArray();  
6.          **char** data = exps\[j\];  
7.          b = **null**;  
8.          **while** (j < exps.length - 1) \{  
9.              **switch** (data) \{  
10.             **case** '(':  
11.                 top++;  //top 层数
12.                 nodes\[top\] = p;  
13.                 k = 1;  //1 left child,2 right child
14.                 **break**;  
15.             **case** ')':  
16.                 top--;  
17.                 **break**;  
18.             **case** ',':  
19.                 k = 2;  
20.                 **break**;  
21.             **default**:  
22.                 p = **new** Node(data, **null**, **null**);  
23.                 **if** (b == **null**) \{  
24.                     b = p;  
25.                 \} **else** \{  
26.                     **switch** (k) \{  
27.                     **case** 1:  
28.                         nodes\[top\].setLchild(p);  
29.                         **break**;  
30.                     **case** 2:  
31.                         nodes\[top\].setRchild(p);  
32.                         **break**;  
33.                     \}  
34.                 \}  
35.             \}  
36.             j++;  
37.             data = exps\[j\];  
38.         \}  
39.         **return** b;  
40.     \}

思路不难，结合上述的理论，自己断点走一遍程序就懂了！

2、二叉树的递归遍历

二叉树的遍历有三种：先序、中序、后序，每种又分递归和非递归。递归程序理解起来有一定的难度，但是实现起来比较简单。对于上述二叉树，其：

a 先序遍历

A B D G C E F

b 中序遍历

D G B A E C F

c 后序遍历

G D B E F C A

先、中、后序递归遍历如下：

**\[java\]**  [view plain][]   [copy][view plain]

1.  /\*\* 
2.       \* pre order recursive 
3.       \*  
4.       \* @param node 
5.       \*/  
6.      **public** **void** PreOrder(Node node) \{  
7.          **if** (node == **null**) \{  
8.              **return**;  
9.          \} **else** \{  
10.             System.out.print(node.getData() + " ");  
11.             PreOrder(node.getLchild());  
12.             PreOrder(node.getRchild());  
13.   
14.         \}  
15.     \}  
16.   
17.     /\*\* 
18.      \* in order recursive 
19.      \*  
20.      \* @param node 
21.      \*/  
22.     **public** **void** InOrder(Node node) \{  
23.         **if** (node == **null**) \{  
24.             **return**;  
25.         \} **else** \{  
26.             InOrder(node.getLchild());  
27.             System.out.print(node.getData() + " ");  
28.             InOrder(node.getRchild());  
29.         \}  
30.     \}  
31.   
32.     /\*\* 
33.      \* post order recursive 
34.      \*  
35.      \* @param node 
36.      \*/  
37.     **public** **void** PostOrder(Node node) \{  
38.         **if** (node == **null**) \{  
39.             **return**;  
40.         \} **else** \{  
41.             PostOrder(node.getLchild());  
42.             PostOrder(node.getRchild());  
43.             System.out.print(node.getData() + " ");  
44.         \}  
45.     \}

二叉树的递归遍历实现起来很简单，关键是非递归遍历有些难度，请看下面的代码：

3、二叉树的非递归遍历

先序非递归遍历：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **public** **void** PreOrderNoRecursive(Node node) \{  
2.          Node nodes\[\] = **new** Node\[CAPACITY\];  
3.          Node p = **null**;  
4.          **int** top = -1;  
5.          **if** (node != **null**) \{  
6.              top++;  
7.              nodes\[top\] = node;  
8.              **while** (top > -1) \{  
9.                  p = nodes\[top\];  
10.                 top--;  
11.                 System.out.print(p.getData() + " ");  
12.                 **if** (p.getRchild() != **null**) \{  
13.                     top++;  
14.                     nodes\[top\] = p.getRchild();  
15.                 \}  
16.                 **if** (p.getLchild() != **null**) \{  
17.                     top++;  
18.                     nodes\[top\] = p.getLchild();  
19.                 \}  
20.             \}  
21.         \}  
22.     \}

原理：利用一个栈，先序遍历即为根先遍历，先将根入栈，然后出栈，凡是出栈的元素都打印值，入栈之前top++，出栈之后top--，利用栈后进先出的原理，右节点先于左节点进栈，根出栈后，开始处理左子树，然后是右子树，读者朋友们可以自己走一遍程序看看，也不算难理解！

中序非递归遍历：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **public** **void** InOrderNoRecursive(Node node) \{  
2.          Node nodes\[\] = **new** Node\[CAPACITY\];  
3.          Node p = **null**;  
4.          **int** top = -1;  
5.          **if** (node != **null**)  
6.              p = node;  
7.          **while** (p != **null** || top > -1) \{  
8.              **while** (p != **null**) \{  
9.                  top++;  
10.                 nodes\[top\] = p;  
11.                 p = p.getLchild();  
12.             \}  
13.             **if** (top > -1) \{  
14.                 p = nodes\[top\];  
15.                 top--;  
16.                 System.out.print(p.getData() + " ");  
17.                 p = p.getRchild();  
18.             \}  
19.         \}  
20.     \}

原理省略。

后续非递归遍历：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **public** **void** PostOrderNoRecursive(Node node) \{  
2.          Node\[\] nodes = **new** Node\[CAPACITY\];  
3.          Node p = **null**;  
4.          **int** flag = 0, top = -1;  
5.          **if** (node != **null**) \{  
6.              **do** \{  
7.                  **while** (node != **null**) \{  
8.                      top++;  
9.                      nodes\[top\] = node;  
10.                     node = node.getLchild();  
11.                 \}  
12.                 p = **null**;  
13.                 flag = 1;  
14.                 **while** (top != -1 && flag != 0) \{  
15.                     node = nodes\[top\];  
16.                     **if** (node.getRchild() == p) \{  
17.                         System.out.print(node.getData() + " ");  
18.                         top--;  
19.                         p = node;  
20.                     \} **else** \{  
21.                         node = node.getRchild();  
22.                         flag = 0;  
23.                     \}  
24.                 \}  
25.             \} **while** (top != -1);  
26.         \}  
27.     \}

三、树与二叉树的转换

本人之前总结的：

![1366546744_5122.JPG][]

这部分概念的其他知识，请读者自己上网查看。

作者：egg

邮箱：xtfggef@gmail.com

微博：[http://weibo.com/xtfggef][http_weibo.com_xtfggef]

博客：[http://blog.csdn.net/zhangerqing][http_blog.csdn.net_zhangerqing]（转载请说明出处）

[http_weibo.com_xtfggef]: http://weibo.com/xtfggef
[http_blog.csdn.net_zhangerqing]: http://blog.csdn.net/zhangerqing
[1366533767_1515.jpg]: https://img-my.csdn.net/uploads/201304/21/1366533767_1515.jpg
[view plain]: http://blog.csdn.net/zhangerqing/article/details/8822476#
[1366546744_5122.JPG]: https://img-my.csdn.net/uploads/201304/21/1366546744_5122.JPG