共计 951 个字符,预计需要花费 3 分钟才能阅读完成。
树的概述
树 是一种常常用到的数据结构,用来模仿具备树状构造性质的数据汇合。
树里的每一个节点有一个值和一个蕴含所有子节点的列表。从图的观点来看,树也可视为一个领有 N 个节点和 N -1 条边的一个有向无环图。
二叉树是一种更为典型的树状构造。如它名字所形容的那样,二叉树是每个节点最多有两个子树的树结构,通常子树被称作“左子树”和“右子树”。
(一)定义
1、前序遍历
前序遍历首先拜访根节点,而后遍历左子树,最初遍历右子树。
2、中序遍历
中序遍历是先遍历左子树,而后拜访根节点,而后遍历右子树。
通常来说,对于二叉搜寻树,咱们能够通过中序遍历失去一个递增的有序序列。咱们将在另一张卡片(数据结构介绍 – 二叉搜寻树)中再次提及。
3、后序遍历
后序遍历是先遍历左子树,而后遍历右子树,最初拜访树的根节点。
值得注意的是,当你删除树中的节点时,删除过程将依照后序遍历的程序进行。也就是说,当你删除一个节点时,你将首先删除它的左节点和它的左边的节点,而后再删除节点自身。
(二)用处
1、前序遍历
- 实现目录构造的显示
2、中序遍历
- 对于二叉搜寻树,中序遍历失去一个递增的有序序列。
找出原始表达式:您能够应用中序遍历轻松找出原始表达式。然而程序处理这个表达式时并不容易,因为你必须查看操作的优先级。
- 编译器底层实现的时候用户能够实现根本的加减乘除,比方 a*b+c。
3、后序遍历
- 你删除树中的节点时,删除过程将依照后序遍历的程序进行。也就是说,当你删除一个节点时,你将首先删除它的左节点和它的左边的节点,而后再删除节点自身。
- 累加数——实现计算目录内的文件占用的数据大小
上述三种递归遍历形式工夫复杂度和空间复杂度剖析
工夫复杂度 0(n)
空间复杂度 O(n)
问题
什么是二叉搜寻树?
二叉查找树(Binary Search Tree),(又:二叉搜寻树,二叉排序树)它或者是一棵空树,或者是具备下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也别离为二叉排序树。
参考链接:
https://leetcode.cn/leetbook/…
写在最初的话
学习路上,经常会懈怠
《有想学技术须要监督的同学嘛~》
https://mp.weixin.qq.com/s/Fy…