大话数据第五天

六、 树

树是n个结点的有限集&＃xff0c;n&＃61;0时称为空树。

任意一棵非空树中&＃xff1a;

1. 有且仅有一个特定的称为根的结点
2. 当n>1时&＃xff0c;其余结点可分为m个互不相交的有限集T1、T2...Tm&＃xff0c;每一个集合本身又是一棵树&＃xff0c;称为子树

结点分类

度&＃xff1a;结点拥有的子树数称为结点的度

1. 根结点
2. 叶结点

树的表示方法

双亲表示法&＃xff1a;一组连续空间存储树的结点&＃xff0c;同时在每个结点中&＃xff0c;附设一个指示器指示其双亲结点到链表的位置

data是数据域&＃xff0c;parent是指针域

上述结构如果要知道结点的孩子是什么&＃xff0c;就需要遍历整个结构才行

增加一个结点最左边的域(相当于长子)&＃xff0c;如果没有孩子的结点&＃xff0c;这个长子域就设置为-1

但是长子表示了出来&＃xff0c;还有次子&＃xff0c;次次子。。。及兄弟关系为表示出来

那就增加一个右兄弟域来体现兄弟关系&＃xff0c;也就是说&＃xff0c;每一个结点如果存在右兄弟&＃xff0c;则记录下右兄弟的下标,不存在设为-1

孩子表示法&＃xff1a;每个结点有多个指针域&＃xff0c;其中每个指针指向一棵子树的根结点--多重链表表示法

方案一&＃xff1a;树的度是树各个结点度的最大值     浪费大量的空间

方案二&＃xff1a;取一个位置来存放结点的度&＃xff0c;节省空间   每个结点的链表是不同的结构&＃xff0c;浪费时间

最终的孩子表示法&＃xff1a;把每个孩子结点排列起来&＃xff0c;以单链表作存储结构&＃xff0c;则n个结点有n个孩子链表&＃xff0c;如果是叶子结点则此单链表为空

孩子兄弟表示法&＃xff1a;任意一棵树&＃xff0c;它的结点的第一个孩子如果存在就是唯一的&＃xff0c;它的右兄弟存在也是唯一的。设置两个指针&＃xff0c;分别指向该结点的第一个孩子和此结点的右兄弟

二叉树

定义&＃xff1a;是n个结点的有限集合&＃xff0c;该集合或者为空集&＃xff0c;或者由一个结点和两棵互相不相交的、分别称为根结点的左子树和右子树的二叉树组成。

特殊的二叉树&＃xff1a;

1. 斜树&＃xff1a;所有的结点都只有左子树的二叉树叫做左斜树&＃xff0c;所有结点都是只有右子树的二叉树叫右斜树
2. 满二叉树&＃xff1a;在一棵二叉树中&＃xff0c;如果所有分支结点都存在左子树和右子树&＃xff0c;并且所有叶子都在同一层上
3. 完全二叉树&＃xff1a;

                所有的叶结点都出现在第k层或k-l层&＃xff08;层次最大的两层&＃xff09;对任一结点&＃xff0c;

                如果其右子树的最大层次为L&＃xff0c;则其左子树的最大层次为L或L&＃43;l。

二叉树的性质&＃xff1a;

1. 在二叉树的第i层上至多有

             

   
   

   二叉树的存储结构

   
   

   顺序存储结构

   
   

   二叉链表

   二叉树每个结点最多有两个孩子&＃xff0c;左指针和右指针

   
   

   
   二叉树的遍历

   以子结点为转折点&＃xff0c;先遍历子结点&＃xff0c;则为前序遍历

   
   
   1. 前序遍历
   2. 中序遍历
   3. 后续遍历
   4. 层序遍历&＃xff1a;一层一层的遍历
   
   

   二叉树的建立

   

   为了让每个结点确认是否右左右孩子&＃xff0c;对这棵树进行扩展&＃xff0c;引入虚结点&＃xff0c;值为"#"

   
   

   线索二叉树

   

   上图中存在很多空指针域

   一个有n个结点的二叉链表&＃xff0c;每个结点有指向左右孩子的两个指针域&＃xff0c;一共有2n个指针域&＃xff0c;有n-1条分支线&＃xff0c;存在2n-(n-1)&＃61;n&＃43;1个空指针域。

   如果事先知道每个结点的前驱结点和后继结点

   指向前驱和后继的指针称为线索&＃xff0c;加上线索的二叉链表称为线索二叉链表

     

        

   
   

   树、森林与二叉树的转换

   
   

   树-->二叉树

   

   

   
   

   森林-->二叉树

   

   

   
   

   二叉树-->树

   

   

   

   
   

   二叉树-->森林

   

   

   
   

   树与森林的遍历

   树

   
   
   1. 先根遍历树
   2. 后跟遍历树

   森林

   
   
   1. 前序遍历
   2. 后序遍历
   
   

   赫夫曼树及其应用

   赫夫曼树&＃xff1a;权重最大的作为根结点

   

   路径&＃xff1a;从树中一个结点到另一个结点之间的分支构成两个结点的路径&＃xff0c;路径上的分支数目称为路径长度

   树的路径长度&＃xff1a;从根结点到每个结点之间的距离

   二叉树a&＃xff1a;

   二叉树b&＃xff1a;

   考虑权值--带权路径长度WPL最小的二叉树称做赫夫曼树

   

   

   赫夫曼树的构建

   

   

   

                          

   

   赫夫曼树编码

   有段文字"BADCADFEED"传输&＃xff0c;但是用二进制时所需字节编码太过长

   

   

   当按照字符出现的频率&＃xff0c;可以构造赫夫曼树

   

   构造赫夫曼树后&＃xff1a;

   

   但是出现WPL变得很大&＃xff0c;编码效率不高&＃xff0c;

   因此还是用0和1编码更为效率