摘要:實(shí)現(xiàn)基本數(shù)據(jù)結(jié)構(gòu)棧,隊(duì)列,鏈表這篇筆記側(cè)重點(diǎn)二叉樹的三種遍歷前中后迭代非迭代代碼重建二叉樹的代碼與分析和關(guān)于二叉樹的題簡(jiǎn)單理解二叉查找樹紅黑樹,的性質(zhì),實(shí)際用途。同時(shí),以對(duì)應(yīng)的節(jié)點(diǎn)為邊界,就會(huì)把中序遍歷的結(jié)果分為左子樹和右子樹。
雖是讀書筆記,但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/
.. 拒絕伸手復(fù)制黨
以下是算法導(dǎo)論第十章的學(xué)習(xí)筆記 即 劍指offer題目
劍指offer電子書 見(jiàn)我的github https://github.com/GsmToday/JianZhi-offer/tree/master
前面總結(jié)了,棧,隊(duì)列,鏈表。 Java 實(shí)現(xiàn)基本數(shù)據(jù)結(jié)構(gòu) 1(棧,隊(duì)列,鏈表)
這篇筆記側(cè)重點(diǎn):
1 二叉樹的三種遍歷(前中后)迭代非迭代代碼
2 重建二叉樹的代碼與分析 和 關(guān)于二叉樹的題 簡(jiǎn)單理解
3 二叉查找樹, 紅黑樹,Btree的性質(zhì),實(shí)際用途。比如hashmap用到了紅黑樹
二叉樹最重要的操作某過(guò)于遍歷,namely 按照某一順序訪問(wèn)樹中的所有節(jié)點(diǎn)。
通常有四種遍歷方式:
深度優(yōu)先:
- 前序遍歷 (根-左-右)10,6,4,8,14,12,16
用途:1 拷貝樹。 2 計(jì)算前綴表達(dá)式
- 中序遍歷 (左-根-右)4,6,8,10,12,14,16
用途:BST(二叉搜索樹)的中序遍歷以非降序方式輸出節(jié)點(diǎn)。
- 后序遍歷 (右-左-根)4,8,8,12,16,14,10
后序遍歷的用途:1 刪除樹 2 計(jì)算后綴表達(dá)式
2. 廣度優(yōu)先:
- 層序遍歷
二叉樹的遍歷時(shí)間復(fù)雜度,無(wú)論遞歸與否,方式與否,都是O(n). 這是因?yàn)槊總€(gè)算法都要遍歷每個(gè)節(jié)點(diǎn)僅僅一次。
1.2代碼 前序遍歷(遞歸)</>復(fù)制代碼
java public static void preOrderTraverse(Treenode rootnode){
Treenode p = rootnode;
if(p!=null){
System.out.println(p.value);
preOrderTraverse(p.leftchild);
preOrderTraverse(p.rightchild);
}
else return;
}
前序遍歷(非遞歸)
樹的深度優(yōu)先遍歷,因?yàn)闆](méi)有parent指針,所有非遞歸形式一定要借助棧;相反,如果二叉樹的節(jié)點(diǎn)有parent指針,那么就不需要棧了。
先讓根進(jìn)棧。只要棧不為空,就可以彈棧。每次彈出一個(gè)節(jié)點(diǎn),要把它的左右節(jié)點(diǎn)進(jìn)棧(右節(jié)點(diǎn)先進(jìn)棧)。
</>復(fù)制代碼
java public static void preOrderNonrecur(Treenode rootnode){
if(rootnode==null){
return;
}
Treenode p = rootnode;
Stack stack = new Stack();
stack.push(p);
while(stack.isEmpty()!=true){
p = stack.pop();
System.out.println(p.value);
if(p.rightchild != null ){
stack.push(p.rightchild);
}
if(p.leftchild != null){
stack.push(p.leftchild);
}
}
}
中序遍歷(遞歸)
</>復(fù)制代碼
java public static void inOrderTraverse(Treenode rootnode){
Treenode p = rootnode;
if(p!=null){
inOrderTraverse(p.leftchild);
System.out.println(p.value);
inOrderTraverse(p.rightchild);
}
else return;
}
中序遍歷(非遞歸):
current = root;
把current, current的左孩子,current的左孩子的左孩子都入棧,直至current = null -> 跳到step 3
(current = current.left, push(current))
若current = null 且棧沒(méi)空,則彈棧,并訪問(wèn)。current = 彈出的節(jié)點(diǎn)的右孩子 <- 十分重要,之后重復(fù)2。
geeksforgeeks思路參照l(shuí)ink
</>復(fù)制代碼
java public static void inOrderNonrecur(Treenode rootnode){
if(rootnode==null){
return;
}
Treenode current = rootnode;
Stack stack = new Stack();
while(current != null||stack.isEmpty()!=true){
while(current!=null){
stack.push(current);
current = current.leftchild;
}
if(current==null){
Treenode node = stack.pop();
System.out.println(node.value);
current = node.rightchild;
}
}
}
后序遍歷(遞歸)
</>復(fù)制代碼
java public static void postOrderTraverse(Treenode rootnode){
Treenode p = rootnode;
if(p!=null){
postOrderTraverse(p.leftchild);
postOrderTraverse(p.rightchild);
System.out.println(p.value);
}
else return;
}
后序遍歷(非遞歸)
1.1 創(chuàng)建一個(gè)空棧
2.1 當(dāng)current is not null
a) 先右孩子進(jìn)棧,然后current進(jìn)棧
b) 設(shè)置current為左孩子
這樣從根節(jié)點(diǎn),down to 最左孩子節(jié)點(diǎn)。最后current == null
2.2 出棧,設(shè)置出棧的節(jié)點(diǎn)為current
既然出棧了,該節(jié)點(diǎn)肯定沒(méi)有左孩子。
a) 如果出棧節(jié)點(diǎn)存在右孩子
并且 右孩子是棧頂^1(這個(gè)是必要的,原因下面講)
并且 棧不為空 ^2(這個(gè)是必要的,原因下面講),
則 再?gòu)棗#◤棾鲇液⒆樱裞urrent指向的剛剛出棧的節(jié)點(diǎn)(右孩子的爹)入棧。
設(shè)置 current = current.right;
b) 如果出棧節(jié)點(diǎn)不存在右孩子,那么就可以訪問(wèn)之。記得設(shè)置current = null
2.3 重復(fù) 2.1 and 2.2 直到棧空.
^1 請(qǐng)看例子:
如果current指向6,他存在右孩子,但是這個(gè)時(shí)候他的孩子節(jié)點(diǎn)都已經(jīng)訪問(wèn)完畢,沒(méi)必要再把8入棧。所以要判斷。
^2 判斷條件2出現(xiàn)在遍歷根節(jié)點(diǎn)的時(shí)候,因?yàn)樵L問(wèn)一個(gè)節(jié)點(diǎn)的時(shí)機(jī)必是彈棧之后,當(dāng)根節(jié)點(diǎn)彈棧之后,棧已空,所以stack.peek()會(huì)報(bào)錯(cuò)。
geeksforgeeks思路參照l(shuí)ink
</>復(fù)制代碼
java public static void postOrderNonrecur(Treenode rootnode){
if(rootnode==null){
return;
}
Stack stack = new Stack();
Treenode current = rootnode;
while(current !=null || stack.isEmpty()!=true){
//step 1
while(current!=null){
if(current.rightchild!=null){
stack.push(current.rightchild);
}
stack.push(current);
current = current.leftchild;
}
// step2 既然出棧了,該節(jié)點(diǎn)肯定沒(méi)有左孩子。
current = stack.pop();
if(current.rightchild!=null && !stack.isEmpty() && current.rightchild == stack.peek()) {
stack.pop(); //出棧右孩子
stack.push(current);
current = current.rightchild;
}
else{
System.out.println(current.value);
current = null;
}
}
}
層序遍歷(遞歸)
先介紹下如何計(jì)算樹的高度
樹的高度的定義:"height of the root"
節(jié)點(diǎn)高度的定義:"number of edges in longest path from the node to a leaf node". 如:葉子節(jié)點(diǎn)的高度是0.
計(jì)算高度的時(shí)候,利用遞歸,從父節(jié)點(diǎn)到子節(jié)點(diǎn),直至葉子節(jié)點(diǎn),設(shè)置葉子節(jié)點(diǎn)的高度是0。再?gòu)娜~子回到父節(jié)點(diǎn),直至跟根節(jié)點(diǎn),height(parentnode) = max(height(left),height(son))+1
節(jié)點(diǎn)深度的定義:"number of edges in path from root to that node"
</>復(fù)制代碼
java public static int height(Treenode rootnode){
if(rootnode == null){
return -1;
}
int lheight = height(rootnode.leftchild); 計(jì)算該節(jié)點(diǎn)左孩子的高度
int rheight = height(rootnode.rightchild); 計(jì)算該節(jié)點(diǎn)右孩子的高度
return Math.max(lheight, rheight)+1; 返回給該節(jié)點(diǎn)自己的高度
}
貼的是我在leetcode AC 的代碼
</>復(fù)制代碼
javapublic class Solution {
public List> levelOrder(TreeNode rootnode) {
List> resultlist = new ArrayList>();
for(int level = 0; level<= height(rootnode);level++)
{
List list = new ArrayList();
printGivenLevel(rootnode,level,list);
resultlist.add(list);
}
return resultlist;
}
public int height(TreeNode rootnode){
if(rootnode==null){
return -1;
}
else{
return Math.max(height(rootnode.left),height(rootnode.right))+1;
}
}
public void printGivenLevel(TreeNode rootnode, int level, List list){
if(rootnode==null){
return;
}
if(level == 0){
list.add(rootnode.val);
}
else{
printGivenLevel(rootnode.left, level-1, list);
printGivenLevel(rootnode.right, level-1, list);
}
}
}
思路參照
層序遍歷(非遞歸)無(wú)論是樹,還是圖的廣度優(yōu)先遍歷,都要使用先進(jìn)先出的隊(duì)列結(jié)構(gòu)。
步驟:
1. 創(chuàng)建隊(duì)列
2. tempnode = root
3. tempnode 不是 null時(shí)候循環(huán)
a) 輸出tempnode.value
b) 將tempnode的孩子入隊(duì)(先左后右)
c) 出隊(duì),把出隊(duì)的值賦予tempvalue
</>復(fù)制代碼
java public static void LevelOrderNonRecur(Treenode rootnode){
Treenode tempnode = rootnode;
ArrayDeque queue=new ArrayDeque();
if(rootnode==null){
return;
}
queue.add(tempnode);
while(queue.isEmpty()!=true){
tempnode = queue.remove();
System.out.println(tempnode.value);
if(tempnode.leftchild!=null)
queue.add(tempnode.leftchild);
if(tempnode.rightchild!=null)
queue.add(tempnode.rightchild);
}
}
2 二叉樹的題
2.1 線性時(shí)間判斷一個(gè)樹是否是平衡二叉樹:
最直接的方法是遍歷樹的每個(gè)節(jié)點(diǎn)的時(shí)候,調(diào)用函數(shù)的TreeDepth得到他的左右節(jié)點(diǎn)的高度,如果每個(gè)節(jié)點(diǎn)的左右子樹的高度相差不超過(guò) 1. 則它就是一顆平衡二叉樹。
但是在計(jì)算一個(gè)節(jié)點(diǎn)的深度的時(shí)候,就把該節(jié)點(diǎn)和該節(jié)點(diǎn)level以下的所有節(jié)點(diǎn)都遍歷了。 因此,一個(gè)節(jié)點(diǎn)會(huì)被重復(fù)遍歷多次,這種思路的時(shí)間效率不高。所以,效率更高的做法是在計(jì)算高度的時(shí)候,邊計(jì)算邊判斷。
思路參考
</>復(fù)制代碼
java private int getHeight(TreeNode root) {
if (root == null) return 0;
int depL = getHeight(root.left);
int depR = getHeight(root.right);
if (depL < 0 || depR < 0 || Math.abs(depL - depR) > 1) return -1; 返回給該節(jié)點(diǎn)自己的value
else return Math.max(depL, depR) + 1; 返回給該節(jié)點(diǎn)自己的value
}
public boolean isBalanced(TreeNode root) {
return (getHeight(root) >= 0);
}
2.2 輸入兩棵二叉樹A,B,判斷B是不是A的子結(jié)構(gòu)。
</>復(fù)制代碼
java //遍歷Tree1,查找與Tree2 root相同的節(jié)點(diǎn)
boolean HasSubtree(TreeNode root1, TreeNode root2){
boolean result = false;
if(root1 != null && root2 != null){
if(root1.val == root2.val){
//查找到與Tree2 root相同的節(jié)點(diǎn),接著判斷二者是否具有相同結(jié)構(gòu)
result = DoesTree1hasTree2(root1,root2);
}
if(result != true)
result = HasSubtree(root1.left, root2);
if(result != true)
result = HasSubtree(root1.right, root2);
}
return result;
}
</>復(fù)制代碼
java boolean DoesTree1hasTree2(TreeNode root1, TreeNode root2){
boolean lflag = false;
boolean rflag = false;
//Tree2結(jié)束
if(root2==null){
return true;
}
//Tree2有節(jié)點(diǎn)時(shí)候,Tree1還有,說(shuō)明肯定不是包含關(guān)系
if(root1==null){
return false;
}
if(root1.val != root2.val){
return false;
}
else{
lflag = DoesTree1hasTree2(root1.left,root2.left);
rflag = DoesTree1hasTree2(root1.right,root2.right);
return lflag && rflag;
}
}
2.3 輸入某二叉樹的前序遍歷和中序遍歷結(jié)果,請(qǐng)重建二叉樹 ,假設(shè)前序遍歷和中序遍歷中不含重復(fù)數(shù)字。
思路: 前序遍歷的每一個(gè)節(jié)點(diǎn)都是當(dāng)前子樹的根節(jié)點(diǎn)。同時(shí),以對(duì)應(yīng)的節(jié)點(diǎn)為邊界,就會(huì)把中序遍歷的結(jié)果分為左子樹和右子樹。
</>復(fù)制代碼
java public static TreeNode buildTree(int[] preOrder,int start, int[] inOrder,
int end,int length){
// 邊界驗(yàn)證
if (preOrder == null || preOrder.length == 0 || inOrder == null
|| inOrder.length == 0 || length <= 0) {
return null;
}
//根據(jù) 前序遍歷的第一個(gè)元素建立樹根節(jié)點(diǎn)
int value = preOrder[start];
TreeNode root = new TreeNode();
root.val = value;
// 遞歸終止條件:子樹只有一個(gè)節(jié)點(diǎn)
if (length == 1)
return root;
// 根據(jù) 前序遍歷的第一個(gè)元素在中序遍歷中的位置分拆樹的左子樹和右子樹
int i = 0;
while (i < length) {
if (value == inOrder[end - i]) {
break;
}
i++;
}
// 建立子樹的左子樹
root.left = buildTree(preOrder, start + 1, inOrder,
end - i - 1, length - 1 - i);
// 建立子樹的右子樹
root.right = buildTree(preOrder, start + length - i,
inOrder, end, i);
return root;
}
2.3.1 根據(jù)中序+后序遍歷結(jié)果重構(gòu)二叉樹
</>復(fù)制代碼
java public static TreeNode buildTree(int postOrder[], int pend, int inOrder[],int iend, int length){
//boundary test
if(postOrder == null || postOrder.length == 0 || inOrder == null || inOrder.length == 0 || postOrder.length != inOrder.length)
{
System.out.print("te");
return null;
}
//create root;
TreeNode root = new TreeNode();
int value = postOrder[pend];
root.val = value;
if(length ==1)
return root;
// search the index of the root in inorder
int i =0;
while(inOrder[iend-i]!=value){
i++;
}
root.right = buildTree(postOrder, pend-1, inOrder, iend, i);
root.left = buildTree(postOrder, pend-i-1, inOrder, iend-i-1, length-i-1);
return root;
}
2.4 二叉樹中和位某一值的所有路徑
</>復(fù)制代碼
java private static Stack stack=new Stack();
public static void findPathk(TreeNode root,int k,int sum){
boolean isLeaf = false;
// 為了追溯路徑,需要記住棧記錄父節(jié)點(diǎn)
stack.push(root);
// 記錄路徑的sum
sum = root.val + sum;
// 判斷是否路徑到頭
if(root.left == null && root.right==null){
isLeaf = true;
}
// 路徑到頭且和達(dá)到k
if(isLeaf && sum ==k){
System.out.println(stack);
}
// 左子樹
if(root.left != null){
findPathk(root.left,k,sum);
}
// 右子樹
if(root.right != null){
findPathk(root.right,k,sum);
}
// 出棧
stack.pop();
}
想更一進(jìn)步的支持我,請(qǐng)掃描下方的二維碼,你懂的~
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/64291.html
摘要:有網(wǎng)友私信我,期待我的下一篇數(shù)據(jù)結(jié)構(gòu)。前言數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新,歡迎各位讀者監(jiān)督。本文介紹數(shù)據(jù)結(jié)構(gòu)里一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)樹,相應(yīng)的會(huì)補(bǔ)充一些算法。除根節(jié)點(diǎn)外,每個(gè)節(jié)點(diǎn)又可以分為多個(gè)不相交的子樹。 聲明:碼字不易,轉(zhuǎn)載請(qǐng)注明出處,歡迎文章下方討論交流。有網(wǎng)友私信我,期待我的下一篇數(shù)據(jù)結(jié)構(gòu)。非常榮幸文章被認(rèn)可,也非常感謝你們的監(jiān)督。 前言:Java數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新,歡...
摘要:結(jié)構(gòu)型模式適配器模式橋接模式裝飾模式組合模式外觀模式享元模式代理模式。行為型模式模版方法模式命令模式迭代器模式觀察者模式中介者模式備忘錄模式解釋器模式模式狀態(tài)模式策略模式職責(zé)鏈模式責(zé)任鏈模式訪問(wèn)者模式。 主要版本 更新時(shí)間 備注 v1.0 2015-08-01 首次發(fā)布 v1.1 2018-03-12 增加新技術(shù)知識(shí)、完善知識(shí)體系 v2.0 2019-02-19 結(jié)構(gòu)...
摘要:一名年工作經(jīng)驗(yàn)的程序員應(yīng)該具備的技能,這可能是程序員們比較關(guān)心的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)和算法分析數(shù)據(jù)結(jié)構(gòu)和算法分析,對(duì)于一名程序員來(lái)說(shuō),會(huì)比不會(huì)好而且在工作中能派上用場(chǎng)。 一名3年工作經(jīng)驗(yàn)的Java程序員應(yīng)該具備的技能,這可能是Java程序員們比較關(guān)心的內(nèi)容。我這里要說(shuō)明一下,以下列舉的內(nèi)容不是都要會(huì)的東西—-但是如果你掌握得越多,最終能得到的評(píng)價(jià)、拿到的薪水勢(shì)必也越高。 1、基本語(yǔ)法 這包括...
摘要:很多文章或書籍在介紹紅黑樹的時(shí)候直接上來(lái)就是紅黑樹的個(gè)基本性質(zhì)插入刪除操作等。這也不奇怪,算法的作者就是紅黑樹的作者之一。所以,理解樹對(duì)掌握紅黑樹是至關(guān)重要的。 本文主要包括以下內(nèi)容: 什么是2-3樹 2-3樹的插入操作 紅黑樹與2-3樹的等價(jià)關(guān)系 《算法4》和《算法導(dǎo)論》上關(guān)于紅黑樹的差異 紅黑樹的5條基本性質(zhì)的分析 紅黑樹與2-3-4樹的等價(jià)關(guān)系 紅黑樹的插入、刪除操作 JDK ...
摘要:在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)?yīng)樹結(jié)構(gòu)來(lái)說(shuō)二叉樹是最常用的一種樹結(jié)構(gòu),二叉樹具有一個(gè)唯一的根節(jié)點(diǎn),也就是最上面的節(jié)點(diǎn)。二叉樹每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子,一個(gè)孩子都沒(méi)有的節(jié)點(diǎn)通常稱之為葉子節(jié)點(diǎn),二叉樹每個(gè)節(jié)點(diǎn)最多有一個(gè)父親,根節(jié)點(diǎn)是沒(méi)有父親節(jié)點(diǎn)的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...
閱讀 1934·2021-10-11 10:59
閱讀 1042·2021-09-07 09:59
閱讀 2233·2021-08-27 16:17
閱讀 2790·2019-08-30 15:54
閱讀 2281·2019-08-30 12:58
閱讀 1780·2019-08-30 12:53
閱讀 1474·2019-08-28 18:13
閱讀 738·2019-08-26 13:35