一、树
树(Tree)是一种非常常见的数据结构,它模拟了自然界中树的结构,由节点(或称为顶点)组成,并且具有层次化的组织形式。树结构在计算机科学中广泛应用,例如在组织数据、管理信息层次以及算法设计中。
1.基本概念
节点(Node)
- 根节点(Root):树的最顶端节点,没有父节点。
- 内部节点(Internal Node):至少有一个子节点的节点。
- 叶节点(Leaf Node)或外部节点(External Node):没有子节点的节点。
- 子节点(Child):直接连接到另一个节点的节点。
- 父节点(Parent):有子节点的节点。
- 兄弟节点(Sibling):共享相同父节点的节点。
边(Edge)
连接两个节点的线称为边,表示节点之间的关系。
层(Level)
- 根节点位于第0层。
- 每个节点的层数是其父节点的层数加1。
高度(Height)和深度(Depth)
- 高度:节点的高度是指从该节点到最远叶子节点的最长路径上的边的数目。树的高度是其根节点的高度。
- 深度:节点的深度是指从根节点到该节点的路径上的边的数目。
树的种类
- 二叉树(Binary Tree):每个节点最多有两个子节点的树。
- 满二叉树:每个节点都有0个或2个子节点。
- 完全二叉树:除了最后一层外,每一层都被完全填满,最后一层的节点都靠左排列。
- 平衡二叉树(AVL Tree):任何节点的两个子树的高度差都不超过1。
- 多叉树(N-ary Tree):每个节点可以有多个子节点。
- 二叉搜索树(Binary Search Tree, BST):左子树的所有节点值小于根节点值,右子树的所有节点值大于根节点值。
- 堆(Heap):是一种特殊的完全二叉树,通常用于实现优先队列。
树的遍历
树结构的应用非常广泛,例如在文件系统的目录结构、组织结构、决策树、XML和HTML文档解析等领域都有应用。树的实现和操作通常比线性数据结构(如数组、链表)更复杂,但它们提供了强大的功能和灵活性。
深度优先遍历(DFS):从根节点开始,优先深入每个分支的子节点,直到叶节点,之后再回溯到父节点处理下一个分支。DFS 在普通树中的常见方式是先序遍历(pre-order traversal),即先访问节点本身,然后递归访问它的所有子节点。
广度优先遍历(BFS):层次遍历,从根节点开始,逐层访问每一层的节点。在普通树中,BFS 也叫做层次遍历(Level Order Traversal)。
2.深度优先遍历实现
在普通树中,DFS 的顺序通常是:先访问节点本身,再递归访问它的所有子节点。
class TreeNode {
constructor(value) {
this.value = value;
this.children = []; // children 是一个子节点数组
}
}
深度优先遍历 - 递归实现
//深度优先遍历
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd',
children: [],
},
{
val: 'e',
children: [],
}
],
},
{
val: 'c',
children: [
{
val: 'f',
children: [],
},
{
val: 'g',
children: [],
}
],
}
],
};
const dfs = (root) => {
console.log(root.val);
// root.children.forEach((child) => { dfs(child) });//可以直接写成下一行的样式
root.children.forEach(dfs);
};
dfs(tree);
深度优先遍历 - 非递归实现(使用栈)
function dfsIterative(root) {
if (root === null) return;
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
console.log(node.value); // 访问当前节点
for (let i = node.children.length - 1; i >= 0; i--) {
stack.push(node.children[i]); // 逆序将子节点压栈
}
}
}
3.广度优先遍历实现
对于普通树的 BFS,可以使用队列来实现逐层遍历:
function bfs(root) {
if (root === null) return;
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
console.log(node.value); // 访问当前节点
for (let child of node.children) {
queue.push(child); // 将所有子节点入队
}
}
}
//广度优先遍历算法口诀
//1.新建一个队列,把根节点入队;2.把队头出队并访问;
//3.把队头的children挨个入队;4.重复第二、第三步,直到队列为空。
//广度优先遍历
const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd',
children: [],
},
{
val: 'e',
children: [],
}
],
},
{
val: 'c',
children: [
{
val: 'f',
children: [],
},
{
val: 'g',
children: [],
}
],
}
],
};
const bfs = (root) => {
const q = [root];
while (q.length > 0) {
const n = q.shift();
console.log(n.val);
n.children.forEach((child) => {
q.push(child);
});
}
}
bfs(tree);
二、二叉树
二叉树(Binary Tree)是一种特殊的树结构,其中每个节点最多有两个子节点,通常称为左子节点和右子节点。
1.基本概念
基本定义
- 节点(Node):二叉树的基本单元,包含数据元素和两个指向其他节点的指针(可能为空)。
- 根节点(Root):二叉树的顶端节点,没有父节点。
- 子节点(Child):由父节点的指针指向的节点。
- 左子节点(Left Child):父节点的左侧子节点。
- 右子节点(Right Child):父节点的右侧子节点。
- 叶节点(Leaf):没有子节点的节点。
- 内部节点(Internal Node):至少有一个子节点的节点。
- 兄弟节点(Sibling):共享相同父节点的节点。
特殊类型的二叉树
- 满二叉树:每一层的节点数都是最大节点数,即每一层都是满的。
- 完全二叉树:除了最后一层外,每一层都是满的,并且最后一层的节点都靠左排列。
- 平衡二叉树(AVL Tree):任何节点的两个子树的高度差都不超过1。
- 二叉搜索树(Binary Search Tree, BST):左子树的所有节点值小于根节点值,右子树的所有节点值大于根节点值。
二叉树的性质
- 二叉树的第 i 层最多有 2^i 个节点(i 从 0 开始)。
- 高度为 h 的二叉树最多有 2^(h+1) - 1 个节点。
- 对于任何非空二叉树,如果叶子数为 N0,度为 2 的节点数为 N2,则有 N0 = N2 + 1。
二叉树的遍历
二叉树的遍历是指按照某种顺序访问树中的每个节点,以下是四种常见的遍历方法:
-
前序遍历(Pre-order Traversal):
- 访问根节点。
- 前序遍历左子树。
- 前序遍历右子树。
-
中序遍历(In-order Traversal):
- 中序遍历左子树。
- 访问根节点。
- 中序遍历右子树。
-
后序遍历(Post-order Traversal):
- 后序遍历左子树。
- 后序遍历右子树。
- 访问根节点。
-
层序遍历(Level-order Traversal):
- 从根节点开始,按从上到下、从左到右的顺序访问每一层的节点。
二叉树的实现
在计算机中,二叉树通常通过指针或引用来实现。以下是一个简单的二叉树节点的JavaScript实现:
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
通过创建 TreeNode
实例并适当地链接它们,我们可以构建出各种二叉树结构。
二叉树是许多高级数据结构和算法的基础,例如堆、优先队列、平衡树和二叉搜索树等。它们在计算机科学中扮演着重要角色,因为它们提供了一种有效的组织和处理数据的方法。
//先序遍历二叉树
const bt = {
val: 1,
left: {
val: 2,
left: {
val: 4,
left: null,
right: null,
},
right: {
val: 5,
left: null,
right: null,
},
},
right: {
val: 3,
left: {
val: 6,
left: null,
right:null,
},
right: {
val: 7,
left: null,
right:null,
}
}
}
module.exports = bt;
2.二叉树的先序遍历
非递归实现思路:
- 初始化一个空栈。
- 将根节点压入栈中。
- 当栈不为空时:
- 弹出栈顶节点,并访问它。
- 先将右子节点压入栈(如果存在)。
- 再将左子节点压入栈(如果存在)
//先序遍历
//导入二叉树的结构
const bt = require('./bt.js');
// 递归的方法
// console.log(bt);
// const preorder = (root) => {
// if (!root) return;
// console.log(root.val);
// preorder(root.left);
// preorder(root.right);
// }
// 非递归的方法
const preorder = (root) => {
if (!root) return;
const stack = [root];
while (stack.length) {
const n = stack.pop();
console.log(n.val);
// 先右后左,因为栈是后进先出
if (n.right) stack.push(n.right);
if (n.left) stack.push(n.left);
}
}
preorder(bt);
3.二叉树的中序遍历
非递归实现思路:
- 初始化一个空栈。
- 将当前节点压入栈,并将当前节点更新为其左子节点,重复此操作直到当前节点为空。
- 弹出栈顶节点,并访问它,然后将当前节点更新为其右子节点。
- 重复步骤2和3,直到栈为空且当前节点为空。
//中序遍历
//导入二叉树的结构
// 递归版
const bt = require('./bt.js');
// console.log(bt);
// const inorder = (root) => {
// if (!root) return;
// inorder(root.left);
// console.log(root.val);
// inorder(root.right);
// }
// 非递归的方法
const inorder = (root) => {
if (!root) return;
const stack = [];
let p = root;
while (p || stack.length) {
while (p) {
stack.push(p);
p = p.left;
}
const n = stack.pop();
console.log(n.val);
p = n.right;
}
};
inorder(bt);
4.二叉树的后序遍历
非递归实现思路:
后序遍历的非递归实现相对复杂,因为需要确保在访问一个节点之前,它的左右子节点已经被访问过。一种方法是在先序遍历的基础上稍作修改,然后反转结果。
- 初始化一个空栈。
- 将根节点压入栈中。
- 当栈不为空时:
- 弹出栈顶节点,并访问它。
- 先将左子节点压入栈(如果存在)。
- 再将右子节点压入栈(如果存在)。
- 将遍历的结果反转。
function postOrderTraversalIterative(root) {
if (!root) return;
const stack = [root];
const result = [];
while (stack.length > 0) {
const node = stack.pop();
result.push(node.value); // 先将节点值加入结果数组
// 先左后右,因为最后需要反转结果
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}
// 反转结果数组得到后序遍历的顺序
while (result.length > 0) {
console.log(result.pop());
}
}
也可以使用两个栈。
//后序遍历
//导入二叉树的结构
const bt = require('./bt.js');
// console.log(bt);
// const postorder = (root) => {
// if (!root) return;
// postorder(root.left);
// postorder(root.right);
// console.log(root.val);
// }
// 非递归的方法
const postorder = (root) => {
if (!root) return;
const stack = [root];
const outputstack = [];
while (stack.length) {
const n = stack.pop();
outputstack.push(n);
if (n.left) stack.push(n.left);
if (n.right) stack.push(n.right);
}
while (outputstack.length) {
const n = outputstack.pop();
console.log(n.val);
}
};
postorder(bt);
5.二叉树的深度优先遍历
// 二叉树的深度优先遍历
const bt = require('./bt.js');
const bdfs = (root) => {
if (!root) return;
console.log(root.val);
bdfs(root.left);
bdfs(root.right);
};
bdfs(bt);
6.二叉树的广度优先遍历
// 二叉树的广度优先遍历
const bt = require('./bt.js');
const bbfs = (root) => {
if (!root) return;
const q = [root];
while (q.length > 0) {
const n = q.shift();
console.log(n.val);
if (n.left) q.push(n.left);
if (n.right) q.push(n.right);
}
}
// 如果想知道每个结点是第几层
// const bbfs = (root) => {
// if (!root) return;
// const q = [[root, 1]];
// while (q.length > 0) {
// const [n, l] = q.shift();
// console.log(n.val, l);
// if (n.left) q.push([n.left, l + 1]);
// if (n.right) q.push([n.right, l + 1]);
// }
// };
bbfs(bt);
标签:遍历,const,val,JS,之树,二叉树,root,节点
From: https://blog.csdn.net/qq_56101688/article/details/143608855