树
其实最初之所以会想看看数据结构，就是为了了解树，图，和一些算法。前面的数组、链表、字符串之类的，自己还是了解些的。现在到树了，挺开心的。
树型结构是一种以分支关系定义的层次结构，是应用十分广泛和重要的非线性数据结构（我都从来没用上唉。。。）。
在现实生活中的很多问题，比如人类的家族关系，动植物的分类，行政隶属关系，都可以按照层次表示成树的形式（这倒是）。
树是N个结点的有限集合T，在一颗非空树中有且仅有一个称做根的结点（这么说有根结点就可以找到所有的结点了）：其余的结点可分为m棵树。当n=0时，称为空树。树的概念还是找张图来比较容易懂，这里不好贴图，就不贴了。
（1）结点的度数（度数。这名词，不知道还以为是眼镜的度数呢）
树中每个结点具有的子树或后继结点数成为该结点的度数（degree），其实我觉得可以说是儿女数，父母所有的儿女的数目。
（2）树的深度：类比与上面的，那就是家庭的代（多少代人的意思）数。
（3）森林：n个树的集合（⊙﹏⊙b汗，这名字取的）。
（4）二叉树：也叫二分树，二元树，对分树（外号真多，干脆叫二树），是树形结构中最常见的类型。二叉树的定义去看个图就知道，这里不写了。注意的是二叉树可不是简单的等于度数不超过2的树（你不明白这句话的意思吗？查书去）。
（5）在一个二叉树中，若第i层的结点数为2的i-1次幂，则称此层的结点是满的，每一层都是满的，则称为满二叉树（那总共有多少个结点嘞？深度为i的话 2的i次幂-1个结点）。
（6）完全二叉树：如果一个二叉树各层都是满的，唯独最下面的一层从右边起连续缺失N个结点，这种树叫做完全二叉树（干吗要定义这个树？？？）。
对于完全二叉树，对其结点采用“按层编号”比较方便，即从根结点开始由上而下逐层给结点编号，同一层的结点由左向右编号（有点明白干嘛要定义这个树了）。
（7）完全二叉树的一些特征（要好好体会下哦）：
1 如果i=1，则它是整个树的根结点，无父结点；i>1，则其父结点编号为[i/2];
2 如果2in，则无左儿子结点；
3 如果(2i+1)
（8）二叉树的存储结构（嗯，我一直想知道这个问题）：
二叉树通常有两种存储结构：顺序存储结构与链式存储结构（怎么每个都是这两种，⊙﹏⊙b汗）。
二叉树的顺序存储结构就是用一个一维数组来存储二叉树的各个结点（秒素完全二叉树特征的时候，应该就会想到可以用一维数组来存储吧）。这种存储结构适合于完全二叉树和满二叉树（这个很好理解）。
链式存储结构： left指针+data域+right指针。 这种结构的缺点是什么？就是只能从父到子，无法从子到父。
（9）普通二叉树与二叉树的转换
这个转换的思路还是蛮巧妙的，不过不难，大家可以先想想，没想到的话，再查查书吧。现在有点懒，不想抄。
（10）二叉树的遍历
遍历的次序有6种，我们通常用的是三种，前序，中序，后序。
算法的话，分为递归和非递归的。递归的很好理解。非递归的采用的是堆栈，堆栈存的是结点的右指针，具体也不想抄了。。。。。
（11）线索二叉树：这种二叉树结点的结构是left+Itag+data+Rtag+rigth.多出来的哪两个是什么东西呢？大家可以先猜猜。
Itag为0时，left域指向其左儿子结点的指针，为1时，指向其前驱结点的左线索；
Rtag为0时，rigth域指向其右儿子结点的指针，为1时，指向其后继结点的右线索。
线索二叉树的前驱后继结点的不同，跟你采用的遍历方式有关系（前序，后序，中序）。一般是一边中序遍历一边建立线索。
线索化后，查找后继结点 和前驱结点的过程就容易了，这样遍历起来也就容易了。具体代码，不想写了，现在好不想写东西。。
（12）树的应用：
有：二叉树的排序 二叉排序树。
哈夫曼树：这个很有意思，哈夫曼编码实现数据压缩，真的很强大，哈夫曼真是个聪明的人，因为如果要抄下来的话，会很多，我现在很懒。。。不说了，想知道的自己看看书，查查资料吧。
阅读(1043) | 评论(0) | 转发(0) |
