从小白开始自学数据结构——第九天【树的基本概念和定义】

         树分类
             一般树
                 任意一个结点的子结点的个数都不受限制
             二叉树
                 任意一个结点的子结点个数最多两个，且子结点的位置不可更改                                     
                 分类：
                     一般二叉树

                     满二叉树
                         在不增加树的层数的情况下，无法多添加一个结点的二叉树。
                     完全二叉树
                         如果只是删除了满二叉树最底层最右边连续若干个结点
                             这样形成的完全二叉树

                     满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

             森林
                 m(M>=0)棵互不相交的树的集合 

         树的存储
             二叉树的存储
                 连续存储【完全二叉树】
                     优点：
                         查找某个结点的双亲结点和子结点（判断有没有子结点）速度很快
                     缺点：
                         内存耗用空间过大

                 链式存储

             一般树的存储
                 双亲表示法
                     求父结点方便
                 孩子表示法
                     求子结点方便
                 双亲孩子表示法
                     求子结点和父结点都很方便，但是操作困难
                 二叉树表示法
                     把一个普通树转换成二叉树来存储
                     具体转换方法： 
                         设法保证任意一个结点的
                             左指针域指向他的第一个孩子
                             右指针域指向他的兄弟
                                 只要能满足条件，就可以把一个普通书转化为二叉树
                 （到这里我有点想吐）

             森林的存储
                 先把森林转换为二叉树，再存储二叉树。


         树操作
             遍历
                先序遍历
                    先访问根结点
                    再先序访问左子树
                    再先序访问右子树

                中序遍历
                    中序遍历左子树
                    再访问根结点
                    再中序遍历右子树 

                后序遍历
                    中序遍历左子树
                    中序遍历右子树
                    再访问根结点