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