文章目录
- 二叉树
- 1. 递归遍历
- 2. 层序遍历
- 3. 多叉树遍历
二叉树
【子节点】：每个节点下方相连的节点
【父节点】：每个节点上方相连的节点
【根节点】：最上方没有父节点的节点
【叶子节点】：最下方没有子节点的节点
【最大深度】：树的最大层数
【高度】：节点数减一，即枝数。
【满二叉树(Perfect Binary Tree)】：深度为h，则总节点数：2^h - 1
Full Binary Tree 是指一棵二叉树的所有节点要么没有孩子节点，要么有两个孩子节点。
【完全二叉树(Complete Binary Tree)】：二叉树的每一层的节点都紧靠左排列，且除了最后一层，其他每层都必须是满的。完全二叉树可以用数组来存储，不需要真的构建链式节点。完全二叉树的左右子树中，至少有一棵是满二叉树
【平衡二叉树】：每个节点的左右子树的高度差不超过 1。
设平衡二叉树中共有 N 个节点，则高度是 O(logN)
1 / \2 3/ / \
4 5 6\ \8 7 （不符合）
【二叉搜索树（BST）】：对于树中的每个节点，其左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。左小右大。中序遍历结果是有序的，会从小到大排序。
7/ \4 9/ \ \
1 8 10 （不符合）
1. 递归遍历
//二叉树节点
class TreeNode {constructor(val) {this.val = val;this.left = null;this.right = null;}
}//递归遍历框架——从左节点到右节点，依赖函数堆栈递归
//更改左右调用顺序实现先右后左
var traverse =function(root) {if (root === null) {return;}//先序遍历——中左右traverse(root.left);//中序遍历——左中右traverse(root.right);//后序遍历——左右中
}
2. 层序遍历
3种层序遍历写法，借助队列
//方法1
//最简单，但是无法知道当前节点在第几层
var levelOrderTraverse1 = function(root) {if (root === null) {return;}var q = [];q.push(root);while(q.length !== 0) {var cur = q.shift();//删除首个元素并返回，其他元素向前顺移// 访问cur节点的各种操作console.log(cur.val);//把cur的左右子节点加入队列if (cur.left != null) {q.push(cur.left);}if (cur.right != null) {q.push(cur.right);}}
}//写法2
//能记录对应节点的层数
var levelOrderTraverse2 = function(root) {if (root === null) {return;}let q = [];q.push(root);let depth = 1; //记录当前层数while(q.length !== 0) {let sz = q.length;for (let i = 0; i < sz; i++) {//i可以记录当前节点是当前层的第几个元素let cur = q.shift();console.log ("depth = " + depth + ", val = " + cur.val);if (cur.left !== null) {q.push(cur.left);}if (cur.right !== null) {q.push(cur.right);}}depth++;}
}//写法3
//适用于路径具有权重的树
function State(node, depth) {this.node = node;this.depth = depth;
}var levelOrderTraverse3 = function(root) {if (root === null) {return;}var q = [];q.push(new State(root, 1)); //根节点的路径权重和是1while(q.length !== 0) {var cur = q.shift();console.log("depth = " + cur.depth + ", val = " + cur.node.val);if (cur.node.left !== null) {q.push(new State(cur.node.left, cur.depth + 1));}if (cur.node.right !== null) {q.push(new State(cur.node.right, cur.depth + 1));}}
}
3. 多叉树遍历
- 递归遍历（深度优先遍历DFS）
//多叉树的递归遍历
var Node =function(val) {this.val = val;this.children = [];
}//前序遍历
function preOrderTrees(root, callback) {if (root === null) {return;}//先处理当前节点callback(root.val);//递归遍历所有子节点for (const child of root.children) {preOrderTrees(child, callback);}
}//后序遍历
function postOrderTree(root, callback) {if (root === null) {return;}for(const child of root.children) {postOrderTree(child, callback);}//最后处理该节点callback(root.val);
}const root = new Node('0');
const node1 = new Node('1');
const node2 = new Node('2');
const node3 = new Node('3');
const node4 = new Node('4');
const node5 = new Node('5');
const node6 = new Node('6');
const node7 = new Node('7');root.children = [node1, node2,node3];
node2.children = [node4, node5];
node3.children = [node6, node7];console.log("先序遍历");
preOrderTrees(root, val => console.log(val));
console.log("后序遍历");
postOrderTree(root, val => console.log(val));
- 层序遍历（广度优先遍历BFS）
// 多叉树节点定义
var Node = function(val) {this.val = val;this.children = [];};// 层序遍历函数（直接输出结果）function BFS(root, callback) {if (root === null) return;const q = [root];while (q.length !== 0) {const cur = q.shift();callback(cur.val); // 触发回调输出值for (const child of cur.children) {q.push(child);}}}// 1. 构建树结构const root = new Node('0');const node1 = new Node('1');const node2 = new Node('2');const node3 = new Node('3');const node4 = new Node('4');const node5 = new Node('5');const node6 = new Node('6');root.children = [node1, node2, node3];node1.children = [node4, node5];node2.children = [node6];console.log('层序遍历结果:');BFS(root, val => console.log(val));
