前言
上一節(jié)，簡(jiǎn)單概述了樹(shù)這種數(shù)據(jù)結(jié)構(gòu)，以及樹(shù)結(jié)構(gòu)向下，具有某些一些特征的樹(shù)，比如二叉樹(shù)，B樹(shù)，B+樹(shù)，堆等。其中，二叉樹(shù)是一個(gè)很重要的模塊。也是在一些技術(shù)面試中，可能會(huì)問(wèn)到的問(wèn)題。本節(jié)，我們就二叉樹(shù)，做詳細(xì)介紹。
1. 存儲(chǔ)
二叉樹(shù)是一個(gè)邏輯結(jié)構(gòu)，底層可以用數(shù)組或者鏈表存儲(chǔ)。
1.1 數(shù)組存儲(chǔ)
使用數(shù)組存儲(chǔ)時(shí)，會(huì)按照層級(jí)順序把二叉樹(shù)的節(jié)點(diǎn)放到數(shù)組中對(duì)應(yīng)的位置上。如果某一個(gè)節(jié)點(diǎn)的左孩子或右孩子空缺，則數(shù)組的相應(yīng)位置也空出來(lái)。
由此，可以得出結(jié)論：在用數(shù)組存儲(chǔ)時(shí)，
- 一個(gè)父節(jié)點(diǎn)的下標(biāo)是n，那么它的左孩子節(jié)點(diǎn)下標(biāo)就是2×n+1、右孩子節(jié)點(diǎn)下標(biāo)就是2x(n+1)
- 對(duì)于一個(gè)稀疏的二叉樹(shù)（孩子不滿）來(lái)說(shuō)，用數(shù)組表示法是非常浪費(fèi)空間的
- 所以二叉樹(shù)一般用鏈表存儲(chǔ)實(shí)現(xiàn)。（二叉堆除外，因?yàn)?strong>二叉堆是一個(gè)完全二叉樹(shù)，節(jié)點(diǎn)基本都是滿的）
1.2 鏈表存儲(chǔ)
在使用鏈表存儲(chǔ)時(shí)，二叉樹(shù)的每個(gè)節(jié)點(diǎn)至少包含三部分：
- 存儲(chǔ)數(shù)據(jù)的data變量
- 指向左孩子的left指針
- 指向右孩子的right指針
如下圖所示：
2. 遍歷
二叉樹(shù)，是典型的非線性數(shù)據(jù)結(jié)構(gòu)，遍歷時(shí)需要把非線性關(guān)聯(lián)的節(jié)點(diǎn)轉(zhuǎn)化成一個(gè)線性的序列，以不同的方式來(lái)遍歷，遍歷出的序列順序也不同。
2.1 深度優(yōu)先遍歷
所謂深度優(yōu)先，就是偏向于縱深，“一頭扎到底”的訪問(wèn)方式。
2.1.1 前序遍歷
二叉樹(shù)的前序遍歷，輸出順序是根節(jié)點(diǎn)、左子樹(shù)、右子樹(shù)。
步驟如下：
- 首先輸出的是根節(jié)點(diǎn)1
- 由于根節(jié)點(diǎn)1存在左孩子，輸出左孩子節(jié)點(diǎn)2
- 由于節(jié)點(diǎn)2也存在左孩子，輸出左孩子節(jié)點(diǎn)4
- 節(jié)點(diǎn)4既沒(méi)有左孩子，也沒(méi)有右孩子，那么回到節(jié)點(diǎn)2，輸出節(jié)點(diǎn)2的右孩子節(jié)點(diǎn)5
- 節(jié)點(diǎn)5既沒(méi)有左孩子，也沒(méi)有右孩子，那么回到節(jié)點(diǎn)1，輸出節(jié)點(diǎn)1的右孩子節(jié)點(diǎn)3
- 節(jié)點(diǎn)3沒(méi)有左孩子，但是有右孩子，因此輸出節(jié)點(diǎn)3的右孩子節(jié)點(diǎn)6
到此為止，所有的節(jié)點(diǎn)都遍歷輸出完畢
2.1.2 中序遍歷
二叉樹(shù)的中序遍歷，輸出順序是左子樹(shù)、根節(jié)點(diǎn)、右子樹(shù)。
步驟如下：
- 首先訪問(wèn)根節(jié)點(diǎn)的左孩子，如果這個(gè)左孩子還擁有左孩子，則繼續(xù)深入訪問(wèn)下去，一直找到不再有左孩子 的節(jié)點(diǎn)，并輸出該節(jié)點(diǎn)。顯然，第一個(gè)沒(méi)有左孩子的節(jié)點(diǎn)是節(jié)點(diǎn)4
- 依照中序遍歷的次序，接下來(lái)輸出節(jié)點(diǎn)4的父節(jié)點(diǎn)2
- 再輸出節(jié)點(diǎn)2的右孩子節(jié)點(diǎn)5
- 以節(jié)點(diǎn)2為根的左子樹(shù)已經(jīng)輸出完畢，這時(shí)再輸出整個(gè)二叉樹(shù)的根節(jié)點(diǎn)1
- 由于節(jié)點(diǎn)3沒(méi)有左孩子，所以直接輸出根節(jié)點(diǎn)1的右孩子節(jié)點(diǎn)3
- 最后輸出節(jié)點(diǎn)3的右孩子節(jié)點(diǎn)6
到此為止，所有的節(jié)點(diǎn)都遍歷輸出完畢
2.1.3 后序遍歷
二叉樹(shù)的后序遍歷，輸出順序是左子樹(shù)、右子樹(shù)、根節(jié)點(diǎn)
步驟如下：
- 首先訪問(wèn)根節(jié)點(diǎn)的左孩子，如果這個(gè)左孩子還擁有左孩子，則繼續(xù)深入訪問(wèn)下去，一直找到不再有左孩子 的節(jié)點(diǎn)，并輸出該節(jié)點(diǎn)。顯然，第一個(gè)沒(méi)有左孩子的節(jié)點(diǎn)是節(jié)點(diǎn)4
- 輸出右節(jié)點(diǎn)5
- 輸出節(jié)點(diǎn)4的父節(jié)點(diǎn)2
- 以節(jié)點(diǎn)2為根的左子樹(shù)已經(jīng)輸出完畢，這時(shí)再輸出整個(gè)二叉樹(shù)的右子樹(shù)
- 訪問(wèn)根節(jié)點(diǎn)的右孩子，如果這個(gè)右孩子擁有左孩子，則繼續(xù)深入訪問(wèn)下去，一直找到不再有左
孩子 的節(jié)點(diǎn)，如果沒(méi)有左孩子則找右孩子，并輸出該節(jié)點(diǎn)6 - 輸出節(jié)點(diǎn)6的父節(jié)點(diǎn)3
到此為止，所有的節(jié)點(diǎn)都遍歷輸出完畢。
2.2 廣度優(yōu)先遍歷
也叫層序遍歷，顧名思義，就是二叉樹(shù)按照從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的層次關(guān)系，一層一層橫向遍歷各個(gè)節(jié)點(diǎn)。
二叉樹(shù)同一層次的節(jié)點(diǎn)之間是沒(méi)有直接關(guān)聯(lián)的，利用隊(duì)列可以實(shí)現(xiàn)
2.3 遍歷代碼實(shí)現(xiàn)
2.3.1 定義樹(shù)節(jié)點(diǎn)
package org.wanlong.tree;
/**
* @author wanlong
* @version 1.0
* @description: 樹(shù)節(jié)點(diǎn)定義
* @date 2023/6/1 11:22
*/
public class TreeNode<T> {
//數(shù)據(jù)
T data;
//左孩子
TreeNode left;
//右孩子
TreeNode right;
public TreeNode(T data) {
this.data = data;
}
}
2.3.2 定義樹(shù)節(jié)點(diǎn)維護(hù)方法
package org.wanlong.tree;
/**
* @author wanlong
* @version 1.0
* @description: 二叉樹(shù)
* @date 2023/6/1 11:24
*/
public class BinaryTree {
TreeNode root;
public void insertNode(int data) {
root = insert(root, data);
}
/**
* @param node: 基準(zhǔn)節(jié)點(diǎn)
* @param data: 待插入數(shù)據(jù)
* @return org.wanlong.tree.TreeNode
* @Description:往一個(gè)節(jié)點(diǎn)下面插入data數(shù)據(jù)
* @Author: wanlong
* @Date: 2023/6/1 11:28
**/
public TreeNode insert(TreeNode<Integer> node, Integer data) {
//如果基準(zhǔn)節(jié)點(diǎn)為空，創(chuàng)建新的節(jié)點(diǎn)插入
if (node == null) {
return new TreeNode(data);
}
//如果待插入數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，插入左子樹(shù)
if (data < node.data) {
//遞歸確定插入左子樹(shù)的位置，插入后，返回左子樹(shù)指針
node.left = insert(node.left, data);
//如果待插入節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)，插入右子樹(shù)
} else if (data > node.data) {
node.right = insert(node.right, data);
} else {
node.data = data;
}
return node;
}
}
2.3.3 前序遍歷代碼實(shí)現(xiàn)
/**
* @param node:
* @return void
* @Description: 前序遍歷節(jié)點(diǎn) 先根，再左再右
* @Author: wanlong
* @Date: 2023/6/1 11:38
**/
public void preOrder(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.data);
preOrder(node.left);
preOrder(node.right);
}
2.3.4 中序遍歷代碼實(shí)現(xiàn)
/**
* @param node:
* @return void
* @Description:中序遍歷 先左 再根 再右
* @Author: wanlong
* @Date: 2023/6/1 11:41
**/
public void middleOrder(TreeNode node) {
if (node == null) {
return;
}
middleOrder(node.left);
System.out.println(node.data);
middleOrder(node.right);
}
2.3.5 后序遍歷代碼實(shí)現(xiàn)
/**
* @param node:
* @return void
* @Description:后序遍歷 先左，再右，再根
* @Author: wanlong
* @Date: 2023/6/1 15:21
**/
public void postOrder(TreeNode node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.data);
}
2.3.6 廣度優(yōu)先遍歷代碼實(shí)現(xiàn)
廣度優(yōu)先遍歷可用節(jié)點(diǎn)入隊(duì)出隊(duì)的方式便捷實(shí)現(xiàn)，具體代碼實(shí)現(xiàn)如下文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-468655.html
/**
* @Description: 廣度優(yōu)先遍歷
* @Author: wanlong
* @Date: 2023/6/1 15:29
* @param root:
* @return void
**/
public void wideOrder(TreeNode root){
//廣度優(yōu)先遍歷可用隊(duì)列出隊(duì)入隊(duì)的方式快速實(shí)現(xiàn)
LinkedList<TreeNode> queue = new LinkedList<>();
//根節(jié)點(diǎn)入隊(duì)
queue.offer(root);
while (!queue.isEmpty()){
//隊(duì)列頭節(jié)點(diǎn)出隊(duì)
TreeNode node = queue.poll();
//打印數(shù)據(jù)
System.out.println(node.data);
//左右節(jié)點(diǎn)入隊(duì)
if (node.left!=null){
queue.offer(node.left);
}
if (node.right!=null){
queue.offer(node.right);
}
}
}
2.3.7 遍歷結(jié)果測(cè)試
package org.wanlong.tree;
import org.junit.BeforeClass;
import org.junit.Test;
/**
* @author wanlong
* @version 1.0
* @description: 測(cè)試樹(shù)的遍歷
* @date 2023/6/1 15:15
*/
public class Client {
static BinaryTree btt = new BinaryTree();
@BeforeClass
public static void init() {
btt.insertNode(10);
btt.insertNode(8);
btt.insertNode(11);
btt.insertNode(7);
btt.insertNode(9);
btt.insertNode(12);
}
@Test
public void testpre() {
btt.preOrder(btt.root);
//10
//8
//7
//9
//11
//12
}
@Test
public void testMiddle() {
btt.middleOrder(btt.root);
//7
//8
//9
//10
//11
//12
}
@Test
public void testpost() {
btt.postOrder(btt.root);
//7
//9
//8
//12
//11
//10
}
@Test
public void testwide(){
btt.wideOrder(btt.root);
}
//10
//8
//11
//7
//9
//12
}
以上，本人菜鳥(niǎo)一枚，如有錯(cuò)誤，請(qǐng)不吝指正。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-468655.html
到了這里，關(guān)于11. 數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
