二叉树的基础

本片文章参考：https://www.yuque.com/mazhuan/er7l7d/cdim2i

备注：

前序遍历：根左右

后序遍历：左根右

中序遍历：左右根

知识点：

1. 二叉树的前序遍历
2. 二叉树的中序遍历
3. 二叉树的后序遍历
4. 层次遍历
5. 广度优先遍历（BFS）
6. 深度优先遍历（DFS）

js—API

shift：移除数组开头的数字

unshift：在数组开头添加一个数字

图1

代码1

const treeOjb = {
    val:1,
    left:{
        val:2,
        left:{
            val:4,
        },
        right:{
            val:5,
            left:{
              val:7  
            },
            right:{
               val:8,
            },
        },
    },
    right:{
      val:3,
      right:{
          val:6,
      },
    },
}

前序优先遍历（深度优先遍历）

递归思路

• 打印当前节点的值
• 递归调用自身，传入左子树
• 递归调用自身，传入右子树

const arr = []
const treeOjb = {
    val:1,
    left:{
        val:2,
        left:{
            val:4,
        },
        right:{
            val:5,
            left:{
                val:7
            },
            right:{
                val:8,
            },
        },
    },
    right:{
        val:3,
        right:{
            val:6,
        },
    },
}
function PreorderSearchBinaryTree(treeOjb){
    if(!treeOjb){
        return undefined
    } else {
        arr.push(treeOjb.val)
        PreorderSearchBinaryTree(treeOjb.left)
        PreorderSearchBinaryTree(treeOjb.right)
    }
}
PreorderSearchBinaryTree(treeOjb)
// console.log(PreorderSearchBinaryTree(treeOjb))
// 此处会重新调用一次
console.log(arr)

非递归思路

• 将根节点塞入栈
• 执行以下循环，当栈为空结束循环
• • 推出栈中的第一个节点
  • 检测是否有右子树，如果有，塞入栈
  • 检测是否有左子树，如果有，塞入栈
  • 打印当前推出节点的值

const treeOjb = {
    val:1,
    left:{
        val:2,
        left:{
            val:4,
        },
        right:{
            val:5,
            left:{
                val:7
            },
            right:{
                val:8,
            },
        },
    },
    right:{
        val:3,
        right:{
            val:6,
        },
    },
}
function fun(treeOjb) {
    const result = []
    const stack = [treeOjb]
    let currentNode
    while(stack.length > 0){
        currentNode = stack.pop()
        if(currentNode.right){
            stack.push(currentNode.right)
        }
        if(currentNode.left){
            stack.push(currentNode.left)
        }
        result.push(currentNode.val)
    }
    return result
}
console.log(fun(treeOjb));

后序遍历

递归版代码：

const tree = {
    val:1,
    left:{
        val:2,
        left:{
            val:4,
        },
        right:{
            val:5,
            left:{
                val:7
            },
            right:{
                val:8,
            },
        },
    },
    right:{
        val:3,
        right:{
            val:6,
        },
    },
}
const arr = []
function afterRecursion(tree) {
    if(!tree){
        return undefined
    }
    afterRecursion(tree.left)
    afterRecursion(tree.right)
    arr.push(tree.val)
}
afterRecursion(tree)
console.log(arr)

非递归代码：

const tree = {
    val:1,
    left:{
        val:2,
        left:{
            val:4,
        },
        right:{
            val:5,
            left:{
                val:7
            },
            right:{
                val:8,
            },
        },
    },
    right:{
        val:3,
        right:{
            val:6,
        },
    },
}
function afterNoRecursion(tree) {
    const result = []
    // 根节点塞入栈
    const stack = [tree]
    let currentNode
    while(stack.length > 0){
        // 推出栈中的第一个节点
        currentNode = stack.pop()
        // 如果有左节点，左节点入栈
        if(currentNode.left){
            stack.push(currentNode.left)
        }
        // 如果有右节点，右节点入栈
        if(currentNode.right){
            stack.push(currentNode.right)
        }
        // 打印当前节点
        result.unshift(currentNode.val)
    }
    return result
}
console.log(afterNoRecursion(tree))

中序遍历

递归的思想

const arr = []
const treeOjb = {
    val:1,
    left:{
        val:2,
        left:{
            val:4,
        },
        right:{
            val:5,
            left:{
                val:7
            },
            right:{
                val:8,
            },
        },
    },
    right:{
        val:3,
        right:{
            val:6,
        },
    },
}
function middleRecursion(treeOjb){
    if(!treeOjb){
        return undefined
    }else {
        middleRecursion(treeOjb.left)
        arr.push(treeOjb.val)
        middleRecursion(treeOjb.right)
    }
}
middleRecursion(treeOjb)
console.log(arr)

非递归的思想

const treeOjb = {
    val:1,
    left:{
        val:2,
        left:{
            val:4,
        },
        right:{
            val:5,
            left:{
                val:7
            },
            right:{
                val:8,
            },
        },
    },
    right:{
        val:3,
        right:{
            val:6,
        },
    },
}
function middleNoRecursion(root){
    const stack = []
    const result = []
    if(!root){
        return []
    }else{
        while(root || stack.length !== 0){
            while (root){
                stack.push(root)
                root = root.left
            }
            root = stack.pop()
            result.push(root.val)
            root = root.right
        }
    }
    return result
}
console.log(middleNoRecursion(treeOjb))

层序优先遍历（广度队列版）

const treeOjb = {
    val:1,
    left:{
        val:2,
        left:{
            val:4,
        },
        right:{
            val:5,
            left:{
                val:7
            },
            right:{
                val:8,
            },
        },
    },
    right:{
        val:3,
        right:{
            val:6,
        },
    },
}
function irregular(node){
        let result = [];
        let queue = [];
        queue.push(node);
        while(queue.length) {
            node = queue.shift();
            result.push(node.val); // 不要忘记访问
            // console.log(node.value);
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        return result;
}
console.log(irregular(treeOjb));