数据结构第一回合：树

         不管是数据结构导论中还是软考中，树都是一个很重要的部分，相对来讲数据结构导论比软考中要讲的相对详细，下面我就结合例题对这部分进行一下整合：

          总的来说，结构如下：

         概述部分都是一些基本概念和性质的阐释，森林和二叉树都特殊形式的树，判定树和哈弗曼树本质作为树的同时，也可以作为树的应用，运用树（包括二叉树）的基本知识描述和解决一些实际的问题  。下面就依次来看：

一、二叉树

       1. 【概况】

           二叉树有满，完全、非完全三种情况。所谓满二叉树就是一个子结点都不差，所有的位置该有的都有，如图：

         这样一个都不缺的是满的，假设现在该二叉树中缺少了4这一个子结点，那么就是完全二叉树，而如果2、4存在，7或者5的位置空了，那么就由一个完全变成不完全了。

完全二叉树和非完全二叉树的区别就是：有缺失的那一层，子结点的存在是否连续。

       【例题分析】（出自《数据结构导论》125页 填空第4题）

         已知完全二叉树的第7层有20个结点，则整个完全二叉树的叶子结点个数是______.

        [解析] ：因为是一个完全二叉树，所以在树的最后一层一定有缺失，也就是说结点的个数小于2 的（n-1）次方个。而第6层一 定是满的，一共有32 个结点。而根据题意该

                        树一共有7层，而且根据完全二叉树的性质，这20个结点是第6层的10结点中的子结点数。而第六层剩下的22个结点都是叶子结点。

                        所以，该树的叶子结点一共有20+22=42个。

 2、树和二叉树之间的转换

         在这里咱们用图说话，这里说的明白。

         1）先将树上所有的兄弟进行连接，得到原图右边的图：

         2）再保留每一层的兄弟结点中的第一个作为该层的左子树结点，断开C、D与根结点的连线，直接将B、C、D作为一条线，以B为中心顺时针向旋转45度角，这样就得到下面的图：

       其实可以这样归结：当所有的兄弟结点进行连线以后，每一层的所有兄弟结点中左边的第一个都作为所有兄弟结点的父结点，其他的兄弟结点保持队形，以该结点为中心进行旋转，这样就得出最终的二叉树。

二、森林

         森林可以看作实实在在的树的虚拟化，也是多棵树组成的。这里知识点主要是和二叉树之间的转换

         森林和二叉树之间的转换实际上是对树和二叉树之间转换的一种扩展，当将各个树转换为各自对应的二叉树后，将所有的根结点作为兄弟进行连接，而实现二叉树到森林的转换就是一个逆过程，这里就不再赘述。

         这本数据结构第一遍看的挺乱，听难的，翻开一看不是图就是字母，顿时感觉全世界都被这两个东西充斥了。但终究“眼是狗熊，手是英雄”，所以在学习的同时我总结了数据结构的一点学习技巧：

      1.实例化

            “此实例化非彼实例化”，这里主要是融入生活，用生活中常见的熟悉的事物来代替或者是帮助理解这些抽象的，空旷的理论结构。

      2.手脑并用            

              这门课中很多知识点都需要另外的思路图来辅助理解，比如树、图、或者指针的指向。这就要求我们手脑并用，用纸上的图来帮我们理解和解决。

      3.沉心

             面对那些庞杂的专业名词，丰富的树图都不要畏惧，免得自己心沉。为了不让自己心沉就必须沉心，要是能闹明白这两个词，那你就"沉心"了:静下心仔细想想好好理理，其实问题都不是问题。

          这门数据结构就是一个纸猫，因为它连老虎也不算，大家加油！

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠