# 中序遍历
遍历顺序为:
遍历之后:["LL","L","LR","Root","RL","R","RR"]
递归遍历
function inOrderRec (tree) { let list = [] let inOrderRecFn = function (node) { if (node) { if (node.left) inOrderRecFn(node.left) list.push(node.value) if (node.right) inOrderRecFn(node.right) } } inOrderRecFn(tree) return list }
@CodePoet: 代码已经复制到剪贴板
非递归遍历
非遍历我是这样考虑的:
- 会先把中间
"Root"
压入栈中 - 然后开始压入
"Root"
的左边节点 - 当左边节点全部都压进栈了之后,
["Root", "L", "LL"]
- 要开始从栈的末位取出
value
了,同时要开始把右边的也压入栈了 - 当取出
"LL"
的时候,"LL"
已经没有左右子节点了,所以会继续从栈的末位取出value
- 也就是取出了
"L"
,"L"
还是有右节点的,所以要把"LR"
压入栈 "LR"
压入栈之后,"LR"
也是没有左子节点的,所以会从栈的末位取出,且它又没有右子节点,就会继续取出- 继续取出
"Root"
,这时候再开始把node = "Root".right
了,也就是要开始遍历"R"
了 - 以此类推把
"R"
也按上面的步骤遍历完
function inOrderUnRec (tree) { let list = [] let inOrderUnRecFn = function (node) { if (node) { // 当前节点存在 let stack = [] // 定义一个空的栈 while(stack.length !== 0 || node) { // 判断栈不为空或者当前节点存在 if (node) { // 若是节点存在 stack.push(node) // 将当前节点推入栈 node = node.left // 将左子树作为当前节点 } else { // 当前节点不存在(左子树为空) node = stack.pop() // 从栈中取出节点 list.push(node.value) node = node.right // 将右子树作为当前节点 } } } } inOrderUnRecFn(tree) return list }
@CodePoet: 代码已经复制到剪贴板
非递归第一次遍历
let stack = [] // 定义一个空的栈 while(stack.length !== 0 || node) { // 判断栈不为空或者当前节点存在 // 此时: // node: {value: 'Root', left: {}, right: {}} if (node) { // 若是节点存在 // 将当前节点推入栈 // stack: [ {value: 'Root', left: {}, right: {}} ] stack.push(node) // 将左子树作为当前节点 // node: {value: 'L', left: {}, right: {}} node = node.left } else { // 当前节点不存在(左子树为空) node = stack.pop() // 从栈中取出节点 list.push(node.value) node = node.right // 将右子树作为当前节点 } }
@CodePoet: 代码已经复制到剪贴板
非递归第二次遍历
let stack = [] // 定义一个空的栈 while(stack.length !== 0 || node) { // 判断栈不为空或者当前节点存在 // 此时: // node: {value: 'L', left: {}, right: {}} if (node) { // 若是节点存在 // 将当前节点推入栈 // stack: [ {value: 'Root', left: {}, right: {}}, {value: 'L', left: {}, right: {}} ] stack.push(node) // 将左子树作为当前节点 // node: {value: 'LL'} node = node.left } else { // 当前节点不存在(左子树为空) node = stack.pop() // 从栈中取出节点 list.push(node.value) node = node.right // 将右子树作为当前节点 } }
@CodePoet: 代码已经复制到剪贴板
经过第二次循环之后,stack
变成了[ {value: 'Root', left: {}, right: {}}, {value: 'L', left: {}, right: {}} ]
, 当前节点node
变成了{value: 'LL'}。
这样在第四次循环的时候, node
就为undefinded
了,此时进入了else
中,然后就达到了先遍历所有左子树,再获取根节点,最后遍历右子树的效果。
阅读全文