共计 1966 个字符,预计需要花费 5 分钟才能阅读完成。
什么是二叉树
在计算机科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具备左右秩序,不能随便颠倒。
二叉树的第 i 层至少有 2^{i-1} 个结点;
深度为 k 的二叉树至少有 2^k- 1 个结点;
对任何一棵二叉树 T,若树叶总数为 n_0,分支度为 2 的总数为 n_2,则 n_0=n_2+1。
一棵深度为 k,且有 2^k- 1 个节点称之为满二叉树;
深度为 k,有 n 个节点的二叉树,当且仅当其每一个节点都与深度为 k 的满二叉树中,序号为 1 至 n 的节点对应时,称之为齐全二叉树。
非凡类型
齐全二叉树 | 完满二叉树 | |
---|---|---|
总节点 k | 2^ (h − 1) <= k <= 2^(h − 1) | k = 2^h − 1 |
树高 h | h = l o g 2 k + 1 | h = l o g 2 (k + 1) |
深度优先遍历
英文缩写为 DFS 即 Depth First Search。在深度优先级中,咱们心愿从根结点拜访最远的结点。前序,中序和后序遍历都是深度优先遍历的特例。
先来看一张图, 一眼理解这三种遍历:
作为前端, 我是必定先用 JS 来实现这些遍历的, 先定义一个二叉树的构造:
const nodes = {
node: 6,
left: {
node: 5,
left: {node: 4},
right: {node: 3}
},
right: {
node: 2,
right: {node: 1}
}
}
先序遍历
let list = []
function preOrder(node) {if (!(node == null)) {list.push(node.node);
preOrder(node.left);
preOrder(node.right);
}
}
执行: preOrder(nodes)
打印 list
后果: [6, 5, 4, 3, 2, 1]
中序遍历
let list = []
function inOrder(node) {if (!(node == null)) {inOrder(node.left);
list.push(node.node);
inOrder(node.right);
}
}
执行: inOrder(nodes)
打印 list
后果: [4, 5, 3, 6, 2, 1]
后序遍历
let list = []
function postOrder(node) {if (!(node == null)) {postOrder(node.left);
postOrder(node.right);
list.push(node.node);
}
}
执行: postOrder(nodes)
打印 list
后果: [4, 3, 5, 1, 2, 6]
广度优先遍历
英文缩写为 BFS 即 Breadth FirstSearch。其过程测验来说是对每一层节点顺次拜访,拜访完一层进入下一层,而且每个节点只能拜访一次。广度遍历即咱们寻常所说的档次遍历。
const levelOrder = function (root) {if (root == null) {return []
}
let result = []
let queue = [root]
while (queue.length) {
// 每一层的节点数
let level = queue.length
let currLevel = []
// 每次遍历一层元素
for (let i = 0; i < level; i++) {
// 以后拜访的节点出队
let curr = queue.shift()
curr.left && queue.push(curr.left)
curr.right && queue.push(curr.right)
currLevel.push(curr.node)
}
result.push.apply(result, currLevel)
}
return result
}
打印后果: [6, 5, 2, 4, 3, 1]
currLevel 中的打印: [6]
[5,2]
[4,3,1]
这个思路比拟好了解, 倒是还不够好
优化
const levelOrder = function (root) {if (!root) return [];
let queue = [root];
let res = [];
while (queue.length) {let item = queue.shift();
res.push(item.node);
item.left && queue.push(item.left);
item.right && queue.push(item.right);
}
return res;
}
打印后果: [6, 5, 2, 4, 3, 1]
这种算法只是用了一个队列, 成果较好
总结
这是二叉树相干的第一篇, 比拟根底, 后续还会更新
仓库地址: https://github.com/Grewer/notes
参考:
- https://zh.wikipedia.org/wiki…
- https://blog.csdn.net/weixin_…
相干系列
- 二叉树 (一): 遍历
- 二叉树 (二): 补充
- 二叉树 (三): 二叉查找树