当前位置: 首页> 教育> 就业 > 泰州cms建站模板_湘阴网站设计_百度用户服务中心客服电话_精准获客

泰州cms建站模板_湘阴网站设计_百度用户服务中心客服电话_精准获客

时间:2025/7/11 0:47:39来源:https://blog.csdn.net/m0_74556076/article/details/146267328 浏览次数:0次
泰州cms建站模板_湘阴网站设计_百度用户服务中心客服电话_精准获客

文章目录

    • 二叉树
      • 1. 递归遍历
      • 2. 层序遍历
      • 3. 多叉树遍历

二叉树

【子节点】:每个节点下方相连的节点

【父节点】:每个节点上方相连的节点

【根节点】:最上方没有父节点的节点

【叶子节点】:最下方没有子节点的节点

【最大深度】:树的最大层数

【高度】:节点数减一,即枝数。

满二叉树(Perfect Binary Tree)】:深度为h,则总节点数:2^h - 1

Full Binary Tree 是指一棵二叉树的所有节点要么没有孩子节点,要么有两个孩子节点。

完全二叉树(Complete Binary Tree)】:二叉树的每一层的节点都紧靠左排列,且除了最后一层,其他每层都必须是满的。完全二叉树可以用数组来存储,不需要真的构建链式节点。完全二叉树的左右子树中,至少有一棵是满二叉树

平衡二叉树】:每个节点的左右子树的高度差不超过 1

设平衡二叉树中共有 N 个节点,则高度是 O(log⁡N)

    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));
关键字:泰州cms建站模板_湘阴网站设计_百度用户服务中心客服电话_精准获客

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: