??二叉樹的存儲
二叉樹的存儲結(jié)構(gòu)分為：順序存儲和類似于鏈表的鏈?zhǔn)酱鎯?/mark>
這里博主講一下鏈?zhǔn)酱鎯?/p>
二叉樹的鏈?zhǔn)酱鎯κ峭ㄟ^一個一個的節(jié)點引用起來的，常見的表示方式有二叉和三叉表示方式
二叉表示：
// 孩子表示法
class Node {
int val; // 數(shù)據(jù)域
Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹
Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹
}
三叉表示：
/
/ 孩子雙親表示法
class Node {
int val; // 數(shù)據(jù)域
Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹
Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹
Node parent; // 當(dāng)前節(jié)點的根節(jié)點
}
這里博主主要講解一下孩子表示法
??二叉樹的基本操作
?????二叉樹的創(chuàng)建
在學(xué)習(xí)二叉樹的基本操作前，需先要創(chuàng)建一棵二叉樹，然后才能學(xué)習(xí)其相關(guān)的基本操作。由于現(xiàn)在大家對二叉樹結(jié)構(gòu)掌握還不夠深入，為了降低大家學(xué)習(xí)成本，此處手動快速創(chuàng)建一棵簡單的二叉樹。
創(chuàng)建如下：
public class BinaryTree{
public static class BTNode{
BTNode left;
BTNode right;
int value;
BTNode(int value){
this.value = value;
}
}
private BTNode root;
public void createBinaryTree(){
BTNode node1 = new BTNode(1);
BTNode node2 = new BTNode(2);
BTNode node3 = new BTNode(3);
BTNode node4 = new BTNode(4);
BTNode node5 = new BTNode(5);
BTNode node6 = new BTNode(6);
root = node1;
node1.left = node2;
node2.left = node3;
node1.right = node4;
node4.left = node5;
node5.right = node6;
}
}
注意：上述代碼并不是創(chuàng)建二叉樹的方式，真正創(chuàng)建二叉樹方式后序詳解重點講解
在我們對二叉樹進行基本操作之前，我們的先來回顧以下二叉樹
二叉樹是：
- 空樹
- 非空：根節(jié)點，根節(jié)點的左子樹、根節(jié)點的右子樹組成的
從概念中可以看出，二叉樹的每一個子樹又是一個新的二叉樹，所以可以知道二叉樹定義是遞歸式的，因此后序基本操作中基本都是按照該概念實現(xiàn)的。
?????二叉樹的遍歷
??前中后序遍歷
學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題(比如：打印節(jié)點內(nèi)容、節(jié)點內(nèi)容加1) 。
遍歷是二叉樹上最重要的操作之一，是二叉樹上進行其它運算之基礎(chǔ)
在遍歷二叉樹時，如果沒有進行某種約定，每個人都按照自己的方式遍歷，得出的結(jié)果就比較混亂，如果按照某種規(guī)則進行約定，則每個人對于同一棵樹的遍歷結(jié)果肯定是相同的。如果N代表根節(jié)點，L代表根節(jié)點的
左子樹，R代表根節(jié)點的右子樹，則根據(jù)遍歷根節(jié)點的先后次序有以下遍歷方式：
-
NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點—>根的左子樹—>根的右子樹。
-
LNR：中序遍歷(Inorder Traversal)——根的左子樹—>根節(jié)點—>根的右子樹。
-
LRN：后序遍歷(Postorder Traversal)——根的左子樹—>根的右子樹—>根節(jié)點
??前序遍歷
前序遍歷(Preorder Traversal 亦稱先序遍歷)規(guī)則為
訪問根結(jié)點—>根的左子樹—>根的右子樹
比如以下二叉樹：
前序遍歷的順序為：
1.== 遍歷A結(jié)點==
2. 遍歷A結(jié)點的左子樹
3. 遍歷B結(jié)點
4. 遍歷B結(jié)點的左子樹
5. 遍歷D結(jié)點
6. 判斷D的左右子樹為空后返回
7. 遍歷B結(jié)點的右子樹，為空返回
8. 此時A結(jié)點左子樹遍歷完，開始遍歷A結(jié)點右子樹
9. 遍歷C結(jié)點
10.遍歷C結(jié)點的左子樹
11.遍歷E結(jié)點
12.判斷E結(jié)點的左右子樹為空后返回
13.遍歷C結(jié)點的右子樹
14.遍歷F結(jié)點
15.判斷F結(jié)點的左右子樹為空后返回
16.自此遍歷完畢全部返回
最后前序的遍歷結(jié)果為：
A->B->D->C->E->F
??中序遍歷
中序遍歷(Inorder Traversal)的訪問規(guī)則為：
根的左子樹—>根節(jié)點—>根的右子樹。
比如以下二叉樹：
中序遍歷的順序為：
- 遍歷A結(jié)點的左子樹
- 遍歷B結(jié)點的左子樹
- 遍歷D結(jié)點的左子樹，發(fā)現(xiàn)為空返回
- 遍歷D結(jié)點
- 遍歷D結(jié)點的右子樹，發(fā)現(xiàn)為空返回
- 遍歷B結(jié)點
- 遍歷B結(jié)點的右子樹。發(fā)現(xiàn)為空返回
- 此時左子樹遍歷完成
- 遍歷A結(jié)點
- 遍歷A結(jié)點右子樹
- 遍歷C結(jié)點左子樹
- 遍歷E結(jié)點的左子樹，發(fā)現(xiàn)為空返回
- 遍歷E結(jié)點
- 遍歷E結(jié)點的右子樹，發(fā)現(xiàn)為空返回
- 遍歷C結(jié)點
- 遍歷C結(jié)點的左子樹
- 遍歷F結(jié)點的左子樹，發(fā)現(xiàn)為空返回
- 遍歷F結(jié)點
- 遍歷F結(jié)點的右子樹，發(fā)現(xiàn)為空返回
- 自此遍歷完畢全部返回
最后中序的遍歷結(jié)果為：
D->B->A->E->C->F
??后續(xù)遍歷
后序遍歷(Postorder Traversal)的訪問規(guī)則為：
根的左子樹—>根的右子樹—>根節(jié)點
比如以下二叉樹：
后續(xù)遍歷的順序為：
- 遍歷A結(jié)點的左子樹
- 遍歷B結(jié)點的左子樹
- 遍歷D結(jié)點的左子樹，為空后返回
- 遍歷D結(jié)點的右子樹，為空后返回
- 遍歷D結(jié)點
- 遍歷B結(jié)點的右子樹，為空后返回
- 遍歷B結(jié)點
- 遍歷A結(jié)點的右子樹
- 遍歷C結(jié)點的左子樹
- 遍歷E結(jié)點的左子樹，為空后返回
- 遍歷E結(jié)點的右子樹，為空后返回
- 遍歷E結(jié)點
- 遍歷C結(jié)點的右子樹
- 遍歷F結(jié)點的左子樹，為空后返回
- 遍歷F結(jié)點的右子樹，為空后返回
- 遍歷F結(jié)點
- 遍歷C結(jié)點
- 遍歷A結(jié)點
- 至此遍歷完畢，全部返回
最后后序的遍歷結(jié)果為：
D->B->E->F->C->A
??層序遍歷
層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。
設(shè)二叉樹的根節(jié)點所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先訪問第一層的樹根節(jié)點，然后從左到右訪問第2層上的節(jié)點，接著是第三層的節(jié)點，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點的過程就是層序遍歷。
?????前中后序代碼實現(xiàn)（遞歸）
我們發(fā)現(xiàn)二叉樹本質(zhì)上是一個個小二叉樹組成的
那我們遞歸不就是把大事化小，復(fù)雜變簡單嗎？
因此我們就可以利用遞歸的思想進行實現(xiàn)
我們二叉樹看成最簡單的，也就下面幾種情況
我們從根節(jié)點開始遍歷，遇到空然后返回打印當(dāng)前結(jié)點就好
??前序遍歷
// 前序遍歷 根 左子樹 右子樹 遞歸
public void preOrder(TreeNode root) {
if(root == null) {
return;
}
System.out.print(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}
??中序遍歷
// 中序遍歷
public void inOrder(TreeNode root) {
if(root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
??后續(xù)遍歷
// 后序遍歷
public void postOrder(TreeNode root) {
if(root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+" ");
}
??前中后序練習(xí)題
-
某完全二叉樹按層次輸出（同一層從左到右）的序列為 ABCDEFGH 。該完全二叉樹的前序序列為(A)
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA -
二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK;中序遍歷：HFIEJKG.則二叉樹根結(jié)點為(A)
A: E B: F C: G D: H -
設(shè)一課二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹前序遍歷序列為(D)
A: adbce B: decab C: debac D: abcde -
某二叉樹的后序遍歷序列與中序遍歷序列相同，均為 ABCDEF ，則按層次輸出(同一層從左到右)的序列為(A)
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF
總結(jié)：給出前序遍歷與中序遍歷和給出后序遍歷與中序遍歷可以確定一個二叉樹，但是不給中序遍歷或者只給一個中序遍歷，是無法確定一個二叉樹的
?????二叉樹的基本操作
??獲取樹中節(jié)點的個數(shù)
依舊利用遞歸的思想，遍歷每一棵小樹，若當(dāng)前結(jié)點為空，返回0
先獲取左節(jié)點個數(shù)，再獲取右節(jié)點個數(shù)
然后返回兩者相加再加上根節(jié)點的個數(shù)1
比如以下結(jié)點：
若當(dāng)前結(jié)點不為空，則返回1；
代碼實現(xiàn)如下：
public int size(BTNode root) {
if (root == null) {
return 0;
}
int leftSize = size(root.left);
int rightSize = size(root.right);
return leftSize + rightSize + 1;
}
??獲取葉子節(jié)點的個數(shù)
依舊利用遞歸的思想，遍歷每一棵小樹，若當(dāng)前結(jié)點為空，返回0
當(dāng)前節(jié)點的左右子樹若都為空，說明該節(jié)點為葉子結(jié)點，返回1
先獲取左節(jié)點個數(shù)，再獲取右節(jié)點個數(shù)
然后兩者相加
代碼實現(xiàn)如下：
int getLeafNodeCount(BTNode root) {
if(root == null) {
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
int leftSize = getLeafNodeCount(root.left);
int rightSize = getLeafNodeCount(root.right);
return leftSize+rightSize;
}
??獲取第K層節(jié)點的個數(shù)
依舊利用遞歸的思想，每進去一次，K-1，當(dāng)k=1時，此時若該節(jié)點不為空則返回1
為空則返回0
先遍歷左子樹k層結(jié)點，再遍歷右子樹k層結(jié)點
最后左子樹結(jié)點加上右子樹結(jié)點，就是該層結(jié)點總數(shù)
int getKLevelNodeCount(TreeNode root,int k) {
if(root == null) {
return 0;
}
if(k == 1) {
return 1;
}
int leftSize = getKLevelNodeCount(root.left,k-1);
int rightSize = getKLevelNodeCount(root.right,k-1);
return leftSize+rightSize;
}
?? 獲取二叉樹的高度
分別統(tǒng)計左右子樹的高度，然后進行比較
返回高度高的子樹并加上根節(jié)點
public int maxDepth(BTNode root) {
if(root == null) {
return 0;
}
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return (leftHeight > rightHeight) ?
(leftHeight+1):(rightHeight+1);
}
??檢測值為value的元素是否存在
依舊利用遞歸的思想
先遍歷左子樹，若沒有找到，則返回null
若返回不為null，則返回該結(jié)點
若左子樹沒有，則遍歷右子樹，道理相同
若最后都沒找到，則返回null；文章來源：http://www.zghlxwxcb.cn/news/detail-684611.html
BTNode find(BTNode root, int val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
BTNode leftTree = find(root.left, val);
if (leftTree != null) {
return leftTree;
}
BTNode rightTree = find(root.right, val);
if (rightTree != null) {
return rightTree;
}
return null;//沒有找到
}
?總結(jié)
關(guān)于《【數(shù)據(jù)結(jié)構(gòu)】二叉樹的存儲與基本操作的實現(xiàn)》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評指正，如果文章對您有幫助或者覺得作者寫的還不錯可以點一下關(guān)注，點贊，收藏支持一下！文章來源地址http://www.zghlxwxcb.cn/news/detail-684611.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉數(shù)的存儲與基本操作的實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
