【数据结构与算法】二叉树

定义 二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。 实现 结构定义 尝试了一下C语言，各种指针乱指，各种bug，暂时放自己一马，跟自己和解一下用js写写吧。 class TreeNode { constructor(data) { this.data = data; this.left = null; // 左节点 this.right = null; // 右边节点 } } 创建对象并绑定节点 // 手动绑定节点 let root = new TreeNode(1) root.left = new TreeNode(2) root.right = new TreeNode(3) root.left.left = new TreeNode(4) root.right.right = new TreeNode(5) 此时树的结构： 1 / \ 2 3 / \ \ 4 5 6 遍历二叉树 前序遍历（DFS） function preOrder(node) { if(node) { console.log(node.data) preOrder(node.left) preOrder(node.right) } } 这里用递归调用，遍历到左右元素 层序遍历（BFS） function levelOrder(root) { const queue = []; queue.push(root); while (queue.length) { const node = queue.shift(); console.log(node.data); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } }