树的基础知识

树

            树定义

                    专业定义：

                      1、有且只有一个称为根的节点

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

                     

                    通俗定义：

                        1、树是由节点和边组成

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

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

               

                    专业术语

                        节点    父节点      子节点

                        子孙    堂兄弟     

                        深度：

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

                            根节点是第一层

                        叶子节点；（叶子就不能劈叉了）

                            没有子节点的节点

                        非终端节点：

                            实际就是非叶子节点。

                        根节点既可以是叶子也可以是非叶子节点

                        度：

                            子节点的个数称为度。（一棵树看最大的）          

            树分类：

                一般树

                    任意一个节点的子节点的个数都不受限制

                二叉树（有序树）

                    任意一个节点的子节点的个数最多两个，且子节点

                    的位置不可更改。

                   

                    分类：

                        一般二叉树

                        满二叉树

                            在不增加树的层数的前提下。无法再多

                            添加一个节点的二叉树就是满二叉树。

                        完全二叉树

                            如果只是删除了满二叉树最底层最右边的

                            连续若干个节点，这样形成的二叉树就是

                            完全二叉树。

                       

                森林

                    n个互不相交的树的集合

 

 

一般的二叉树要以数组的方式存储，要先转化成完全二叉树，因为如果你

只存有效节点（无论先序，中序，后序），则无法知道这个树的组成方式

是什么样子的。

 

                   

            树的存储（都是转化成二叉树来存储）

                二叉树的存储

                    连续存储【完全二叉树】

                        优点：

                            查找某个节点的父节点和子节点（也包括判断有咩有）速度很快

                        缺点：

                            耗用内存空间过大

                   

                    链式存储

                   

                一般树的存储

                    双亲表示法

                        求父节点方便

                    孩子表示法

                        求子节点方便

                    双亲孩子表示法

                        求父节点和子节点都很方便

                    二叉树表示法

                        把一个普通树转化成二叉树来存储

                        具体转换方法：

                            设法保证任意一个节点的

                                左指针域指向它的第一个孩子

                                有指针域指向它的下一个兄弟

                            只要能满足此条件，就可以把一个普通树转化成二叉树

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

                       

               

                森林的存储

                    先把森林转化为二叉树，再存储二叉树，具体方式为：根节点

                    之间可以当成是兄弟来看待

               

            二叉树操作

                遍历

                     

                      先序遍历【先访问根节点】

                            先访问根节点

                            再先序访问左子树

                            再先序访问右子树

                     

                      中序遍历【中间访问根节点】

                            中序遍历左子树

                            再访问根节点

                            再中序遍历右子树

                           

                      后序遍历【最后访问根节点】

                            先后序遍历左子树

                            再后序遍历右子树

                            再访问根节点

                     

                  已知两种遍历序列求原始二叉树

                        通过先序和中序 或者 中序和后续我们可以

                        还原出原始的二叉树

                        但是通过先序和后续是无法还原出原始的二叉树的

                       

                        换种说法：

                            只有通过先序和中序， 或通过中序和后序

                            我们才可以唯一的确定一个二叉树               

                 

                应用

                    树是数据库中数据组织的一种重要形式（例如图书馆

                    的图书分类一层一层往下分。）

                    操作系统子父进程的关系本身就是一棵树

                    面向对象语言中类的继承关系本身就是一棵树

 

                    赫夫曼树（树的一个特例）