JS实现二叉树的创建和遍历

女爷i 2023-02-24 11:11 104阅读 0赞

1、先说二叉树的遍历，遍历方式：

前序遍历：先遍历根结点，然后左子树，再右子树

中序遍历：先遍历左子树，然后根结点，再右子树

后续遍历：先遍历左子树，然后右子树，再根结点

![format_png][]![format_png 1][] ![format_png 2][]

上代码：主要还是利用递归

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

二叉树的非递归遍历

深度优先遍历（主要利用栈的先进后出）

广度优先遍历（主要利用队列的先进先出）

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

//深度优先非递归
    function DepthFirstSearch(biTree) {
        let stack = [];
        stack.push(biTree);
    
        while (stack.length != 0) {
            let node = stack.pop();
            console.log(node.data);
            if (node.rChild) {
                stack.push(node.rChild);
            }
            if (node.lChild) {
                stack.push(node.lChild);
            }
    
        }
    
    }
    
    
    //广度优先非递归
    function BreadthFirstSearch(biTree) {
        let queue = [];
        queue.push(biTree);
        while (queue.length != 0) {
            let node = queue.shift();
            console.log(node.data);
            if (node.lChild) {
                queue.push(node.lChild);
            }
            if (node.rChild) {
                queue.push(node.rChild);
            }
        }
    
    }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

深度优先主要是利用栈，先压右子树，再压左子树

广度优先主要利用队列，先入左子树，再入右子树

深度优先的遍历结果与前序遍历相同ABDGHCEIF，广度优先的遍历结果是 ABCDEFGHI

2、创建二叉树

1中创建二叉树的方式过于笨拙，假入我们根据完全二叉树的模型建立自己的二叉树，空数据的地方用\#表示，如下图所示我们称之为扩展二叉树，我们取其前序遍历的序列 AB\#D\#\#C\#\#。

上代码：也是利用递归

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]![format_png 3][]

//前序遍历得到的字符串
    let strArr = 'AB#D##C##'.split('');
    
    function BiTree(ele) {
        this.data = ele;
        this.lChild = null;
        this.rChild = null;
    }
    var newTree = new BiTree('#');
    
    function createBiTree(biTree) {
        if (strArr.length == 0) return;
        let str = strArr.shift();
        if (str == '#') return;
        biTree.data = str;
        if (strArr[0] != '#') {
            biTree.lChild = new BiTree('#')
        }
        createBiTree(biTree.lChild);
        if (strArr[0] != '#') {
            biTree.rChild = new BiTree('#')
        }
        createBiTree(biTree.rChild);
    }
    createBiTree(newTree);
    console.log(newTree);
    ProOrderTraverse(newTree)

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

你也可以用中序遍历或者后序遍历实现二叉树的创建，代码里生成结点和构建左右子树的代码顺序交换一下就行了

转载：[https://www.cnblogs.com/xbblogs/p/9917245.html][https_www.cnblogs.com_xbblogs_p_9917245.html]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvNzE1MTQxLzIwMTgxMS83MTUxNDEtMjAxODExMDYxOTAwMzM2MDktMTY5MzU3NzAzMS5wbmc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvNzE1MTQxLzIwMTgxMS83MTUxNDEtMjAxODExMDYxOTAzMTA4NDUtNzk3OTAxMzQ3LnBuZw?x-oss-process=image/format,png
[format_png 2]: /images/20230209/2fa5b7aaa87c492bb67abab6afe6e1b7.png
[aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]: /images/20230209/a08d98bdcba94bb193940b979476b8af.png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvNzE1MTQxLzIwMTgxMS83MTUxNDEtMjAxODExMDYxODQ4MzIyMjktNDI1MjI0MzU4LnBuZw?x-oss-process=image/format,png
[https_www.cnblogs.com_xbblogs_p_9917245.html]: https://www.cnblogs.com/xbblogs/p/9917245.html