数据结构复习要点—树

发表这一系列的博客,不是为了初级入门者的教学,而是将要点难点尽可能的列出来,方便快速复习,之前的链表和字符串貌似扯的有点多,这次力求简短。

  • 类型很多:二叉树,完全二叉树,搜索二叉树,Huffman树,AVL 平衡树,红黑树,Trie树,B树
  • 二叉树:能用数组表示一颗完全二叉树,一颗二叉搜索书的中序遍历结果是以一个有序数组;如果要确定一颗二叉树的结构,至少需要知道中序遍历,外加后或者前序遍历的任意一种;叶子结点数量整好比有两个孩子的结点的数量多1(堆排序的调整可以从n/2开始); n个结点的完全二叉树的的深度最多为Math.floor(Log_2 a) +1;
  • 树的遍历,BFS,通过队列来实现;遍历剪枝是一种常用的编程技巧;DFS的前中后的递归很简单,非递归用栈来实现难度依次上升。
  • 线索树,利用叶子结点的空指针,确定某一种遍历次序,遍历的同时建立线索,空左指针指向之前的结点,空的右指针指向之后的结点。这样的数据结构的最大好处就是在那些数值固定的地方,需要经常遍历树的情况下,方便的查找前序后续,以及遍历整个树而不需要占用额外的空间(Stack or Queue)
  • 霍夫曼树,是一种非常简单的字符压缩方法,但是实现起来还是很有挑战的,这个压缩是指原来的字符串变为01串的长度,被压缩为霍夫曼树对应的长度。其做法就是将出现的所有字符(假设Anscii256)按照其出现的频率排序构建优先队列;以此为主要基础,不断取最小的两个作为结点合并为新结点,加入优先队列,不断重复此过程,构建一颗密码树;然后遍历密码树,获取根结点的对应的代码,放到一个HashMap中。加密的过程就是通过HashMap遍历求新字符串;解密的过程就是根据Code 来遍历树,当到根节点的时候,翻译出原文,然后继续向下。
  • 二叉搜索树,左子树的所有值小于根节点的值,右结点的所有值大于根节点,(在判断的一颗树是否是二叉树的时候要小心),二叉树的中序遍历可以转化为一个有序的数组(注意每个元素都不同),一个有序的数组不断以中间的元素作为根节点,可以构造出一颗平衡二叉树(AVL和RB树是为了能够动态的删除和增加,所以如果你的整棵树是固定的话,这也是一个很直观的方法),二叉搜索树主要需要实现的功能是插入,查找,删除,代码简单优美。
  • AVL树,一种要求严格平衡的二叉搜索树,在不断插入元素的同时,左右子树的高度差不能超过2。在此假设下,在不断插入的过程中,只可能出现4种情况分别是LL,LR,RR,RL,针对每种情况,不断的调整树,不同的顺序调整为相同顺序,然后再进行处理。AVL树实现起来简单容易,需要参照,二叉树的插入和删除方法,不过每次整完之后,如果情况有变都需要整体调整,所以可能的操作数量较多。
  • 红黑树,这是一种正确的,但是和AVL以及树完全没关系一套理论,红黑树5条性质,然后插入和删除写起来都非常有难度,AVL树的左旋右旋,这里需要改造一下,而且还只是基础操作,插入总共5中情况,删除总共六种情况。
  • Trie树,每层26个子树,其最大应用应该是神奇酷炫的后缀树的应用了,处理字符串的神器。
  • B+树,其实这个真的不用太怕,直接用一个List<Node>表示Sons,其他的和二叉树都很像了,一般外加剪枝来进行搜索,例如获得所有的排列组合神马的。
  • 堆,正常来说是最大堆和最小堆,最常见的应用是堆排序。

发表评论

电子邮件地址不会被公开。 必填项已用*标注