数据结构--树与二叉树
数据结构分类
集合
线性结构(一对一)
树形结构(一对多)
图结构(多对多)
数据结构三要素
1、逻辑结构
2、数据的运算
3、存储结构（物理结构）
树的概念
树的分类
满二叉树和完全二叉树
二叉排序树
平衡二叉树
二叉树分类总结
二叉树的存储结构
顺序存储
链式存储
二叉树的遍历
先序遍历
class Node {constructor(value) {this.value = value;this.left = null;this.right = null;}}const tree = new Node('A');tree.left = new Node('B');tree.right = new Node('C');tree.left.left = new Node('D');tree.left.right = new Node('E');tree.right.left = new Node('F');tree.right.right = new Node('G');// 前序遍历const preorderTraversal = (root) => {if (root === null) return;console.log(root.value); // 访问根节点preorderTraversal(root.left); // 遍历左子树preorderTraversal(root.right); // 遍历右子树};preorderTraversal(tree);中序遍历
class Node {constructor(value) {this.value = value;this.left = null;this.right = null;}}const tree = new Node('A');tree.left = new Node('B');tree.right = new Node('C');tree.left.left = new Node('D');tree.left.right = new Node('E');tree.right.left = new Node('F');tree.right.right = new Node('G');// 前序遍历const preorderTraversal = (root) => {if (root === null) return;preorderTraversal(root.left); // 遍历左子树console.log(root.value); // 访问根节点preorderTraversal(root.right); // 遍历右子树};preorderTraversal(tree);后序遍历
class Node {constructor(value) {this.value = value;this.left = null;this.right = null;}}const tree = new Node('A');tree.left = new Node('B');tree.right = new Node('C');tree.left.left = new Node('D');tree.left.right = new Node('E');tree.right.left = new Node('F');tree.right.right = new Node('G');// 前序遍历const preorderTraversal = (root) => {if (root === null) return;preorderTraversal(root.left); // 遍历左子树preorderTraversal(root.right); // 遍历右子树console.log(root.value); // 访问根节点};preorderTraversal(tree);遍历构造二叉树
const generateTreeHelper = (node, n) => {node.left = new TreeNode(n);node.right = new TreeNode(n);n -= 1;if (n > 0) {generateTreeHelper(node.left, n);generateTreeHelper(node.right, n);}};const generateTree = (n) => {let root = null;if (n <= 0) return root;root = new TreeNode(3);generateTreeHelper(root, n - 1);return root;};console.log('--------root', generateTree(3));