資訊專欄INFORMATION COLUMN
摘要：什么是樹前面說到的幾種數(shù)據(jù)結(jié)構(gòu)都是線性的，例如鏈表?xiàng)ｊ?duì)列等，今天就來學(xué)習(xí)一種非線性的數(shù)據(jù)結(jié)構(gòu)樹。在上圖中的幾種二叉樹中，有兩個是比較特殊的，分別是滿二叉樹和完全二叉樹。除了使用數(shù)組存儲二叉樹外，最常用的便是使用鏈表法來儲存二叉樹了。
1. 什么是樹？
前面說到的幾種數(shù)據(jù)結(jié)構(gòu)都是線性的，例如鏈表、棧、隊(duì)列等，今天就來學(xué)習(xí)一種非線性的數(shù)據(jù)結(jié)構(gòu)——樹。先來看看幾種樹的結(jié)構(gòu)：
有沒有發(fā)現(xiàn)，其實(shí)樹這種結(jié)構(gòu)跟我們現(xiàn)實(shí)生活中的“樹”非常的相似，像上圖中的這棵“樹”，節(jié)點(diǎn) A 稱作 B 和 C 的父節(jié)點(diǎn)，節(jié)點(diǎn) B 和 C 在同一級，叫做兄弟節(jié)點(diǎn)。沒有父節(jié)點(diǎn)的 A 節(jié)點(diǎn)叫做根節(jié)點(diǎn)，沒有子節(jié)點(diǎn)的節(jié)點(diǎn)叫做葉子節(jié)點(diǎn)或葉節(jié)點(diǎn)，例如圖中的 D E F G。
樹的節(jié)點(diǎn)還涉及到三個概念，分別是高度、深度、層。
節(jié)點(diǎn)高度：節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長路徑
節(jié)點(diǎn)深度：根節(jié)點(diǎn)到這個節(jié)點(diǎn)所經(jīng)歷的邊的個數(shù)
節(jié)點(diǎn)的層：節(jié)點(diǎn)深度 + 1
樹的高度：根節(jié)點(diǎn)的高度
結(jié)合下面的圖你就能夠理解了，高度是從下到上數(shù)的，深度是從上到下數(shù)的：
2. 二叉樹
樹的形態(tài)多種多樣，但是我們平常最常用的還是二叉樹，顧名思義，二叉樹就是每個節(jié)點(diǎn)最多只有兩個子節(jié)點(diǎn)的樹。
在上圖中的幾種二叉樹中，有兩個是比較特殊的，分別是滿二叉樹和完全二叉樹。
滿二叉樹：樹的葉子節(jié)點(diǎn)全在最底層，并且除了葉子節(jié)點(diǎn)，每個節(jié)點(diǎn)都有左右兩個子節(jié)點(diǎn)，例如上圖中的樹 2。
完全二叉樹：葉子節(jié)點(diǎn)都在最底下兩層，最底層的節(jié)點(diǎn)全都靠左排列，并且除了最后一層，其他層的節(jié)點(diǎn)都必須有左右兩個節(jié)點(diǎn)，例如上圖中的樹 3。
完全二叉樹的概念有點(diǎn)不太好理解，你可以多思考一下，其實(shí)滿二叉樹就是完全二叉樹的一種特殊情況。完全二叉樹的這種特性是為了方便其在數(shù)組中的存儲，不至于浪費(fèi)太多的內(nèi)存空間，等后面說到堆的時候你就更能理解了。
除了使用數(shù)組存儲二叉樹外，最常用的便是使用鏈表法來儲存二叉樹了。下面說到的二叉樹的遍歷便是這種存儲方法。
3. 二叉樹的遍歷
二叉樹的一種常見操作就是需要遍歷得到樹種的全部數(shù)據(jù)，最常用的遍歷方式有三種：前序遍歷、中序遍歷、后序遍歷。
前序遍歷：對于樹中的任意節(jié)點(diǎn)來說，先遍歷這個節(jié)點(diǎn)，然后遍歷這個節(jié)點(diǎn)的左子節(jié)點(diǎn)，最后遍歷這個節(jié)點(diǎn)的右子節(jié)點(diǎn)。（父左右）
中序遍歷：對于樹中的任意節(jié)點(diǎn)來說，先遍歷這個節(jié)點(diǎn)的左子節(jié)點(diǎn)，然后遍歷這個節(jié)點(diǎn)本身，最后遍歷這個節(jié)點(diǎn)的右子節(jié)點(diǎn)。（左父右）
后序遍歷：對于樹中的任意節(jié)點(diǎn)來說，先遍歷這個節(jié)點(diǎn)的左子節(jié)點(diǎn)，然后遍歷這個節(jié)點(diǎn)的右子節(jié)點(diǎn)，最后遍歷這個節(jié)點(diǎn)本身。（左右父）
其實(shí)樹的遍歷是一種很典型的遞歸操作，代碼也可以使用遞歸來實(shí)現(xiàn)，你可以看看我實(shí)現(xiàn)的代碼。
//1.前序遍歷
public void preOrder(Node head){
if (head == null) return;
System.out.print(head.getData() + " ");
preOrder(head.left);
preOrder(head.right);
}
//2.中序遍歷
public void midOrder(Node head){
if (head == null) return;
midOrder(head.left);
System.out.print(head.getData() + " ");
midOrder(head.right);
}
//3.后序遍歷
public void postOrder(Node head){
if (head == null) return;
postOrder(head.left);
postOrder(head.right);
System.out.print(head.getData() + " ");
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/73977.html
摘要：因此，根據(jù)題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數(shù)據(jù)結(jié)構(gòu)與算法描述實(shí)現(xiàn)二叉樹算法淺談數(shù)據(jù)結(jié)構(gòu)二叉樹慕課網(wǎng)實(shí)現(xiàn)二叉樹算法前端樹控件騰訊軟件開發(fā)面試題 內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法 內(nèi)容提要 什么是樹 - 為什么使用樹 二叉樹 二叉查找樹 紅黑樹 Ｂ、Ｂ＋樹 堆 伸展樹 樹 可以點(diǎn)擊鏈接感受下筆者用d3.js畫的tree https://codepen...
摘要：本篇主要介紹二叉樹的概念二叉樹的表示二叉樹的操作三種遍歷方式實(shí)現(xiàn)求二叉樹的子樹求節(jié)點(diǎn)的父節(jié)點(diǎn)二叉樹高度，可能是考試中的，也可能是面試中的。通常二叉樹的遍歷根據(jù)根節(jié)點(diǎn)的遍歷次序分為先根遍歷中根遍歷后根遍歷。 聲明：碼字不易，轉(zhuǎn)載請注明出處，歡迎文章下方討論交流。 前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會不定時更新，歡迎各位讀者監(jiān)督。本篇主要介紹二叉樹的概念、二叉樹的表示、二叉樹的操作（三種遍歷...
摘要：一個節(jié)點(diǎn)可以有多個子節(jié)點(diǎn)二叉樹二叉樹是一種特殊的樹，子節(jié)點(diǎn)數(shù)不超過個。以某種特定的順序訪問樹中所有的節(jié)點(diǎn)稱為樹的遍歷樹的層數(shù)稱為樹的深度一個父節(jié)點(diǎn)的兩個子節(jié)點(diǎn)分別稱為左節(jié)點(diǎn)和右節(jié)點(diǎn)二叉查找樹又稱二叉排序樹是一種特殊的二叉樹。 原文地址：http://www.brandhuang.com/article/1564967352592 1、樹 一棵樹最上面的節(jié)點(diǎn)：根結(jié)點(diǎn) 一個節(jié)點(diǎn)下面連接多個...
摘要：所以，如果中序遍歷二叉搜索樹，會得到一個有序的數(shù)據(jù)，時間復(fù)雜度是，所以二叉搜索樹又叫做二叉排序樹。所以，我們需要一種方式來維持二叉樹的平衡，最好是將其維持為滿二叉樹或者完全二叉樹，這就是后面會說到的平衡二叉查找樹，常見的有樹，紅黑樹。 1. 概述 前面的文章說到了二叉樹，其實(shí)今天講的二叉搜索(查找)樹就是二叉樹最常用的一種形式，它支持高效的查找、插入、刪除操作，它的定義是這樣的：對于樹...
閱讀 2114·2021-11-11 16:55
閱讀 3183·2021-10-11 10:58
閱讀 3061·2021-09-13 10:28
閱讀 3997·2021-07-26 23:57
閱讀 1044·2019-08-30 15:56
閱讀 1341·2019-08-29 13:15
閱讀 1278·2019-08-26 18:18
閱讀 1284·2019-08-26 13:44
