数据结构：二叉树
文章目錄
- 樹
- 前言
- 1.樹概念及結構
- 1.1樹的概念
- 1.2樹的實現
- 2.二叉樹
- 2.1概念
- 2.2二叉樹的存儲結構
- 2.3特殊的二叉樹
- 2.4二叉樹的存儲結構
- 2.4.1順序存儲
- 2.4.2鏈式存儲
- 3.二叉樹順序結構及實現
- 3.2二叉樹的順序結構
- 3.1代碼實現
- 4.二叉樹鏈式結構及實現
- 4.1二叉樹鏈式結構的遍歷
- 4.2代碼實現
樹
前言
為什么需要樹這種數據結構？
-
1、數組存儲方式分析
- 優點：通過下表方式訪問元素，速度快，對于有序數組，還可以使用二分、插入以及斐波那契查找算法來提高檢索效率。
- 缺點：如果要檢索具體的某個值，或者進行插入刪除操作，整個數組中的數據都需要移動索引，性能開銷極大并且效率極低。其次由于數組的特點，在創建時數組大小已經固定，數組需進行擴容時極其不方便。
-
2、鏈表存儲方式分析
- 優點：在一定程度上對數組存儲方式進行了優化，當插入數據時，只需要將節點之間指針稍作調整并將數據插入指定位置即可，刪除數據同理，對節點之間指針進行調整即可。
- 缺點：進行檢索時，效率仍然較低，需要從頭結點進行遍歷。
-
3、樹存儲方式的分析
- 能提高數據存儲與讀取的效率，比如利用二叉排序樹(Binary Sort Tree)既可以保證數據檢索速度，同時也可以保證數據的插入、刪除已經修改的速度。
1.樹概念及結構
1.1樹的概念
不同于鏈表、棧以及隊列都是線性的數據結構，數據存儲較為簡單，元素只存在一個對一個的關系，樹是一種更為復雜的數據結構，元素存在一對多的關系，一個父節點可以包含多個子節點。它是一個由n(n>=0)個有限節點組成的有層次關系的集合。
樹可以由幾種方式定義，定義樹的一種自然的方式就是遞歸的方式。
- 根節點(root)
- 除了根節點之外，其余節點被分為一棵結構與樹相類似的子樹。
- 一個節點含有的子樹的根節點稱為該節點的子節點
- 一個節點含有子節點，則將該節點稱之為子節點的父節點
- 節點的度：一個節點含有的子樹的個數稱為該節點的度
- 沒有子節點即度為0的節點稱之為葉子節點，也成為樹葉(leaf)
- 路徑：從根節點到某個節點的路線
- 節點的層次：從根開始定義，根為第一層，根的節點為第二層，以此類推
- 樹的高度或深度：樹中節點的最大層次
- 森林：由m棵互不相交的樹的集合稱為森林，即多棵子樹構成森林
1.2樹的實現
實現樹的一種方法可以是在每一個節點除數據以外還要有一條鏈，使得該節點的每一個子節點都有一個鏈指向它。然而由于每一個節點的子節點個數可以變化很大并且事先不知道，因此在數據結構中建立到各子節點直接的鏈接是不可行的，這樣會產生太多浪費的空間。實際上解決方法很簡單：將每一個節點的所有子節點都放在樹節點的鏈表中。
class TreeNode {Object element;TreeNode firstChild;TreeNode nextSibling; }如上圖所示，向下的箭頭指向的firstChild的鏈，而水平箭頭指向的是nextSibling的鏈，null鏈過多所以沒有畫出。
2.二叉樹
2.1概念
二叉樹(Binary Tree)是一顆樹，其中每個節點都不能超過兩個子節點。
二叉樹的一個性質是一顆平均二叉樹的深度要比節點個數N小得多，分析表明，其深度為O(N1/2)，而對于特殊類型的二叉樹，即二叉查找樹(Binary Search Tree)，其深度的平均值為O(log N)，但最差的情況如下圖所示，深度可以達到N-1。
2.2二叉樹的存儲結構
二叉樹常使用兩種存儲結構，一種為順序結構，一種為鏈式結構
2.3特殊的二叉樹
- 滿二叉樹：一個二叉樹，如果所有葉子節點都在最后一層，并且節點總數為2n - 1，n為層數，則稱該二叉樹為滿二叉樹
- 完全二叉樹：一個二叉樹深度為h，除了第h層外，其他各層的節點數都達到最大個數，第h層有葉子節點，并且葉子節點都是從左到右依次排布
2.4二叉樹的存儲結構
2.4.1順序存儲
順序結構存儲就是用數組來存儲，從數據存儲來看，數組存儲方式和樹的存儲方式可以相互轉換，一般使用數組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。
順序存儲二叉樹特點
- 通常只考慮完全二叉樹
- 第n個元素的左子節點為2*n+1
- 第n個元素的右子節點為2*n+2
- 第n個元素的父節點為(n-1)/2
- 對于具有n個節點的完全二叉樹，如果按照從左至右的數組順序對所有節點從0開始編號，則對序號為index的節點有：
- 如果index>0，index位置的節點雙親序號為(index-1)/2，若index=0，則說明為根節點，無雙親節點
- 若2index+1<n，則說明是序號為index的節點有左子節點，并且該子節點序號為2index+1；否則該序號為index的節點無子節點
- 若2index+2<n，則說明是序號為index的節點有右子節點，并且該子節點序號為2*index+2；否則該序號為index的節點無子節點
2.4.2鏈式存儲
二叉樹的鏈式存儲結構指用鏈表來表示一顆二叉樹，即用鏈來指示元素的邏輯關系，通常的方式是鏈表的每個節點由三個域表示，數據域和左右指針域，左右指針分別用來指向左右子節點的存儲地址。鏈式結構又分為二叉鏈和三叉鏈，當前初學階段是使用二叉鏈，在后面高級數據結構如紅黑樹中會使用到三叉鏈。
二叉鏈圖示：
三叉鏈圖示：
//二叉鏈 class BinaryTreeNode {BinaryTreeNode left;BinaryTreeNode right;Object element; } //三叉鏈 class BinaryTreeNode {BinaryTreeNode parent;BinaryTreeNode left;BinaryTreeNode right;Object element; }3.二叉樹順序結構及實現
3.2二叉樹的順序結構
普通的二叉樹是不適合用數組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結構存儲。現實中我們通常把堆(一種二叉樹)使用順序結構的數組來存儲，需要注意的是這里的堆和操作系統虛擬進程地址空間中的堆是兩回事，一個是數據結構，一個是操作系統中管理內存的一塊區域分段。
完全二叉樹圖示：不會存在大量的空間浪費現象
非完全二叉樹圖示：存在大量的空間浪費現象
3.1代碼實現
/*** 編寫一個ArrayBinaryTree實現順序存儲二叉樹*/ class ArrayBinaryTree {/*** 存儲數據節點的數組*/private int[] arr;public ArrayBinaryTree(int[] arr){this.arr = arr;}public void preOrder(){this.preOrder(0);System.out.println();}public void infixOrder(){this.infixOrder(0);System.out.println();}public void postOrder(){this.postOrder(0);System.out.println();}public boolean isEmpty(){return arr[0] == null;}/*** 前序遍歷* @param index*/public void preOrder(int index){//如果數組為空或者array.length = 0if (arr == null || arr.length == 0){System.out.println("數組為空....");}//數組當前節點數據System.out.println(arr[index]);//向左遞歸遍歷if ((2 * index + 1) < arr.length){preOrder(2 * index + 1);}//向右遞歸遍歷if ((2 * index + 2) < arr.length){preOrder(2 * index + 2);}}/*** 中序遍歷* @param index*/public void infixOrder(int index){//如果數組為空或者array.length = 0if (arr == null || arr.length == 0){System.out.println("數組為空....");}if ((2 * index + 1) < arr.length){infixOrder(2 * index + 1);}//數組當前節點數據System.out.println(arr[index]);if ((2 * index + 2) < arr.length){infixOrder(2 * index + 2);}}/*** 后序遍歷* @param index*/public void postOrder(int index){//如果數組為空或者array.length = 0if (arr == null || arr.length == 0){System.out.println("數組為空....");}if ((2 * index + 1) < arr.length){postOrder(2 * index + 1);}if ((2 * index + 2) < arr.length){postOrder(2 * index + 2);}//數組當前節點數據System.out.println(arr[index]);} }4.二叉樹鏈式結構及實現
4.1二叉樹鏈式結構的遍歷
二叉樹的遍歷(Traversal)就是指沿著某條搜索路線，依次對樹中的節點做一次訪問。訪問時做的操作依賴于實際問題。遍歷時二叉樹中最重要的操作之一，也是對二叉樹進行其他操作的基礎。
遞歸遍歷主要有三種方式：前序/中序/后序遍歷
- 前序遍歷(Preorder Traversal)：訪問根節點的操作發生在遍歷其左右節點之前
- 中序遍歷(Inorder Traversal)：訪問根節點的操作發生在遍歷其左右節點中間
- 后序遍歷(Postorder Traversal)：訪問根節點的操作發生在遍歷其左右節點之后
4.2代碼實現
存儲數據的節點
class Node {private int num;private Object data;private Node left;private Node right;public Node(int num, Object data){this.num = num;this.data = data;}/*** 前序遍歷*/public void preOrder(){//先輸出父節點信息System.out.println(this);//判斷此節點的左節點是否為空if (this.left != null){//向左前序遍歷this.left.preOrder();}//判斷此節點的右節點是否為空if (this.right != null){//向右前序遍歷this.right.preOrder();}}/*** 中序遍歷*/public void infixOrder(){//判斷此節點的左節點是否為空if (this.left != null){//向左中序遍歷this.left.infixOrder();}//輸出父節點信息System.out.println(this);//判斷此節點的右節點是否為空if (this.right != null){//向右中序遍歷this.right.infixOrder();}}/*** 后序遍歷*/public void postOrder(){//判斷此節點的左節點是否為空if (this.left != null){//向左后序遍歷this.left.postOrder();}//判斷此節點的右節點是否為空if (this.right != null){//向右后序遍歷this.right.postOrder();}//輸出父節點信息System.out.println(this);}/*** 前序遍歷查找節點* @param num 待查找節點的編號* @return 如果找到返回該節點 否則返回null*/public Node preOrderSearch(int num){System.out.println("進行前序遍歷查找");//判斷當前節點是否匹配if (this.num == num){return this;}Node result = null;//判斷當前節點的左子節點是否為空if (this.left != null){//向左前序查找result = this.left.preOrderSearch(num);}//如果不為空說明已經找到直接返回該節點并回溯if (result != null){return result;}//判斷當前節點的右子節點是否為空if (this.right != null){//向右前序查找result = this.right.preOrderSearch(num);}return result;}/*** 中序遍歷查找節點* @param num 待查找節點的編號* @return 如果找到返回該節點 否則返回null*/public Node infixOrderSearch(int num){Node result = null;//判斷當前節點的左子節點是否為空if (this.left != null){//向左中序查找result = this.left.infixOrderSearch(num);}//如果不為空說明已經找到直接返回該節點并回溯if (result != null){return result;}System.out.println("進入中序遍歷查找");//判斷當前節點是否匹配if (this.num == num){return this;}//判斷當前節點的右子節點是否為空if (this.right != null){//向右中序查找result = this.right.infixOrderSearch(num);}return result;}/*** 后序遍歷查找節點* @param num 待查找節點的編號* @return 如果找到返回該節點 否則返回null*/public Node postOrderSearch(int num){Node result = null;//判斷當前節點的右子節點是否為空if (this.left != null){//向左后序查找result = this.left.postOrderSearch(num);}//如果不為空說明已經找到直接返回該節點并回溯if (result != null){return result;}//判斷當前節點的右子節點是否為空if (this.right != null){//向右后序查找result = this.right.postOrderSearch(num);}//如果不為空說明已經找到直接返回該節點并回溯if (result != null){return result;}System.out.println("進入后序遍歷查找");//判斷當前節點是否匹配if (this.num == num){return this;}return null;}/*** 遞歸刪除節點* 1.如果刪除的節點是葉子節點則刪除該節點* 2.如果刪除的節點是非葉子節點則刪除該書* @param num*/public void deleteNode(int num){//1.因為該二叉樹是單向的所以先判斷當前節點的子節點是否需要刪除節點而不能判斷當前這個節點是否需要刪除//2.如果當前節點的子左節點不為空,而且左子節點就是需要刪除的節點,就將this.left=null,并且返回,結束遞歸if (this.left != null && this.left.num == num){this.left = null;return;}//3.如果當前節點的子右節點不為空,而且右子節點就是需要刪除的節點,就將this.right=null,并且返回,結束遞歸if (this.right != null && this.right.num == num){this.right = null;return;}//4.如果仍然沒有刪除節點就需要向左子樹進行遞歸刪除if (this.left != null){this.left.deleteNode(num);}//5.如果仍然沒有刪除節點就需要向右子樹進行遞歸刪除if (this.right != null){this.right.deleteNode(num);}}//get set方法省略@Overridepublic String toString(){return "Node{" +"num=" + num +", data=" + data +'}';} }二叉樹
class BinaryTree {/*** 根節點*/private Node root;public void setRoot(Node root){this.root = root;}public void createBinaryTree(ArrayList<Node> list){this.createBinaryTree(list,0);}/*** 創建二叉樹* @param list 節點列表* @param index 用于創建的索引* @return*/private Node createBinaryTree(ArrayList<Node> list,int index){Node node = null;if (isEmpty()){setRoot(list.get(0));}if (index < list.size()){node = list.get(index);node.setLeft(createBinaryTree(list, (2*index+1)));node.setRight(createBinaryTree(list, (2*index+2)));}return node;}/*** 判斷二叉樹是否為空* @return */public boolean isEmpty(){return root == null;}/**** @return 返回二叉樹中的節點個數*/public int getBinaryTreeSize(){return this.getBinaryTreeSize(root);}private int getBinaryTreeSize(Node root){if (root == null){return 0;}return getBinaryTreeSize(root.getLeft()) + getBinaryTreeSize(root.getRight()) + 1;}/*** 葉子節點:無子節點的節點稱之為葉子節點* @return 返回二叉樹中的葉子節點個數*/public int getBinaryTreeLeafSize(){return this.getBinaryTreeLeafSize(root);}private int getBinaryTreeLeafSize(Node root){if (root == null){return 0;}if (root.getLeft() == null && root.getRight() == null){return 1;}return getBinaryTreeSize(root.getLeft()) + getBinaryTreeLeafSize(root.getRight());}/**** @param deep 深度* @return 返回第deep層節點個數*/public int getBinaryTreeDeepSize(int deep){return this.getBinaryTreeDeepSize(root,deep);}private int getBinaryTreeDeepSize(Node root,int deep){if (root == null){return 0;}/*** Deep等于1的情況* 1.第一次傳進來的值就是1時,第一層只有根節點root,故返回1* 2.當遍歷到指定層數時,deep等于1*/if (deep == 1){return 1;}return getBinaryTreeDeepSize(root.getLeft(),deep-1) + getBinaryTreeDeepSize(root.getRight(),deep-1);}/*** 前序遍歷*/public void preOrder(){if (root != null){root.preOrder();}else{System.out.println("二叉樹為空,無法遍歷");}}/*** 中序遍歷*/public void infixOrder(){if (root != null){root.infixOrder();}else{System.out.println("二叉樹為空,無法遍歷");}}/*** 后序遍歷*/public void postOrder(){if (root != null){root.postOrder();}else{System.out.println("二叉樹為空,無法遍歷");}}/*** 前序遍歷查找num匹配的節點* @param num * @return 找到返回該節點 否則返回null*/public Node preOrderSearch(int num){if (root != null){return root.preOrderSearch(num);}return null;}/*** 中序遍歷查找num匹配的節點* @param num* @return 找到返回該節點 否則返回null*/public Node infixOrderSearch(int num){if (root != null){return root.infixOrderSearch(num);}return null;}/*** 后序遍歷查找num匹配的節點* @param num* @return 找到返回該節點 否則返回null*/public Node postOrderSearch(int num){if (root != null){return root.postOrderSearch(num);}return null;}/*** 刪除節點* @param num 待刪除節點編號*/public void deleteNode(int num){if (root != null){if (root.getNum() == num){root = null;}else{root.deleteNode(num);}}else{System.out.println("該樹為空無法刪除數據....");}} }以上。
如有不足或錯誤歡迎評論指正，整理不易，留個三連吧！
總結
- 上一篇： Java实现HashTable的基本操作
- 下一篇： Java实现前中后序线索化二叉树以及遍历