数据结构--树与二叉树

数据结构分类

集合

线性结构(一对一)

树形结构(一对多)

图结构(多对多)

数据结构三要素

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));