数据结构之树结构详解

树的定义

树是一种很特别的数据结构，树这种数据结构叫做“树”就是因为它长得像一棵树。但是这棵树画成的图长得却是一棵倒着的树，根在上，叶在下。

树是图的一种，树和图的区别就在于：树是没有环的，而图是可以有环的。

树的百度定义如下：

树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

结合图来看，可能会更好理解

这就是一棵典型的二叉树

而这里，2,3共有子节点5，那么上图就不是树了。

和树有关的术语

节点的度：一个节点含有的子树的个数称为该节点的度；

叶节点：度为0的节点称为叶节点；

分支节点：度不为0的节点；

父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；

子节点：一个节点含有的子树的根节点称为该节点的子节点；

兄弟节点：具有相同父节点的节点互称为兄弟节点；

树的度：一棵树中，最大的节点的度称为树的度；

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次；

堂兄弟节点：双亲在同一层的节点互为堂兄弟；

节点的祖先：从根到该节点所经分支上的所有节点；

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

森林：由m（m>=0）棵互不相交的树的集合称为森林；

我们以图为样例来看：

树的表现方法

树一共有三种表现方法，分别是图像表现法、符号表现法和遍历表现法

图像表现法

图像表现法是所有的树的表现方法中最常见，也最简单的一种，由于上文已经详细介绍过，这里不做太多解释。

符号表现法

符号表现法没有其它两种方法那么常见，但是更为实用，特别是在比赛中输入时不能输入图片，那么可以用到符号表现法

同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上文中的图就可以表现为;

(1(2(6,7(14),8(15(19))),3(9(16)),4(10,11(17(20)),12),5(13(18(21)))))

遍历表现法

遍历表现法是二叉树特有的一种遍历，下面将会详细介绍：

二叉树简介

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为log2(n+1)。深度为k的完全二叉树，至少有2k-1个节点，至多有2k-1个节点。

——百度百科

特殊的二叉树

上图为一棵普通的二叉树，既然这种二叉树是“普通”的，那么就有“特殊”的二叉树

完全二叉树

如果一个二叉树与满二叉树前m个节点的结构相同，这样的二叉树被称为完全二叉树

下图就是一棵完全二叉树

满二叉树

满二叉树是“特殊中的特殊”，它属于完全二叉树中的一种，既然叫满二叉树，它就是满的二叉树，为什么这么讲呢？它的定义如下：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

下图为一棵满二叉树

二叉树的遍历

回到二叉树的前序、中序、后序遍历。

在正式开始讲之前，读者可以先记住下面一句话，然后在阅读的过程中比较这三种遍历的区别，就会理解得更加深刻了：

前序遍历是中左右，中序遍历是左中右，后序遍历是左右中，所以这三种遍历的区别就是父亲节点什么时候访问

前序遍历

首先访问根，再先序遍历左子树，最后先序遍历右子树

这句话凭空想象很难懂，我们可以借助图来理解。

例如上图，我们按照前序遍历的方法，先遍历根节点，输出根节点的编号

然后遍历根节点的左子树，输出左子树编号，然后重复此循环，直到遇到了叶节点

这时候我们发现没有左子树了！怎么办呢？遇到叶子节点，我们就返回到它的父亲的循环，然后对它父亲的右子树进行访问

结果发现它的父亲没有右子树！

那么我们继续返回，因为叶子节点7的父亲6也是节点4的左孩子，所以我们继续返回，直到遇到了右子树为止

我们访问到了第二个节点，终于遇到了有右子树的了，这是我们对右子树进行访问，并重复以上步骤，直到访问过所有的点为止。

什么？你觉得这个访问步骤有些熟悉？没错，这和DFS（深度优先搜索）的访问步骤非常相似！

现在读者应该明白了“前序遍历是中左右”的意思了，先访问中间的节点，即根节点（一般来说，在一个用图来表现的树中，将根节点放置与左右节点的中间的上方，所以形象地称为中节点，当然，读者也可以称为“根左右”），再访问左右子树。那么类似的，读者也应该明白了中序遍历和后序遍历了。

中序遍历

首先中序遍历左子树，再访问根，最后中序遍历右子树

由于读者们看完前序遍历之后，应该懂得中序遍历是怎样的了，这里就不做和前序遍历一样详细的步骤了：

首先，遍历根节点1的左子树2，发现2有左子树，那么就遍历2的左子树4，直到遇到了没有左子树的节点7，这时输出7

遍历7的根节点6，输出。

发现6没有右子树，那么我们遍历6的根节点4，输出

节点4的根节点2有右子树，遍历节点2的右子树。

重复以上循环直到所有点被访问完为止。

特别提醒：在8和9的访问顺序中，读者可能有一些疑问：8没有左子树怎么办？8没有左子树，那么我们就到下一步，访问根节点，所以这时我们应该先访问8再访问9.

后序遍历

实际上，明白了前两种遍历后，读者应该可以自己遍历出后序遍历了，所以这里只给出树和后序遍历，供读者参考

代码

这里给出前序遍历、中序遍历和后序遍历的代码，比较容易理解，就不多解释

先设置一个结构体来保存tree节点

structTree

{

intdata; //节点值

Tree *lchild ,*rchild; //分别为左孩子有孩子

};

前序遍历：

voidpreorder_traversal(tree root)

{

if(root.data== NULL)

return;

printf( “%d”, root.data);

preorder_traversal(root.lchild);

preorder_traversal(root.rchild);

}

中序遍历:

voidinorder_traversal(tree root)

{

if(root.data== NULL)

return;

inorder_traversal(root.lchild);

printf( “%d”, root.data);

inorder_traversal(root.rchild);

}

后序遍历：

voidpostorder_traversal(tree root)

{

if(root.data== NULL)

return;

postorder_traversal(root.lchild);

postorder_traversal(root.rchild);

printf( “%d”, root.data);

}