在这里读懂"365bet体育在线"

js 中二叉树的深度遍历与广度遍历(递归实现与非

来源:原创 2020-07-01 03:24 标签:
栈、队列、链表等数据结构,都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地,树型结构是以分支关系定义的层次结构。树型结构树在计算
栈、队列、链表等数据结构,都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地,树型结构是以分支关系定义的层次结构。 树型结构 树在计算机领域中也有着广泛的应用,例如在编译程序中,用树来表示源程序的语法结构;在数据库系统中,可用树来组织信息;在分析算法的行为时,可用树来描述其执行过程等等。 例如,(a)是只有一个根结点的树;(b)是有13个结点的树,其中A是根,其余结点分成3个互不相交的子集:T1={B,E,F,K,L},t2={D,H,I,J,M};T1,T2和T3都是根A的子树,且本身也是一棵树。 结点拥有的子树数称为结点的度(Degree)。例如,(b)中A的度为3,C的度为1,F的度为0。度为0的结点称为叶子(Leaf)或者终端结点。度不为0的结点称为非终端结点或分支结点。 树的度是树内各结点的度的最大值。(b)的树的度为3。结点的子树的根称为该结点的孩子(Child)。相应的,该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。反之,以某结点为根的子树中的任一结点都称为该结点的子孙。 求树的深度:看这篇: 二叉树(Binary Tree)是另一种树型结构,它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分(其次序不能任意颠倒。) 如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲parent(i)是结点Math.floor(i/2)。 如果2i > n,则结点i无左孩子(结点i为叶子结点);否则其左孩子LChild(i)是结点2i. 如果2i + 1 > n,则结点i无右孩子;否则其右孩子RChild(i)是结点2i + 1; 二叉树 完全二叉树 用一组连续的存储单元依次自上而下,自左至右存储完全二叉树上的结点元素,即将二叉树上编号为i的结点元素存储在加上定义的一维数组中下标为i-1的分量中。“0”表示不存在此结点。这种顺序存储结构仅适用于完全二叉树。因为,在最坏情况下,一个深度为k且只有k个结点的单支树(树中不存在度为2的结点)却需要长度为2的n次方-1的一维数组。 顺序:[1, 2, 3, 4, 5, , 6, , , 7] 二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成,则表示二叉树的链表中的结点至少包含三个域:数据域和左右指针域。有时,为了便于找到结点的双亲,还可在结点结构中增加一个指向其双亲结点的指针域。利用这两种结构所得的二叉树的存储结构分别称之为二叉链表和三叉链表。 在含有n个结点的二叉链表中有n+1个空链域,我们可以利用这些空链域存储其他有用信息,从而得到另一种链式存储结构---线索链表。 链式:{ data, left, right} 遍历二叉树(Traversing Binary Tree):是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。 二叉树有深度遍历和广度遍历, 深度遍历有前序、 中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等;中序遍历可以实现表达式树,在编译器底层很有用;后序遍历可以用来实现计算目录内的文件及其信息等。 二叉树是非常重要的数据结构, 其中二叉树的遍历要使用到栈和队列还有递归等,很多其它数据结构也都是基于二叉树的基础演变而来的。熟练使用二叉树在很多时候可以提升程序的运行效率,减少代码量,使程序更易读。 二叉树不仅是一种数据结构,也是一种编程思想。学好二叉树是程序员进阶的一个必然进程。 前序遍历:访问根–>遍历左子树–>遍历右子树; 中序遍历:遍历左子树–>访问根–>遍历右子树; 后序遍历:遍历左子树–>遍历右子树–>访问根; 广度遍历:按照层次一层层遍历; 对该二叉树进行深度和广度遍历为: *前序遍历:- + a * b c / d e 中序遍历:a + b * c - d / e 后序遍历:a b c + d e / - 广度遍历:- + / a * d e b c 1. js中的二叉树 上述二叉树(a+b*c)-d/e在js中可以用对象的形式表示出来: var tree = { value: "-", left: { value: '+', left: { value: 'a', }, right: { value: '*', left: { value: 'b', }, right: { value: 'c', } } }, right: { value: '/', left: { value: 'd', }, right: { value: 'e', } } }2. js中二叉树的深度遍历 深度遍历也可称为深度优先遍历(Depth-First Search,DFS),因为它总是优先往深处访问。 先序遍历 let result = [];let dfs = function (node) { if(node) { result.push(node.value); dfs(node.left); dfs(node.right); } } dfs(tree);console.log(result); // ["-", "+", "a", "*", "b", "c", "/", "d", "e"] 先序递归遍历思路: 先遍历根结点,将值存入数组,然后递归遍历:先左结点,将值存入数组,继续向下遍历;直到(二叉树为空)子树为空,则遍历结束; 然后再回溯遍历右结点,将值存入数组,这样递归循环,直到(二叉树为空)子树为空,则遍历结束。 let dfs = function (nodes) { let result = []; let stack = []; stack.push(nodes); while(stack.length) { // 等同于 while(stack.length !== 0) 直到栈中的数据为空 let node = stack.pop(); // 取的是栈中最后一个j result.push(node.value); if(node.right) stack.push(node.right); // 先压入右子树 if(node.left) stack.push(node.left); // 后压入左子树 } return result; } dfs(tree); 先序非递归遍历思路: 中序遍历 let result = [];let dfs = function (node) { if(node) { dfs(node.left); result.push(node.value); // 直到该结点无左子树 将该结点存入结果数组 接下来并开始遍历右子树 dfs(node.right); } } dfs(tree);console.log(result);// ["a", "+", "b", "*", "c", "-", "d", "/", "e"] 中序递归遍历的思路: 先递归遍历左子树,从最后一个左子树开始存入数组,然后回溯遍历双亲结点,再是右子树,这样递归循环。 function dfs(node) { let result = []; let stack = []; while(stack.length || node) { // 是 || 不是 && if(node) { stack.push(node); node = node.left; } else { node = stack.pop(); result.push(node.value); //node.right && stack.push(node.right); node = node.right; // 如果没有右子树 会再次向栈中取一个结点即双亲结点 } } return result; } dfs(tree);// ["a", "+", "b", "*", "c", "-", "d", "/", "e"] 一种利用回溯法思想的代码: 看这里: 但是他的代码有些问题。。。 非递归遍历的思路: 将当前结点压入栈,然后将左子树当做当前结点,如果当前结点为空,将双亲结点取出来,将值保存进数组,然后将右子树当做当前结点,进行循环。 后序遍历 result = [];function dfs(node) { if(node) { dfs(node.left); dfs(node.right); result.push(node.value); } } dfs(tree);console.log(result);// ["a", "b", "c", "*", "+", "d", "e", "/", "-"] 写到这,深深的被递归折服。。。。服 先走左子树,当左子树没有孩子结点时,将此结点的值放入数组中,然后回溯遍历双亲结点的右结点,递归遍历。 (含大量注释代码的) function dfs(node) { let result = []; let stack = []; stack.push(node); while(stack.length) { // 不能用node.touched !== 'left' 标记‘left’做判断, // 因为回溯到该结点时,遍历右子树已经完成,该结点标记被更改为‘right’ 若用标记‘left’判断该if语句会一直生效导致死循环 if(node.left && !node.touched) { // 不要写成if(node.left && node.touched !== 'left') // 遍历结点左子树时,对该结点做 ‘left’标记;为了子结点回溯到该(双亲)结点时,便不再访问左子树 node.touched = 'left'; node = node.left; stack.push(node); continue; } if(node.right && node.touched !== 'right') { // 右子树同上 node.touched = 'right'; node = node.right; stack.push(node); continue; } node = stack.pop(); // 该结点无左右子树时,从栈中取出一个结点,访问(并清理标记) node.touched && delete node.touched; // 可以不清理不影响结果 只是第二次对同一颗树再执行该后序遍历方法时,结果就会出错啦因为你对这棵树做的标记还留在这棵树上 result.push(node.value); node = stack.length ? stack[stack.length - 1] : null; //node = stack.pop(); 这时当前结点不再从栈中取(弹出),而是不改变栈数据直接访问栈中最后一个结点 //如果这时当前结点去栈中取(弹出)会导致回溯时当该结点左右子树都被标记过时 当前结点又变成从栈中取会漏掉对结点的访问(存入结果数组中) } return result; // 返回值} dfs(tree); 后序遍历非递归遍历思路:先把根结点和左树推入栈,然后取出左树,再推入右树,取出,最后取根结点。 步骤: 3. js中二叉树的广度遍历 广度优先遍历二叉树(层序遍历)是用队列来实现的,广度遍历是从二叉树的根结点开始,自上而下逐层遍历;在同一层中,按照从左到右的顺序对结点逐一访问。 let result = [];let stack = [tree]; // 先将要遍历的树压入栈let count = 0; // 用来记录执行到第一层let bfs = function () { let node = stack[count]; if(node) { result.push(node.value); if(node.left) stack.push(node.left); if(node.right) stack.push(node.right); count++; bfs(); } } dfc();console.log(result);// ["-", "+", "/", "a", "*", "d", "e", "b", "c"] function bfs(node) { let result = []; let queue = []; queue.push(node); let pointer = 0; while(pointer < queue.length) { let node = queue[pointer++]; // // 这里不使用 shift 方法(复杂度高),用一个指针代替 result.push(node.value); node.left && queue.push(node.left); node.right && queue.push(node.right); } return result; } bfs(tree);// ["-", "+", "/", "a", "*", "d", "e", "b", "c"] 另外一种比较消耗性能的方法:不额外定义一个指针变量 pointer,使用数组的shift()方法,每次改变 queue 的数据(入栈、出栈),来读取数据,直到栈 queue 中数据为空,执行结束。(频繁的改变数组,因为数组是引用类型,要改变它,要新开辟一个地址,所以比较消耗空间) function bfs (node) { let result = []; let queue = []; queue.push(node); while(queue.length) { node = queue.shift(); result.push(node.value); // 不要忘记访问 // console.log(node.value); node.left && queue.push(node.left); node.right && queue.push(node.right); } return result; } bfs(tree);// ["-", "+", "/", "a", "*", "d", "e", "b", "c"] 作者:黎贝卡beka 链接:
推荐阅读