javascript实现二叉树遍历(递归与借用栈两种实现)

in 算法 with 0 comment

javascript实现二叉树遍历思想跟C,Java等语言是一样的,不过写起来,因为javascript没有链表,指针一说,(通常用链接来表示二叉树),只能大概表达一下意思。

构造二叉树

    //构建二叉树
    function Node(data) {
        this.left = null
        this.right = null
        this.data = data
    }

生成二叉树

    //以前序遍历的顺序创建二叉树
    function createTree(data) {
        let node_data = data.shift()
        let p = null
        if (node_data != 0) {
            p = new Node(node_data)
            p.left = createTree(data)
            p.right = createTree(data)
        }
        return p
    }

调用createTree生成一棵二叉树,节点值为0的节点,表示子树为空

const arr = [1, 2, 4, 8, 0, 0, 5, 0, 0, 6, 0, 0, 3, 7, 10, 0, 0, 11, 0, 0, 9, 12, 0, 0, 13, 0, 14, 0, 0]
const root = createTree(arr)

前序遍历(递归)

//前序遍历(递归)
function prevTraverse(node) {
    if (node == null) return
    console.log(node.data)
    prevTraverse(node.left)
    prevTraverse(node.right)
}

中序遍历(递归)

//中序遍历(递归)
function middleTraverse(node) {
    if (node == null) return
    middleTraverse(node.left)
    console.log(node.data)
    middleTraverse(node.right)
}

后序遍历(递归)

function lastTraverse(node) {
    if (node == null) return
    lastTraverse(node.left)
    lastTraverse(node.right)
    console.log(node.data)
}

javascript递归实现代码简洁,递归其实也是借助栈来实现的,递归调用是把函数及函数的参数压栈,然后再一步步回溯,下边用javascript的数组来表示栈,利用栈的后进先出特性来实现二叉树的前,中,后序遍历,其中前序,中序遍历稍微简单一些,看其它大神有几种实现思路,我只用其中自己感觉比较好理解的思路实现了一下,后序遍历比较复杂一些,我暂时放了一个比较巧的方法,即是正常二叉树的前序遍历:根-->左子树-->右子树,变为 根 --> 右子树 --> 左子树,然后再逆序输出

注:用数组表示栈可以在栈顶操作,也可以在栈底操作,在栈顶: push加入数据,pop弹出数据,在栈底: unshift加入数据,shift弹出数据

前序遍历(非递归,借助栈)

function prevTraverseWithStack(node) {
        const stack = []
        let p = node
        while (p != null || stack.length > 0) {
            //处理左子树
            while (p != null) {
                //stack.unshift(p)
                stack.push(p)
                console.log(p.data)
                p = p.left
            }
            //处理右子树
            if (stack.length > 0) {
                //p = stack.shift()
                p = stack.pop()
                //console.log('stack length: ' + stack.length)
                p = p.right
            }
        }
    }

前序遍历二,便于跟中序遍历比较(非递归,借助栈)

function prevTraverseWithStack2(node) {
        const stack = []
        let p = node
        while (p != null || stack.length > 0) {
            if (p != null) {
                stack.push(p)
                console.log(p.data)
                p = p.left
            } else {
                p = stack.pop()
                p = p.right
            }
        }
    }

前序遍历三(非递归,借助栈)

function prevTraverseWithStack3(node) {
        const stack = []
        let p = null
        stack.unshift(node)
        while (stack.length > 0) {
            //p = stack.shift()
            p = stack.pop()
            //console.log('stack length: ' + stack.length)
            console.log(p.data)
            if (p.right != null) {
                //stack.unshift(p.right)
                stack.push(p.right)
            }
            if (p.left != null) {
                //stack.unshift(p.left)
                stack.push(p.left)
            }
        }
    }

中序遍历(非递归,借助栈)

先上一版,我蒙头写的,反正是可以运行的,方法就是把输出结果摆在那里,然后一点点试错,stack.push(p.right)这一句就是为了有一个bug而来的,但最后分析一下,逻辑也是对的,感觉用栈来实现的核心就是 每个节点都要访问它的左节点,右节点,然后再看情况进行回溯

function middleTraverseWithStack(node) {
      let p = node
      let stack = [] 
      while(p !== null || stack.length > 0){
        if(p.left !== null) {
          stack.push(p)
          p = p.left
        }else{
          console.log(p.data)
          if(p.right) {
            stack.push(p.right)
          }
          let t = stack.pop()
          console.log(t.data)
          p = t.right
        }
      }
    }

书上的

function middleTraverseWithStack(node) {
        const stack = []
        let p = node
        while (stack.length > 0 || p != null) {
            if (p === null) {
                //p = stack.shift()
                p = stack.pop()
                console.log(p.data)
                p = p.right
            } else {
                //stack.unshift(p)
                stack.push(p)
                p = p.left
            }
        }
    }

后序遍历一(非递归,借助栈)

相比前,中序遍历,多定义一个 result 栈来实现逆序输出结果

左-->右-->根 ----- reverse --- 根-->右-->左 ------- 根-->左-->右 前序遍历翻版

function lastTraverseWithStack(node) {
        let stack = [], p = node, result = []
        while (stack.length > 0 || p !== null) {
            if (p !== null) {
                stack.push(p)
                result.unshift(p.data)
                //console.log(p.data)
                p = p.right
            } else {
                p = stack.pop()
                p = p.left
            }
        }
        console.log(result)
        //return result
    }

后序遍历二(非递归,借助栈)

相比前,中序遍历,多定义一个 tag 来标记是否已经访问过,目前还是不太懂

function lastTraverseWithStack1(node) {
        let stack = [], p = node, tag
        while (p !== null || stack.length > 0) {
            if (p !== null) {
                stack.push(p)
                p = p.left
            }
            else {
                p = stack[stack.length - 1];
                if (p.right && tag != p.right) {
                    p = p.right;
                }
                else {
                    stack.pop();
                    console.log(p.data);
                    tag = p;
                    p = null;
                }
            }
        }
    }

层序遍历(非递归,借助队列)

层序遍历用递归实现比较绕,需要先求出二叉树的深度,再进行递归

//层序遍历 push与shift结合,将数组当作队列使用
function floorPrintWithQuene(node) {
    const quene = []
    quene.push(node)
    while (quene.length > 0) {
        node = quene.shift()
        console.log(node.data)
         if (node.left != null) {
            quene.push(node.left)
         }
        if (node.right != null) {
            quene.push(node.right)
        }
      }
 }

其它非递归实现思想可参考:

非递归实现

知乎使用JS实现二叉树

js实现csdn

递归实现层序遍历参考stackoverflow

评论已关闭.