欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之二叉樹

 更新時(shí)間:2021年06月21日 15:07:33   作者:文程公子  
今天給大家?guī)淼氖顷P(guān)于Java數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí),文章圍繞著Java二叉樹展開,文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下

一、背景知識(shí):樹(Tree)

在之前的筆記中,我們介紹的鏈表、棧、隊(duì)列、數(shù)組和字符串都是以線性結(jié)構(gòu)來組織數(shù)據(jù)的。本篇筆記要介紹的采用的是樹狀結(jié)構(gòu),這是一種非線性的數(shù)據(jù)組織形式。

樹結(jié)構(gòu)由節(jié)點(diǎn)構(gòu)成,且不存在環(huán)。我們?cè)诰€性表型的數(shù)據(jù)結(jié)構(gòu)中介紹過循環(huán)鏈表和循環(huán)隊(duì)列,這兩種數(shù)據(jù)結(jié)構(gòu)使得存儲(chǔ)容器中的元素形成一個(gè)閉環(huán),具體可參看“數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記”系列的相關(guān)博文,鏈接貼在下面:

鏈表:http://www.dbjr.com.cn/article/215278.htm

隊(duì)列:http://www.dbjr.com.cn/article/211502.htm

樹狀結(jié)構(gòu)與線性結(jié)構(gòu)最重要的區(qū)別在于:樹只能有分叉,不能有閉環(huán)。如下圖所示:

樹結(jié)構(gòu)不允許有環(huán)其實(shí)是樹的層級(jí)性決定的。樹結(jié)構(gòu)中最頂端的結(jié)點(diǎn)是根節(jié)點(diǎn), 根節(jié)點(diǎn)即整棵樹的頂級(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)。也就是說,樹中的數(shù)據(jù)只與其上下層的數(shù)據(jù)有關(guān),同層數(shù)據(jù)間不能有直接聯(lián)系,這也就是樹結(jié)構(gòu)不能有環(huán)的原因。

樹層級(jí)的多少往往被描述為樹的高度(height),由于我們是從上往下觀察樹結(jié)構(gòu)的,因此也被描述為樹的深度(depth)。上面圖示中兩顆樹的深度都是3.

二、何為二叉樹(Binray Tree)

2.1 二叉樹的概念與結(jié)構(gòu)

二叉樹顧名思義,即每個(gè)父節(jié)點(diǎn)最多只有兩個(gè)分叉的樹,這是數(shù)據(jù)結(jié)構(gòu)領(lǐng)域使用頻率極高的一種樹結(jié)構(gòu),這與我們常常用二元對(duì)立的觀點(diǎn)認(rèn)識(shí)世界的思維習(xí)慣有關(guān)。

二叉樹的結(jié)構(gòu)不僅具有層級(jí)性,還具有遞歸性,一個(gè)父節(jié)點(diǎn)連接左子節(jié)點(diǎn)右子節(jié)點(diǎn),而左右子節(jié)點(diǎn)又可以作為父節(jié)點(diǎn)再各自連接兩個(gè)子節(jié)點(diǎn),以此類推。因此二叉樹是一種層次嵌套的數(shù)據(jù)結(jié)構(gòu),除了根節(jié)點(diǎn)外,樹中任意一個(gè)父節(jié)點(diǎn)都能作為一棵子樹,位于上層父節(jié)點(diǎn)左側(cè)的子樹被稱為左子樹,位于右側(cè)的子樹被稱為右子樹。

二叉樹體現(xiàn)了人們用二元思維認(rèn)識(shí)自然的方式。筆者的本行是語(yǔ)言學(xué),語(yǔ)言學(xué)界主流的對(duì)句法結(jié)構(gòu)的分析方法就是類似于二叉樹的二分法。拿漢語(yǔ)的句法結(jié)構(gòu)來說,有主謂、述賓、定中、狀中、述補(bǔ)等基本的結(jié)構(gòu)類型。句法結(jié)構(gòu)具有層次嵌套遞歸的特點(diǎn),同時(shí)也有對(duì)語(yǔ)序的要求,即句法二叉樹中的左右節(jié)點(diǎn)的位置并不是任意的。這種分析方法語(yǔ)言學(xué)上被稱為層次分析法,如果我們用該方法分析句子“文程同學(xué)熱愛編程”,傳統(tǒng)圖示和句法樹圖示分別如下:

2.2 滿二叉樹與完全二叉樹

二叉樹中有兩個(gè)特殊的結(jié)構(gòu)類型:滿二叉樹完全二叉樹。滿二叉樹的結(jié)構(gòu)特點(diǎn)是除了最后一層外,所有層級(jí)的節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn);完全二叉樹的結(jié)構(gòu)特點(diǎn)是除了最后兩層外,所有層級(jí)的節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn),倒數(shù)第二層的子節(jié)點(diǎn)(即最后一層節(jié)點(diǎn))全部靠左排列。如下圖所示:

由此可見,滿二叉樹一定是完全二叉樹,完全二叉樹可滿可不滿。這兩種二叉樹體現(xiàn)了我們采用樹狀結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)時(shí),對(duì)于空間利用率的追求。比如我們?cè)O(shè)計(jì)一個(gè)深度為n的二叉樹,那么整個(gè)二叉樹能容納的最大節(jié)點(diǎn)數(shù)為2^n-1,滿二叉樹就是達(dá)到了最大節(jié)點(diǎn)數(shù),用足了二叉樹的容量。完全二叉樹除了n層沒有子節(jié)點(diǎn),除n-1層外各層父節(jié)點(diǎn)都充分利用了自己擁有子節(jié)點(diǎn)的名額,也算是盡可能做到了對(duì)空間的充分利用。

為了更好地理解完全二叉樹的空間利用率,我們看一個(gè)非完全二叉樹的例子,如下圖所示:

上圖是一個(gè)深度為4的非完全二叉樹,前3層的父節(jié)點(diǎn)都預(yù)留了左右兩個(gè)子節(jié)點(diǎn)的位置,然而第二層的第2個(gè)結(jié)點(diǎn)只使用了右子節(jié)點(diǎn)的空間,浪費(fèi)了左子節(jié)點(diǎn)的空間。如果二叉樹的深度很深,其中很多層級(jí)的父節(jié)點(diǎn)都存在浪費(fèi)子節(jié)點(diǎn)“名額”的現(xiàn)象,那么會(huì)造成相當(dāng)大的空間資源的浪費(fèi),二叉樹也失去了“二叉”的意義。但是完全二叉樹最多浪費(fèi)倒數(shù)第二層父節(jié)點(diǎn)的子節(jié)點(diǎn)名額, 整體上能夠保證較高的空間利用率。

2.3 二叉樹的三種遍歷方式

二叉樹的形狀整體上構(gòu)成一個(gè)三角形,最小的二叉樹由一個(gè)位于中間的父節(jié)點(diǎn)和位于左右兩側(cè)的子節(jié)點(diǎn)構(gòu)成,這導(dǎo)致遍歷訪問一棵二叉樹的所有節(jié)點(diǎn)有三種順序:前序遍歷(Preorder Traversal , VLR)、中序遍歷(Inorder Traversal , LDR)和后序遍歷(Inorder Traversal , LRD)。

無(wú)論哪種遍歷方式,二叉樹都是從上到下、從左到右遍歷的,即從父節(jié)點(diǎn)層到子節(jié)點(diǎn)層、從左子樹到右子樹。2.1解釋了二叉樹的遞歸性,遍歷二叉樹時(shí)采用的也是遞歸(recursion)的方式。對(duì)于整棵樹或某一子樹,都是從根開始,先遍歷其左子樹,再遍歷其右子樹;分別遍歷左右子樹時(shí),同樣是從根開始,從左向右遍歷;以此類推,直到遍歷到最后一個(gè)右子節(jié)點(diǎn)。

如果我們以打印節(jié)點(diǎn)數(shù)據(jù)的方式來表示對(duì)節(jié)點(diǎn)的訪問,那么前序、中序和后序的區(qū)別就在于打印節(jié)點(diǎn)的時(shí)機(jī)不同。前序遍歷的操作順序是打印節(jié)點(diǎn)在遍歷左子樹和遍歷右子樹之前,中序遍歷的操作順序是打印節(jié)點(diǎn)在遍歷左子樹和遍歷右子樹之間,后序遍歷的操作順序是打印節(jié)點(diǎn)在遍歷左子樹和遍歷右子樹之后。子樹遍歷的過程是遞歸實(shí)現(xiàn)的。 

如果我們想遍歷2.1演示的“文程同學(xué)熱愛編程”的句法二叉樹,那么用三種遍歷方法得到的遍歷結(jié)果分別如下:

三、二叉樹及其遍歷的簡(jiǎn)單實(shí)現(xiàn)(Java)

我們用Java語(yǔ)言實(shí)現(xiàn)“文程同學(xué)熱愛編程”這個(gè)句子對(duì)應(yīng)的句法二叉樹,設(shè)計(jì)思路是:將同層級(jí)的父節(jié)點(diǎn)(二叉樹及其各子樹的根節(jié)點(diǎn))存入數(shù)組中,數(shù)組中存入的是結(jié)點(diǎn),包括數(shù)據(jù)左右指針,左右指針分別指向位于下一層節(jié)點(diǎn)的左右子節(jié)點(diǎn),如果沒有子節(jié)點(diǎn)則指針為空指針。

用數(shù)組的好處是,可以通過節(jié)點(diǎn)所在的索引建立上下層級(jí)父節(jié)點(diǎn)和子節(jié)點(diǎn)的指針聯(lián)系。假設(shè)父節(jié)點(diǎn)在它所在的層級(jí)數(shù)組中的索引為i,那么左子節(jié)點(diǎn)在它所在層級(jí)數(shù)組中的索引為(i+1)*2-2,右子節(jié)點(diǎn)的索引為(i+1)*2-1,即左子節(jié)點(diǎn)的索引+1。

遍歷默認(rèn)從整棵二叉樹的根節(jié)點(diǎn)開始,通過方法的重寫實(shí)現(xiàn)默認(rèn)參數(shù)的效果。

準(zhǔn)備工作1:MyBinaryTree.java,創(chuàng)建一個(gè)二叉樹的類

package com.notes.data_structure6;
 
import com.notes.data_structure6.NumberOfNodesException;
 
public class MyBinaryTree {
	// 樹的根結(jié)點(diǎn)
	private Node[] root;
	// 樹的深度(當(dāng)前層級(jí)數(shù))
	private int depth;
	// 將每一層所有的 結(jié)點(diǎn) 都存儲(chǔ)在數(shù)組中,結(jié)點(diǎn)數(shù)是 2的 層數(shù) 次冪
	private Node[] currentLevel;
	
	
	public MyBinaryTree(String data) {
		Node[] rootArray = new Node[] {new Node(data)};
		this.root = rootArray;
		this.currentLevel = rootArray;
	}
 
	// 定義一個(gè)結(jié)點(diǎn)類
	private class Node{
		private String data; // 數(shù)據(jù)
		private Node leftNext; // 左指針
		private Node rightNext; // 右指針
		
		// 構(gòu)造方法:Node實(shí)例化時(shí)傳入數(shù)據(jù)
		public Node(String data) {
			this.data = data;
		}	
	}
	
	// 向樹中增加一層結(jié)點(diǎn)
	public void add(String[] datas) throws NumberOfNodesException {
		// 層級(jí)數(shù)增加1
		depth++;
		// 新增 層級(jí) 的最大結(jié)點(diǎn)數(shù)
		int nodeNum = numberOfNextNodes();
		// 如果傳入的 數(shù)據(jù)數(shù) 與 當(dāng)前層級(jí) 最大結(jié)點(diǎn)數(shù) 不符,拋出異常
		if(datas.length != nodeNum) {
			throw new NumberOfNodesException("第"+depth+"層最大父節(jié)點(diǎn)數(shù)為"+nodeNum);
		}
		// 將傳入的 數(shù)據(jù)數(shù)組 轉(zhuǎn)換為 結(jié)點(diǎn)數(shù)組
		Node[] newLevel = new Node[nodeNum];
		// 當(dāng)前 層級(jí)的 結(jié)點(diǎn)數(shù)量(新增層級(jí)的父)
		int nodeNum2 = (int) Math.pow(2, depth-1);
		// 讓每一個(gè)結(jié)點(diǎn)都與上層 父結(jié)點(diǎn) 建立連接
		for(int i=0;i<nodeNum2;i++) {
			// 讓父結(jié)點(diǎn) 的左指針 指向 左子結(jié)點(diǎn)
			int leftIndex = (i+1)*2-2; // 計(jì)算左子結(jié)點(diǎn)對(duì)應(yīng)的新層級(jí)數(shù)組的索引
			currentLevel[i].leftNext = new Node(datas[leftIndex]); // 建立指針指向
			newLevel[leftIndex] = currentLevel[i].leftNext; // 將結(jié)點(diǎn)加入新層級(jí)結(jié)點(diǎn)數(shù)組
			// 讓父結(jié)點(diǎn) 的右指針 指向 右子結(jié)點(diǎn)
			int rightIndex = leftIndex+1; // 計(jì)算右子結(jié)點(diǎn)對(duì)應(yīng)的新層級(jí)數(shù)組的索引
			currentLevel[i].rightNext = new Node(datas[rightIndex]); // 建立指針指向
			newLevel[rightIndex] = currentLevel[i].rightNext; // 將結(jié)點(diǎn)加入新層級(jí)結(jié)點(diǎn)數(shù)組
		}
		// 讓新增層級(jí)的數(shù)組成為當(dāng)前層級(jí)的數(shù)組
		currentLevel =  newLevel;
	}
	
	// 前序遍歷所有結(jié)點(diǎn)
	public void preTraversal(Node node) {
		if(node==null) {
			return;
		}
		System.out.print(node.data+" ");
		preTraversal(node.leftNext);
		preTraversal(node.rightNext);
	}
	
	// 重寫 前序遍歷 方法,讓遍歷從 根結(jié)點(diǎn) 開始
	public void preTraversal() {
		Node node = root[0];
		if(node==null) {
			return;
		}
		// 遞歸時(shí)調(diào)用帶參數(shù)的方法
		System.out.print(node.data+" ");
		preTraversal(node.leftNext);
		preTraversal(node.rightNext);
	}
	
	// 中序遍歷所有結(jié)點(diǎn)
	public void midTraversal(Node node) {
		if(node==null) {
			return;
		}
		midTraversal(node.leftNext);
		System.out.print(node.data+" ");
		midTraversal(node.rightNext);
	}
	
	// 重寫中序遍歷 方法,讓遍歷從 根結(jié)點(diǎn) 開始
	public void midTraversal() {
		Node node = root[0];
		if(node==null) {
			return;
		}
		// 遞歸時(shí)調(diào)用帶參數(shù)的方法
		midTraversal(node.leftNext);
		System.out.print(node.data+" ");
		midTraversal(node.rightNext);
	}
	
	// 后序遍歷所有結(jié)點(diǎn)
	public void posTraversal(Node node) {
		if(node==null) {
			return;
		}
		posTraversal(node.leftNext);
		posTraversal(node.rightNext);
		System.out.print(node.data+" ");
	}
	
	// 重寫后序遍歷 方法,讓遍歷從 根結(jié)點(diǎn) 開始
	public void posTraversal() {
		Node node = root[0];
		if(node==null) {
			return;
		}
		// 遞歸時(shí)調(diào)用帶參數(shù)的方法
		posTraversal(node.leftNext);
		posTraversal(node.rightNext);
		System.out.print(node.data+" ");
	}
	
	// 查看 新增層級(jí) 的最大結(jié)點(diǎn)數(shù)
	public int numberOfNextNodes() {
		return (int) Math.pow(2,depth);
	}
	
	// 查看 樹 的深度(層級(jí)數(shù))
	public int getDepth() {
		return depth;
	}
	
	
}

準(zhǔn)備工作2:NumberOfNodesException.java,為add()方法創(chuàng)建一個(gè)自定義異常,如果傳入的數(shù)據(jù)數(shù)與當(dāng)前層級(jí)最大結(jié)點(diǎn)數(shù)不符,則拋出該異常(如果二叉樹不滿,在數(shù)組的相應(yīng)位置傳入null)。

package com.notes.data_structure6;
 
public class NumberOfNodesException extends Exception{
	public NumberOfNodesException(String message) {
		super(message);
	}
}

句法二叉樹的實(shí)現(xiàn)及其遍歷:TreeDemo.java

package com.notes.data_structure6;
 
public class TreeDemo {
	public static void main(String[] args) throws NumberOfNodesException {
		// 實(shí)例化二叉樹類,并且傳入根節(jié)點(diǎn)的數(shù)據(jù)
		MyBinaryTree tree = new MyBinaryTree("句子");
		// 加入第一層節(jié)點(diǎn)的數(shù)據(jù)
		tree.add(new String[] {"主語(yǔ)","謂語(yǔ)"});
		// 加入第二層節(jié)點(diǎn)的數(shù)據(jù)
		tree.add(new String[] {"定語(yǔ)","中心語(yǔ)","述語(yǔ)","賓語(yǔ)"});
		
		// 前序遍歷
		tree.preTraversal(); // 句子 主語(yǔ) 定語(yǔ) 中心語(yǔ) 謂語(yǔ) 述語(yǔ) 賓語(yǔ) 
		System.out.println();
		// 中序遍歷
		tree.midTraversal(); // 定語(yǔ) 主語(yǔ) 中心語(yǔ) 句子 述語(yǔ) 謂語(yǔ) 賓語(yǔ) 
		System.out.println();
		// 后序遍歷
		tree.posTraversal(); // 定語(yǔ) 中心語(yǔ) 主語(yǔ) 述語(yǔ) 賓語(yǔ) 謂語(yǔ) 句子 
	}
}

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之二叉樹的文章就介紹到這了,更多相關(guān)Java二叉樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 將java普通項(xiàng)目打包成exe可執(zhí)行文件的步驟記錄

    將java普通項(xiàng)目打包成exe可執(zhí)行文件的步驟記錄

    將JAVA代碼打包為exe文件,會(huì)讓程序運(yùn)行更加方便,這篇文章主要給大家介紹了關(guān)于將java普通項(xiàng)目打包成exe可執(zhí)行文件的相關(guān)資料,需要的朋友可以參考下
    2021-07-07
  • Java超詳細(xì)梳理IO流的使用方法上

    Java超詳細(xì)梳理IO流的使用方法上

    流(Stream)是指一連串的數(shù)據(jù)(字符或字節(jié)),是以先進(jìn)先出的方式發(fā)送信息的通道,數(shù)據(jù)源發(fā)送的數(shù)據(jù)經(jīng)過這個(gè)通道到達(dá)目的地,按流向區(qū)分為輸入流和輸出流
    2022-04-04
  • spring boot啟動(dòng)時(shí)mybatis報(bào)循環(huán)依賴的錯(cuò)誤(推薦)

    spring boot啟動(dòng)時(shí)mybatis報(bào)循環(huán)依賴的錯(cuò)誤(推薦)

    今天小編抽時(shí)間給大家分享spring boot啟動(dòng)時(shí)mybatis報(bào)循環(huán)依賴的錯(cuò)誤,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友參考下吧
    2017-12-12
  • SpringBoot整合Zookeeper詳細(xì)教程

    SpringBoot整合Zookeeper詳細(xì)教程

    Curator是Netflix公司開源的?套zookeeper客戶端框架,Curator是對(duì)Zookeeper?持最好的客戶端框架。Curator封裝了?部分Zookeeper的功能,?如Leader選舉、分布式鎖等,減少了技術(shù)?員在使?Zookeeper時(shí)的底層細(xì)節(jié)開發(fā)?作
    2022-12-12
  • 使用SpringBoot發(fā)送郵件的方法詳解

    使用SpringBoot發(fā)送郵件的方法詳解

    這篇文章主要介紹了使用SpringBoot發(fā)送郵件的方法詳解,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2023-05-05
  • Springboot mybais配置多數(shù)據(jù)源過程解析

    Springboot mybais配置多數(shù)據(jù)源過程解析

    這篇文章主要介紹了Springboot+mybais配置多數(shù)據(jù)源過程解析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-03-03
  • Java日常練習(xí)題,每天進(jìn)步一點(diǎn)點(diǎn)(61)

    Java日常練習(xí)題,每天進(jìn)步一點(diǎn)點(diǎn)(61)

    下面小編就為大家?guī)硪黄狫ava基礎(chǔ)的幾道練習(xí)題(分享)。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧,希望可以幫到你
    2021-08-08
  • IDEA 集成 Docker 插件一鍵部署 SpringBoot 應(yīng)用小結(jié)

    IDEA 集成 Docker 插件一鍵部署 SpringBoot 應(yīng)用

    通過本文介紹的方法,我們期望能幫助開發(fā)者更輕松地在IDEA中實(shí)現(xiàn)Spring Boot應(yīng)用的Docker化部署,為現(xiàn)代軟件開發(fā)提供更便捷的解決方案,感興趣的朋友一起看看吧
    2023-11-11
  • MyBatis-Plus插件機(jī)制及通用Service新功能

    MyBatis-Plus插件機(jī)制及通用Service新功能

    這篇文章主要介紹了MyBatis-Plus插件機(jī)制以及通用Service、新功能,本文通過實(shí)例圖文相結(jié)合給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2022-07-07
  • SpringBoot無(wú)法解析parameter參數(shù)問題的解決方法

    SpringBoot無(wú)法解析parameter參數(shù)問題的解決方法

    使用最新版的 Springboot 3.2.1(我使用3.2.0)搭建開發(fā)環(huán)境進(jìn)行開發(fā),調(diào)用接口時(shí)出現(xiàn)奇怪的錯(cuò),本文小編給大家介紹了SpringBoot無(wú)法解析parameter參數(shù)問題的原因及解決方法,需要的朋友可以參考下
    2024-04-04

最新評(píng)論