二叉樹

1. 二叉樹簡介

定義： 每一個結(jié)點的子節(jié)點數(shù)量不超過 2

二叉樹的結(jié)點分為：左節(jié)點、右節(jié)點

滿二叉樹： 每個結(jié)點都有兩個子結(jié)點的二叉樹（除了葉子結(jié)點外）

完全二叉樹： 除去最后一層，是一個滿二叉樹，并且最后一層結(jié)點左連續(xù)

(從左到右，從上到下，依次編號1,2,3,4…，這樣的編號和滿二叉樹一一對應(yīng)的二叉樹叫完全二叉樹)

2. 鏈式存儲的二叉樹

2.1 創(chuàng)建二叉樹

思路： 首先必須有一個BinaryTree 二叉樹的類-用于設(shè)置根節(jié)點(也可以是一顆空樹)

? 其次需要結(jié)點 TreeNode 來構(gòu)建二叉樹

? 結(jié)點包含：value結(jié)點值、leftNode左節(jié)點、rightNode右節(jié)點 以及設(shè)置/獲取左右節(jié)點的方法

創(chuàng)建一個如下圖的二叉樹

具體化以后：

代碼：

//二叉樹 public class BinaryTree {//根節(jié)點TreeNode root;//設(shè)置根節(jié)點、獲取根節(jié)點public TreeNode getRoot() {return root;}public void setRoot(TreeNode root) {this.root = root;} } //樹的結(jié)點 public class TreeNode {//結(jié)點的值int value;//左節(jié)點TreeNode leftNode;//右節(jié)點TreeNode rightNode;//初始化值public TreeNode(int value){this.value=value;}//設(shè)置左節(jié)點public void setLeftNode(TreeNode leftNode) {this.leftNode = leftNode;}//設(shè)置右節(jié)點public void setRightNode(TreeNode rightNode) {this.rightNode = rightNode;} }

測試類：

public class TestBinaryTree {public static void main(String[] args) {//創(chuàng)建一顆空二叉樹BinaryTree binaryTree = new BinaryTree();//創(chuàng)建根結(jié)點TreeNode root=new TreeNode(1);binaryTree.setRoot(root);//創(chuàng)建根結(jié)點的左節(jié)點和右節(jié)點TreeNode leftNode = new TreeNode(2);TreeNode RightNode = new TreeNode(3);//將左右結(jié)點連接在根結(jié)點后root.setLeftNode(leftNode);root.setRightNode(RightNode);} }

2.2 遍歷二叉樹

三種遍歷方式： 前序遍歷、中序遍歷、后續(xù)遍歷

(這里的前中后，都是對于當前結(jié)點而言)

前序遍歷-當前結(jié)點在左右結(jié)點的前面：簡記為 “根左右”

中序遍歷-當前結(jié)點在左右結(jié)點的中間-“左根右”

后序遍歷-當前結(jié)點在左右結(jié)點的后面-“左右根”

舉個栗子：

前序遍歷：1 2 4 5 3 6 7

中序遍歷：4 2 5 1 6 3 7

后序遍歷：4 5 2 6 7 3 1

代碼實現(xiàn)：

TreeNode.java 中 (代碼沒有前部寫出，前面已經(jīng)寫過的代碼略)

//前序遍歷public void frontShow(){//遍歷當前節(jié)點System.out.print(value+" ");//遍歷左節(jié)點if(leftNode!=null){leftNode.frontShow();}//遍歷右節(jié)點if(rightNode!=null){rightNode.frontShow();}}//中序遍歷public void midShow(){//遍歷左子節(jié)點if(leftNode!=null){leftNode.midShow();}//遍歷當前節(jié)點System.out.print(value+" ");//遍歷右子節(jié)點if(rightNode!=null){rightNode.midShow();}}//后序遍歷public void afterShow(){//遍歷左子節(jié)點if(leftNode!=null){leftNode.afterShow();}//遍歷右子節(jié)點if(rightNode!=null){rightNode.afterShow();}//遍歷當前節(jié)點System.out.print(value+" ");}

BinaryTree中實現(xiàn)封裝：

//前中后序遍歷public void frontShow(){root.frontShow();}public void midShow(){root.midShow();}public void afterShow(){root.afterShow();}

測試：

public class TestBinaryTree {public static void main(String[] args) {//創(chuàng)建一顆空二叉樹BinaryTree binaryTree = new BinaryTree();//創(chuàng)建根結(jié)點TreeNode root=new TreeNode(1);binaryTree.setRoot(root);//創(chuàng)建根結(jié)點的左節(jié)點和右節(jié)點TreeNode leftNode = new TreeNode(2);TreeNode rightNode = new TreeNode(3);//將左右結(jié)點連接在根結(jié)點后root.setLeftNode(leftNode);root.setRightNode(rightNode);//增加四個節(jié)點 4、5、6、7方便遍歷leftNode.setLeftNode(new TreeNode(4));leftNode.setRightNode(new TreeNode(5));rightNode.setLeftNode(new TreeNode(6));rightNode.setRightNode(new TreeNode(7));//前序、中序、后序遍歷System.out.print("前序遍歷：");binaryTree.frontShow();System.out.print("\n中序遍歷：");binaryTree.midShow();System.out.print("\n后序遍歷：");binaryTree.afterShow();System.out.println();} }

結(jié)果：

前序遍歷：1 2 4 5 3 6 7 中序遍歷：4 2 5 1 6 3 7 后序遍歷：4 5 2 6 7 3 1

可以看到和我們上面分析的結(jié)果一模一樣

2.3 二叉樹結(jié)點的查找

三種查找方式：前序、中序、后序查找
和遍歷差不多，不同的是傳入一個要查找的值，并且返回目標結(jié)點

三種查找實現(xiàn)差不多，只是查找順序不同

代碼：

//前序查找public TreeNode frontSearch(int value){//目標節(jié)點TreeNode target=null;//先查找當前結(jié)點，如果值相同直接返回if(this.value==value){return this;}//查找左子節(jié)點if(leftNode!=null){target = leftNode.frontSearch(value);//如果左子節(jié)點返回的值不為空，則找到，直接返回if(target!=null){return target;}}//查找右子節(jié)點if(rightNode!=null){target = rightNode.frontSearch(value);}//返回return target;}//中序查找public TreeNode midSearch(int value){//目標節(jié)點TreeNode target=null;//先查找左子節(jié)點if(leftNode!=null){target = leftNode.midSearch(value);//如果左子節(jié)點返回的值不為空，則找到，直接返回if(target!=null){return target;}}//再查找當前結(jié)點，如果值相同直接返回if(this.value==value){return this;}//最后查找右子節(jié)點if(rightNode!=null){target = rightNode.midSearch(value);}//返回return target;}//后序查找public TreeNode afterSearch(int value){//目標節(jié)點TreeNode target=null;//先查找左子節(jié)點if(leftNode!=null){target = leftNode.afterSearch(value);//如果左子節(jié)點返回的值不為空，則找到，直接返回if(target!=null){return target;}}//再查找右子節(jié)點if(rightNode!=null){target = rightNode.afterSearch(value);if(target!=null){return target;}}//最后查找當前結(jié)點，如果值相同直接返回if(this.value==value){target=this;}//返回return target;}

BinaryTree中實現(xiàn)封裝：

//前中后序查找public TreeNode frontSearch(int value){return root.frontSearch(value);}public TreeNode midSearch(int value){return root.midSearch(value);}public TreeNode afterSearch(int value){return root.afterSearch(value);}

測試：

//查找 System.out.println(binaryTree.frontSearch(3)==rightNode); System.out.println(binaryTree.midSearch(6)); System.out.println(binaryTree.afterSearch(7));

結(jié)果：

true com.dong.DataStructrue.Day_06.TreeNode@1554909b com.dong.DataStructrue.Day_06.TreeNode@6bf256fa

可以看到，無論用什么查找方式都可以找到樹中有的結(jié)點

2.4 刪除結(jié)點(子樹)

思路： 想刪除一個結(jié)點，可以讓其父節(jié)點指向它的TreeNode為null即可

? 當刪除的不是葉子節(jié)點，相當于刪除子樹

注意： 以下的刪除方法只適用于 結(jié)點值不重復(fù)時

代碼：

BinaryTree

//刪除結(jié)點(子樹)public void delete(int value){if(root!=null){//如果根節(jié)點是要刪除的結(jié)點直接刪除if(root.value==value){root=null;}else{//遞歸root.delete(value);}}else{System.out.println("當前是一顆空樹，無法刪除！");}}

TreeNode：

//刪除結(jié)點(子樹)public void delete(int value) {//存儲父節(jié)點TreeNode parentNode=this;//判斷左子節(jié)點if(parentNode.leftNode!=null&&parentNode.leftNode.value==value){//刪除parentNode.leftNode=null;return;}//判斷右節(jié)點if(parentNode.rightNode!=null&&parentNode.rightNode.value==value){//刪除parentNode.rightNode=null;return;}//將左節(jié)點作為父節(jié)點，遞歸刪除parentNode=leftNode;if(parentNode!=null){parentNode.delete(value);}//將右節(jié)點作為父節(jié)點，遞歸刪除parentNode=rightNode;if(parentNode!=null){parentNode.delete(value);}}

測試：

//刪除結(jié)點 System.out.print("刪除前："); binaryTree.frontShow(); System.out.println(); //這里4、7都是刪除兩個葉子結(jié)點 System.out.print("刪除4："); binaryTree.delete(4); binaryTree.frontShow(); System.out.println();System.out.print("刪除7："); binaryTree.delete(7); binaryTree.frontShow(); System.out.println(); //這里相當于刪除了子樹 System.out.print("刪除2："); binaryTree.delete(2); binaryTree.frontShow();

結(jié)果：

刪除前： 1 2 4 5 3 6 7 刪除4： 1 2 5 3 6 7 刪除7： 1 2 5 3 6 刪除2： 1 3 6

3. 順序存儲的二叉樹

思路：使用數(shù)組來存儲，通過數(shù)組下標關(guān)系來找到左節(jié)點和右節(jié)點以及父節(jié)點，從而實現(xiàn)順序存儲二叉樹

代碼：

public class ArrayBinaryTree {//存儲數(shù)據(jù)int[] data;public ArrayBinaryTree(int[] data) {this.data = data;}//不傳參數(shù)，默認從0開始遍歷public void frontShow(){frontShow(0);}//前序遍歷，傳入?yún)?shù)-從哪個下標開始遍歷public void frontShow(int index){//當數(shù)據(jù)為空時if(data.length==0||data==null){System.out.print("當前為空樹");return;}System.out.print(data[index]+" ");//遍歷左節(jié)點=index*2+1if(index*2+1<data.length){frontShow(index*2+1);}//遍歷右節(jié)點=index*2+2if(index*2+2<data.length){frontShow(index*2+2);}} }

測試：

public class TestArrayBinaryTree {public static void main(String[] args) {//創(chuàng)建數(shù)組，傳入值int[] data=new int[]{1,2,3,4,5,6,7};ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(data);//前序遍歷，從0開始System.out.print("前序遍歷：");arrayBinaryTree.frontShow();} }

結(jié)果：

前序遍歷： 1 2 4 5 3 6 7

總結(jié)

以上是生活随笔為你收集整理的【二叉树详解】二叉树的创建、遍历、查找以及删除等-数据结构05的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。