数据结构之树

树：非线性结构——————其实更像是一串葡萄，哈哈

　　定义：

　　　　专业定义：

　　　　　　1、有且只有一个成为根节点；

　　　　　　2、有若干个互不相交的的子树，这些子树本身也是一颗树；

　　　　通俗的定义：

　　　　　　1、树是由节点和边（指针域）组成；

　　　　　　2、每个节点只有一个父节点，但可以有很多个子节点；

　　　　　　3、但有一个节点例外，该节点没有父节点，此节点成为根节点；

　　　涉及的术语：

　　　　节点，　父节点，　子节点，　子孙， 堂兄弟；

　　　　深度：从根节点到最底层节点的层数称之为深度；

　　　　叶子节点：没有子节点的节点

　　　　非终端节点：实际就是非叶子节点

　　　　度：子节点的个数；

　　　　树的度：子节点的个数数目中最大值；

　　树分类：

　　　　一般树：任意一个子节点的个数的都不受限制；

　　　　二叉树；任意一个节点的字节点的个数最多两个，且子节点的位置不可改变；

　　　　　　　一般二叉树

　　　　　　　满二叉树：在不增加树层数的前提下，无法再多添加一个节点的二叉树；

　　　　　　　完全二叉树（重点）：如果只是删除了满二叉树最底层右边的连续若干个节点。这样形成的二叉树；

　　　  森林：n个互不相交的树的集合；

树的存储：

　　二叉树的存储（重点）：（一般二叉树转成完全二叉树来存储？原因是树是非线性的，而我们要线性的保存它，所以要将非线性转成线性来存储）

　　　　连续存储【完全二叉树】：

　　　　　　优点：查找某个节点的父节点和子节点（包括查找某个节点有没有子节点）

　　　　　　缺点：耗用内存空间过大；

　　　　链式存储：

　　　　　　（每个节点分三块）

　　一般树的存储：

　　　　双亲表示法，孩子表示法，双亲孩子表示法，

　　　　二叉树表示法：

　　　　　　把一个普通树转化成二叉树来储存，具体转换方法：设法保证任意一个节点的左指针域指向它的第一个孩子，右指针域指向它的兄弟；

　　　　　　通过此办法，就可以将一颗树转化为二叉树；

·　　　　　　一个普通树转化成的二叉树一定没有右子树；

 　　　　　　如下图所示：

　　森林的存储：

　　　　转化为二叉树储存；规则如同普通树转化成二叉树一致；（每棵树根节点为兄弟节点）

　　　　如下图所示：

 霍夫曼树：每个节点要么没有子节点，要么有两个子节点；