建站
咨詢
售后
建站咨詢
新聞中心
一、基礎(chǔ)
二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)，其具有如下性質(zhì)：
- 二叉樹中，第 i 層最多有 2^(i-1) 個結(jié)點。
- 如果二叉樹的深度為 K，那么此二叉樹最多有 2K-1 個結(jié)點。
- 對任何一棵二叉樹，如果其葉子結(jié)點(度為0)數(shù)為m, 度為2的結(jié)點數(shù)為n, 則m = n + 1。
二、二叉樹分類
滿二叉樹
如果二叉樹中除了葉子節(jié)點，每個節(jié)點的度都為2，則此二叉樹稱為滿二叉樹。
滿二叉樹示意圖
完全二叉樹
如果二叉樹中除去最后一層節(jié)點為滿二叉樹，且最后一層的節(jié)點依次從左到右分布，則此二叉樹稱為完全二叉樹。
完全二叉樹示意圖
搜索二叉樹
如果一棵樹不為空，并且如果它的根節(jié)點左子樹不為空，那么它左子樹上面的所有節(jié)點的值都小于它的根節(jié)點的值，如果它的右子樹不為空，那么它右子樹任意節(jié)點的值都大于它的根節(jié)點的值，且左右子樹也是二叉搜索樹。
平衡二叉樹
平衡二叉樹又稱為AVL樹，是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
三、二叉樹遍歷
為了實現(xiàn)二叉樹遍歷，首先需要的有一顆二叉樹，下面先設(shè)計一個簡單的二叉樹，如下所示：
// js版本
const binaryTree = {
val: 10,
left: {
val: 8,
right: {
val: 9
}
},
right: {
val: 15
}
};
（1）先序遍歷
二叉樹的先序遍歷是按照“根節(jié)點——左節(jié)點——右節(jié)點”的順序遍歷這顆二叉樹，具體實現(xiàn)如下所示：
// 遞歸版本
function preOrderTraverse(head) {
if (head == null) {
return;
}
console.log(head.val);
preOrderTraverse(head.left);
preOrderTraverse(head.right);
}
// 對于先序遍歷的非遞歸版，準(zhǔn)備一個棧，然后將頭壓入棧中，循環(huán)彈出一個值，有右孩子的先壓右孩子，再壓左孩子
function preOrderTraverseUnRecur(head) {
if (head == null) {
return;
}
const stack = [];
stack.push(head);
while (stack.length > 0) {
head = stack.pop();
console.log(head.val);
if (head.right != null) {
stack.push(head.right);
}
if (head.left != null) {
stack.push(head.left);
}
}
}
（2）中序遍歷
二叉樹的中序遍歷是按照“左節(jié)點——根節(jié)點——右節(jié)點”的順序遍歷這顆二叉樹，具體實現(xiàn)如下所示：
// 遞歸版本
function inOrderTraverse(head) {
if (head == null) {
return;
}
inOrderTraverse(head.left);
console.log(head.val);
inOrderTraverse(head.right);
}
/**
* 非遞歸版本實現(xiàn)
* 準(zhǔn)備一個棧
* 先將左節(jié)點全壓入棧中
* 當(dāng)前節(jié)點為空，則從棧中拿一個打印，當(dāng)前節(jié)點往右跑
*/
function inOrderTraverseUnRecur(head) {
if (head == null) {
return;
}
const stack = [];
while (stack.length > 0 || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
} else {
head = stack.pop();
console.log(head.val);
head = head.right;
}
}
}
（3） 后續(xù)遍歷
二叉樹的后序遍歷是按照“左節(jié)點——右節(jié)點——根節(jié)點”的順序遍歷這顆二叉樹，具體實現(xiàn)如下所示：
// 遞歸版本
function posOrderTraverse(head) {
if (head == null) {
return;
}
posOrderTraverse(head.left);
posOrderTraverse(head.right);
console.log(head.val);
}
// 對于后續(xù)遍歷的非遞歸版，后續(xù)左-右-根，但我們可以根據(jù)根-右-左，然后將其存入一個棧中，彈出就是左-右-根
function posOrderTraverseUnRecur(head) {
if (head == null) {
return;
}
const stack = [];
const stack1 = [];
stack.push(head);
while (stack.length > 0) {
head = stack.pop();
stack1.push(head.val);
if (head.left != null) {
stack.push(head.left);
}
if (head.right != null) {
stack.push(head.right);
}
}
while (stack1.length > 0) {
console.log(stack1.pop());
}
}
（4） DFS(深度優(yōu)先遍歷)
深度優(yōu)先遍歷主要思路是從根節(jié)點開始，沿著一條路一直走到底，然后從這條路盡頭的節(jié)點回退到上一個節(jié)點，再從另一條路開始走到底，不斷遞歸重復(fù)，直到所有的頂點都遍歷完。對于二叉樹的深度優(yōu)先就是二叉樹的先序遍歷。
function DFS1(head) {
if (head == null) {
return;
}
console.log(head.val);
DFS1(head.left);
DFS1(head.right);
}
// 對于二叉樹的深度優(yōu)先就是二叉樹的先序遍歷，用一個棧實現(xiàn)
function DFS2(head) {
if (head == null) {
return;
}
const stack = [head];
while (stack.length > 0) {
head = stack.pop();
console.log(head.val);
if (head.right != null) {
stack.push(head.right);
}
if (head.left != null) {
stack.push(head.left);
}
}
}（5） BFS(廣度優(yōu)先遍歷)
廣度優(yōu)先遍歷指的是一層一層的遍歷樹的內(nèi)容，可利用隊列來實現(xiàn)。
function BFS(head) {
if (head == null) {
return;
}
const list = [head];
while (list.length > 0) {
head = list.shift();
console.log(head.val);
if (head.left != null) {
list.push(head.left);
}
if (head.right != null) {
list.push(head.right);
}
}
} 網(wǎng)頁名稱：盤二叉樹，建議從這些基礎(chǔ)搞起……
分享鏈接：http://www.5511xx.com/article/dhsdpdi.html
