关于javascript:Day-76100-数据结构二叉树13树的遍历

33次阅读

共计 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…

正文完
 0