数据结构—树、二叉树和平衡二叉树(1)
树以及树的基本概念
树结构是一种非线性存储结构，n 个结点组成具有层次关系的有限集合，其中 n >= 0 当 n = 0 时称为空树
存储的是具体一对多的关系的数据元素的集合
结点
度
根结点
子树
树的性质
有且只有一个根结点，根结点没有父节点
树和链表
链表可以看成树的从根节点触发到叶子节点一个路径
二叉树
非线性数据结构
数据元素(结点)按分支关系组织起来的结构
每个结点最多有两个子树的有序树
满二叉树(perfect binary tree)
叶子节点都在同一层并且除叶子节点外的所有节点都有两个子节点
完全二叉树(complete binary tree)
对于一颗二叉树，如果深度 d (d>1) 除了 d 层外所有节点构成满二叉树，且 d 层所有节点从左向右连续紧密排列
叶子结点只可能在最大的两层出现
对任意结点，如果其右子树的最大层次为 L，则其左子树的最大层次为 L 或者 L+1(子树必须向左对齐)
度为 1 的结点只有 0 或 1 个
完全二叉树性质
叶子节点(度为 0 的结点)
n=n0+n1+n2n = n_0 + n_1 + n_2n=n0+n1+n2 n0=n2+1n_0 = n_2 + 1n0=n2+1
n=2n0+n1−1n = 2n_0 + n_1 - 1n=2n0+n1−1
非完全二叉树
二叉树的存储方式
链式存储(图)
线性存储(图)
二叉树的遍历
BFS(广度优先搜索)
层序遍历
DFS(深度优先搜索)
分别可以用递归法和迭代法来实现前、中或后序实现
前序(中左右)
中序(左中右)
后序(左右中 )
二叉搜索树
二叉搜索对树结构，
字典树
平衡二叉树
一颗空树或者左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一个平衡二叉树，同时，平衡二叉树必定是二叉搜索树
代码实现
function node(value){ return{ value, children:[], } } const a = node('a'); const b = node('b'); const c = node('c'); const d = node('d'); const e = node('e'); const f = node('f'); const g = node('g'); const h = node('h'); const i = node('i'); const j = node('j'); const k = node('k'); const l = node('l'); const m = node('m'); a.children.push(b,c,d); b.children.push(e); e.children.push(k,l); c.children.push(f,g,h); h.children.push(m); d.children.push(i,j); 复制代码//递归函数的参数和返回值 //终止条件 //单层递归的逻辑 const breathFirst = (startNode,cb)=>{ // console.log(startNode) let queue = [startNode]; // console.log(queue.shift()) while(queue.length>0){ let node = queue.shift(); // console.log(node) cb(node); queue.push(...node.children) } } 复制代码breathFirst(a,function(node){ console.log(node.value) }) 复制代码/** * * @param {*} node * @param {*} cb */ const depthFirstPreOrder = (node,cb)=>{ cb(node); node.children.forEach(node=>{ depthFirstPreOrder(node,cb) }) } 复制代码const depthFirstPostOder = (node,cb)=>{ node.children.forEach(node=>{ depthFirstPostOder(node,cb) }); cb(node) } // depthFirstPreOrder(a,function(node){ // console.log(node.value) // }) // depthFirstPostOder(a,function(node){ // console.log(node.value) // })
作者：ti138729
链接：https://juejin.cn/post/7018861117728374791