数据结构与算法(3)——树（二叉、二叉搜索树） 前言：题图无关，现在开始来学习学习树相关的知识 前序文章：数据结构与算法(1)——数组与链表（https://www.sigusoft.com/p/7b93b）数据结构与算法(2)——栈和队列(https://www.sigusoft.com/p/5087c751cb42) 树 什么是树 树是一种类似于链表的数据结构，不过链表的结点是以线性方式简单地指向其后继结点，而树的一个结点可以指向许多个结点；数是一种典型的非线性结构；树结构是以表达具有层次特性的图结构的一种方法； 
相关术语 根节点：根节点是一个没有双亲结点的结点，一棵树中最多有一个根节点（如上图的结点A就是根节点）；边：边表示从双亲结点到孩子结点的链接（如上图中所有的链接）；叶子结点：没有孩子结点的结点叫作叶子结点（如E、J、K、H和I）；兄弟结点：拥有相同双亲结点的所有孩子结点叫作兄弟结点（B、C、D是A的兄弟结点，E、F是B的兄弟结点）；祖先结点：如果存在一条从根节点到结点q的路径，其结点p出现在这条路径上，那么就可以吧结点p叫作结点q的祖先结点，结点q也叫做p的子孙结点（例如，A、C和G是K的祖先结点）；结点的大小：结点的大小是指子孙的个数，包括其自身。（子树C的大小为3）；树的层：位于相同深度的所有结点的集合叫作树的层（B、C和D具有相同的层，上图的结构有0/1/2/3四个层）；结点的深度：是指从根节点到该节点的路径长度（G点的深度为2，A—C—G）；结点的高度：是指从该节点到最深节点的路径长度，树的高度是指从根节点到书中最深结点的路径长度，只含有根节点的树的高度为0。（B的高度为2，B—F—J）；树的高度：是树中所有结点高度的最大值，树的深度是树中所有结点深度的最大值，对于同一棵树，其深度和高度是相同的，但是对于各个结点，其深度和高度不一定相同； 二叉树 如果一棵树中的每个结点有0，1或者2个孩子结点，那么这棵树就称为二叉树；空树也是一颗有效的二叉树，一颗二叉树可以看做是由根节点和两棵不相交的子树（分别称为左子树和右子树）组成，如下图所示。 
二叉树的类型 严格二叉树：二叉树中的每个节点要么有两个孩子结点，要么没有孩子结点 
满二叉树：二叉树中的每个结点恰好有两个孩子结点且所有叶子结点都在同一层 
完全二叉树：在定义完全二叉树之前，假定二叉树的高度为h；对于完全二叉树，如果将所有结点从根节点开始从左至右，从上至下，依次编号（假定根节点的编号为1），那么僵得到从1~n（n为结点总数）的完整序列，在遍历过程中对于空指针也赋予编号，如果所有叶子结点的深度为h或h-1，且在结点编号序列中没有漏掉任何数字，那么这样的二叉树叫作完全二叉树。 
二叉树的应用 编译器中的表达式树；用于数据压缩算法中的赫夫曼编码树；支持在集合中查找、插入和删除，其平均时间复杂度为O(lognn)的二叉搜索树（BST）；优先队列（PQ），它支持以对数时间（最坏情况下）对集合中的最小（或最大）数据素进行搜索和删除； 二叉树的遍历 
访问树中所有结点的过程叫作树的遍历，在遍历过程中，每个结点只能被处理一次，尽管其有可能被访问多次；根据结点处理顺序的不同，。可以定义不同的遍历方法，遍历分类可以根据当前节点被处理的顺序来划分： 前序遍历 在前序遍历中，每个结点都是在它的子树遍历之前进行处理，这是最容易理解的便利方法，然而，尽管每个结点在其子树之前进行了处理，但在向下移动的过程仍然需要保留一些信息，以上图为例，首先访问结点1，随后遍历其左子树，最后遍历其右子树，因此当左子树遍历完后，必须要返回到其右子树来继续遍历；为了能够在左子树遍历完成后移动到右子树，必须保留根节点的信息，能够实现该信息存储的抽象数据类型显而易见是栈，由于它是LIFO的结构，所以它可以以逆序来汇过去该信息并返回到右子树； 前序遍历可以如下定义：访问根节点；按前序遍历方式遍历左子树；按前序遍历方式遍历右子树； 利用前序遍历方法上图所示的树的输出序列为：1 2 4 5 3 6 7 中序遍历 在中序遍历中，根节点的访问在两棵子树的遍历中间完成，中序遍历如下定义：按中序遍历方式遍历左子树；访问根节点；按中序遍历方式遍历右子树； 基于中序遍历，上图所示树的中序遍历输出顺序为：4 2 5 1 6 3 7 后序遍历 在后续遍历中，根节点的访问是在其两棵子树都遍历完成后进行的，后续遍历如下定义：按后序遍历左子树；按后序遍历右子树；访问根节点； 对上图所示的二叉树，后续遍历产生的输出序列为：4 5 2 6 7 3 1 层次遍历 层次遍历的定义如下：访问根节点；在访问第l层时，将l+1层的节点按顺序保存在队列中；进入下一层并访问该层的所有结点；重复上述操作直至所有层都访问完； 对于上图所示的二叉树，层次遍历产生的输出序列为：1 2 3 4 5 6 7 二叉搜索树 在二叉搜索树中，所有左子树结点的素小于根节点的数据，所有右子树结点的素大于根节点数据，注意，树中的每个结点都应满足这个性质； 
实现自己的二叉搜索树 其中包含了常用的一些方法，包括几种遍历方法还有查询、删除等，仅供参考： LeetCode相关题目整理 94.二叉树的中序遍历 
我的答案：（1ms） 参考答案：（0ms） 98. 验证二叉搜索树 
我的答案：（53ms） 自己写的时候提交错了很多次..没有掌握到二分搜索树的精髓.. 参考答案：（2ms） 这答案写得我服了..真服.. 101. 对称二叉树（剑指Offer面试题28） 
参考答案：（12ms） 自己做的思路是使用中序遍历来判断（转成数组之后是对称的），但是出了很多问题，就是需要考虑null值，中序遍历中并不能很好地把一棵树保存为一个完整二叉树的样子..所以看了下参考答案..写得服.. 104. 二叉树的最大深度（剑指Offer面试题55） 
我的答案：（3ms） 参考答案：（0ms） 105. 从前序与中序遍历序列构造二叉树（剑指Offer面试题7） 
参考答案：（2ms） 思路是这样的：在二叉树的前序遍历序列中，第一个数字总是树的根节点的值，但在中序遍历序列中，根节点的值保存在序列的中间，左子树的节点的值位于根节点的值的左边，而右子树则相反，然后既然找到了左右子树我们又可以使用同样的方法在前序和中序中分别构建左右子树，这样我们就能够使用递归的方法完成；（上面算法中的ps、is、ie分别表示前序的开始位置，中序的开始位置和中序的结束位置；） 113. 路径总和 II（剑指Offer面试题34） 
参考答案：（3ms） 230. 二叉搜索树中第K小的素（类似剑指Offer面试题54） 
我的答案：（23ms） 贼蠢，完全没有用到二叉搜索树的特性 参考答案：（1ms） 449. 序列化二叉搜索树（类似剑指Offer面试题37） 
参考答案：（12ms） 572. 另一个树的子树（类似剑指Offer面试题26） 
参考答案：（15ms） 我的第一个反应还是去把两棵树的前序遍历的数组弄出来然后判断是否为子集，但是树这样的天然递归结构这样写很自然… 简单总结 还是只是简单复习了一下树的相关知识吧，通过刷LeetCode题目还有参照着剑指Offer对二叉树、二叉搜索树仅仅这两种结构有了一个较深的认识，因为后续还会继续用到，所以这里简单复习一下也无所谓，不过看着题目倒是感觉这样的结构很容易考面试题啊，因为这些结构既重要考点又多…欢迎转载，转载请注明出处！简书ID：@我没有三颗心脏github：wmyskxz欢迎公众号：wmyskxz_javaweb分享自己的Java Web学习之路以及各种Java学习资料
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/26815.html
