<藍橋杯軟件賽>零基礎備賽20周--第7周--棧和二叉樹

報名明年4月藍橋杯軟件賽的同學們,如果你是大一零基礎,目前懵懂中,不知該怎么辦,可以看看本博客系列:備賽20周合集
20周的完整安排請點擊:20周計劃
每周發1個博客,共20周(讀者可以按自己的進度選“正常”和“快進”兩種計劃)。
每周3次集中答疑
,周三、周五、周日晚上,在QQ群上答疑:

在這里插入圖片描述

文章目錄

  • 1. 基本數據結構概述
    • 1.1 數據結構和算法的關系
    • 1.2 線性數據結構概述
    • 1.3 二叉樹簡介
  • 2. 棧
    • 2.1 手寫棧
    • 2.2 C++STL棧
    • 2.3 Java 棧
    • 2.4 Python棧
    • 2.5 習題
  • 3. 二叉樹
    • 3.1 二叉樹概念
    • 3.2 二叉樹的存儲和編碼
      • 3.2.1 二叉樹的存儲方法
      • 3.2.2 二叉樹存儲的編碼實現
      • 3.2.3 二叉樹的極簡存儲方法
    • 3.3 例題
    • 3.4 習題

第7周: ?棧、二叉樹

1. 基本數據結構概述

??很多計算機教材提到:程序 = 數據結構 + 算法。
?? 本作者曾給《數據結構》、《算法設計與分析》的作者王紅梅老師題寫了一句贈言:“以數據結構為弓,以算法為箭”。
??數據結構是是計算機存儲、組織數據的方法。常用的數據結構有:數組(Array)、棧(Stack)、隊列(Queue)、鏈表(Linked List)、樹(Tree)、圖(Graph)、堆(Heap)、散列表(Hash)等。分為兩大類:線性表、非線性表。數組、棧、隊列、鏈表是線性表,其他是非線性表。

1.1 數據結構和算法的關系

??數據結構和算法往往密不可分。下面以圖的存儲為例,說明數據結構和算法的關系。這幾種存圖的數據結構,各有優缺點,也各有自己的應用場景。
(1)邊集數組
??定義結構體數組:

struct Edge{int u, v, w;
}edges[M];

??其中(u,v,w)表示一條邊,起點是u,終點是v,邊長是w。edges[M]可以存M條邊。
??邊集數組的優點:是最節省空間的存圖方法,存儲空間不可能再少了。n=1000個點,m=5000條邊的圖,使用的存儲空間是12×5000 = 60KB。
??邊集數組的缺點:不能快速定位某條邊。如果要找某點u和哪些點有邊連接,得把整個edges[M]從頭到尾搜一遍才能知道。
??邊集數組的的應用場景:如果算法不需要查找特定的邊,就用邊集數組。例如最小生成樹Kruskal算法、最短路徑Bellman-ford算法。
(2)鄰接矩陣
??定義一個二維數組:

	int edge[N][N];

??其中edge[i][j]表示點i和點j之間有一條邊,邊長為edge[i][j]。它可以存N個點的邊。若edge[i][j]=0,表示i和j之間沒有邊;若edge[i][j] != 0,i和j之間有邊,邊長為edge[i][j]。
??鄰接矩陣的優點:能極快地查詢任意兩點之間是否有邊。如果edge[i][j] != 0,說明點i和j之間有一條邊,邊長edge[i][j]。
??鄰接矩陣的缺點:如果圖是一張稀疏圖,大部分點和邊之間沒有邊,那么鄰接矩陣很浪費空間,因為大多數edge[][]=0,沒有用到。n=1000個點,m=5000條邊的圖,使用的存儲空間是12×1000×1000 = 12MB。
??鄰接矩陣的應用場景:(1)稠密圖,幾乎所有的點之間都有邊,edge[][]數組幾乎用滿了,很少浪費;(2)算法需要快速查找邊,而且計算結果和任意兩點的關系有關,例如最短路徑算法的Floyd算法。
(3)鄰接表
??鄰接矩陣的優點:十分節省空間,因為只存儲存在的邊。
??鄰接矩陣的缺點:沒有明顯的缺點。它的存儲空間只比邊集數組大一點點,而查詢邊的速度只比鄰接矩陣慢一點點。
??鄰接矩陣應用場景:基于稀疏圖的大部分算法。

1.2 線性數據結構概述

??在所有數據結構中,線性表是最簡單的。線性表有數組、鏈表、隊列、棧,它們有一個共同的特征:把同類型的數據一個接一個地串在一起。
??下面對線性表做個概述,并比較它們的優缺點。
(1)數組
??數組是最最簡單的數據結構,它的邏輯結構和物理內存的存儲完全一樣。例如C語言中定義一個整型數組int a[10],系統會分配一個40字節的存儲空間,這100個字符的存儲地址是連續的。

#include <bits/stdc++.h>
using namespace std;
int main(){int a[10];for (int i=0;i<10;i++)  cout << &a[i] << " ";  //打印10個整數的存儲地址return 0;
}

??在作者機器上運行,輸出10個整數的存儲地址:
0x6dfec4 0x6dfec8 0x6dfecc 0x6dfed0 0x6dfed4 0x6dfed8 0x6dfedc 0x6dfee0 0x6dfee4 0x6dfee8
??數組的優點:(1)簡單,容易編程;(2)訪問快捷,要定位到某個數據,只需使用下標即可,例如a[0]是第1個數據,a[i]是第i-1個數據;(3)與某些應用場景直接對應,例如數列是一維數組,可以在一維護數組上排序,矩陣是二維數組,表示空間坐標,等等。
??數組的缺點:刪除和增加數據很麻煩,非常耗時。例如要刪除數組int a[10]的第5個數據,只能采用覆蓋的方法,從第6個數據開始,每個往前挪一位。增加數據也麻煩,例如要在第5個位置插入一個數據,只能把原來第5個開始的數據逐個往后挪一位,空出第5個位置給新數據。
??(2)鏈表
??鏈表是為了克服數組的缺點提出的一種線性表,鏈表的插入和刪除操作,不需要挪動其他數據。簡單地說,鏈表是“是用指針串起來的數組”。鏈表的數據不是連續存放的,而是用指針串起來的。例如下圖刪除鏈表的第3個數據,只要把原來連接第3個數據的指針斷開,然后連接它前后的數據即可,不用挪動其他的數據。
在這里插入圖片描述
??鏈表的優點:增加和刪除數據很便捷。這個優點彌補了數組的缺點。
??鏈表的缺點:定位某個數據比較麻煩。例如要輸出第5個數據,需要從鏈表頭開始,沿著指針一步步走,找到第5個。鏈表的這個缺點卻是數組的優點。
??鏈表和數組的優缺點正好相反,它們的應用場合不同,數組適合靜態數據,鏈表適合動態數據。
??鏈表如何編程實現?在常見的數據結構教材中,鏈表的數據節點是動態分配的,各節點之間用指針來連接。但是在算法競賽中,如果手寫鏈表,一般不用動態分配,而是用靜態數組來模擬。手寫鏈表的代碼見:《算法競賽》第3頁“1.1.2 靜態鏈表”。當然,除非必要,一般不手寫鏈表,而是用系統提供的鏈表,例如C++ STL的list,Java LinkedList,Python的list。
??鏈表在藍橋杯等算法競賽中不太常用,所以本章沒有詳細介紹。
??(3)隊列
??隊列是線性數據的一種使用方式,模擬現實世界的排隊操作。例如排隊購物,只能從隊頭離開隊伍,新來的人只能排到隊尾,不能插隊。隊列有一個出口和一個入口,出口是隊頭,入口是隊尾。隊列的編程實現,可以用數組,也可以用鏈表。
??隊列這種數據結構無所謂優缺點,只有適合不適合。例如寬度優先搜索BFS,就是基于隊列的,用其他數據結構都不合適。
??(4)棧
??棧也是線性數據的一種使用方式,模擬現實世界的單出入口。例如一管泡騰片,先放進去的泡騰片后出來。棧的編程比隊列更簡單,同樣可以用數組或鏈表實現。
??棧有它的使用場合,例如遞歸使用棧來處理函數的自我調用過程。

1.3 二叉樹簡介

??二叉樹是一種高度組織性、高效率的數據結構。例如在一棵有n個節點的滿二叉樹上定位某個數據,只需走logn步,插入和刪除某個數據也只需logn步。在二叉樹的基礎上發展出了很多高級數據結構和算法。大多數高級數據結構,例如樹狀數組、線段樹、樹鏈剖分、平衡樹、動態樹等,都是基于二叉樹的。

2. 棧

??棧(stack)是比隊列更簡單的數據結構,它的特點是“先進后出”。
??隊列有兩個口,一個入口和一個出口。而棧只有唯一的一個口,既從這個口進入,又從這個口出來。所以如果自己寫棧的代碼,比隊列的代碼更簡單。

2.1 手寫棧

??如果使用環境簡單,最簡單的手寫棧代碼用數組實現。

const int N = 300008;                        //定義棧的大小
struct mystack{int a[N];                                //存放棧元素,從a[0]開始int t = -1;                              //棧頂位置,初始棧為空,置初值為-1void push(int data){ a[++t] = data; }    //把元素data送入棧int top()   { return a[t]; }             //讀棧頂元素,不彈出void pop()  { if(t>-1) t--;}             //彈出棧頂int size()  { return t+1;}               //棧內元素的數量int empty() { return t==-1 ? 1:0; }      //若棧為空返回1
};

??使用棧時要注意不能超過棧的空間。上面第1行定義了棧的大小是N,棧內的元素數量不要超過它。
??用下面的例子給出上述手寫代碼的應用。
??例題:表達式括號匹配
??題解:
??合法的括號串例如“(())”、“()()()”,像“)(()”這樣是非法的。合法括號組合的特點是:左括號先出現,右括號后出現;左括號和右括號一樣多。
??括號組合的合法檢查是棧的經典應用。用一個棧存儲所有的左括號。遍歷字符串的每一個字符,處理流程是:
??(1)若字符是 ‘(’,進棧。
??(2)若字符是’)',有兩種情況:如果棧不空,說明有一個匹配的左括號,彈出這個左括號,然后繼續讀下一個字符;如果棧空了,說明沒有與右括號匹配的左括號,字符串非法,輸出NO,程序退出。
??(3)讀完所有字符后,如果棧為空,說明每個左括號有匹配的右括號,輸出YES,否則輸出NO。
??C++代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 300008;                        //定義棧的大小
struct mystack{int a[N];                                //存放棧元素,從a[0]開始int t = -1;                              //棧頂位置,初始棧為空,置初值為-1void push(int data){ a[++t] = data; }    //把元素data送入棧int top()   { return a[t]; }         //讀棧頂元素,不彈出void pop()  { if(t>-1) t--;     }        //彈出棧頂int size()  { return t+1;}            //棧內元素的數量int empty() {return t==-1 ? 1:0; }   //若棧為空返回1
}st;
int main(){char x;while(cin>>x){   //循環輸入if(x=='@') break;       //輸入為@停止;if(x=='(') st.push(x);  //左括號入棧if(x==')'){             //遇到一個右括號if(st.empty()) {cout<<"NO";return 0;} //棧空,沒有左括號與右括號匹配else st.pop();      //匹配到一個左括號,出棧}}if(st.empty()) cout<<"YES"; //棧為空,所有左括號已經匹配到右括號,輸出yeselse cout<<"NO";return 0;
}

??Java代碼

import java.util.Scanner;
public class Main {static final int N = 300008;static class mystack {int[] a = new int[N];int t = -1;void push(int data) {  a[++t] = data;    }int top() {   return a[t];        }void pop(){   if(t > -1) t--;     }int size(){   return t + 1;       }boolean  empty() {   return t == -1 ? true : false; }}public static void main(String[] args) {Scanner sc = new Scanner(System.in);mystack st = new mystack();String s = sc.next();for (int i = 0; i < s.length(); i++) {char x = s.charAt(i);if(x == '@') break;if(x == '(') st.push(x);if(x == ')') {if(st.empty()) {System.out.println("NO");return;}else st.pop();}}if(st.empty()) System.out.println("YES");else System.out.println("NO");}
}

??Python代碼
??Python的手寫棧用到了list。用list模擬棧有一個好處,不用擔心棧空間不夠大,因為list自動擴展空間。而且list的棧操作非常快,因為棧頂是list的末尾元素,棧只有一個出入口,只在list的末尾進行進棧和出棧操作,操作極為快捷。下面是list實現的棧功能。
在這里插入圖片描述
??下面是例題的Python代碼,棧用list模擬。

st = []             #定義棧,用list實現
flag =  True        #判斷左括號和右括號的數量是否一樣多
s = input().strip()
for x in s:if x=='(':  st.append("(")    #進棧if x==")":if len(st)!=0:            #len():棧的長度st.pop()              #出棧,也可以寫成 del st[-1] ,st[-1]是棧頂else:                     #棧已空,沒有匹配的左括號flag = Falsebreak
if len(st)==0 and flag:  print('YES')
else:                    print('NO')

2.2 C++STL棧

??競賽時一般不自己手寫棧,而是用STL stack https://www.cplusplus.com/reference/stack/stack/。
??STL stack的主要操作見下表。
在這里插入圖片描述
??用下面的例題說明STLqueue的應用
??例題:排列
??題解:把符合條件的一對<i, j>稱為一個“凹”。首先模擬檢查“凹”,了解執行的過程。以“3 1 2 5”為例,其中的“凹”有:“3-1-2”和“3-1-2-5”;還有相鄰的“3-1”、“1-2”、“2-5”。一共5個“凹”,總價值13。
??像“3-1-2”和“3-1-2-5”這樣的“凹”,需要檢查連續3個以上的數字。
??例如“3 1 2”,從“3”開始,下一個應該比“3”小,例如“1”,再后面的數字比“1”大,才能形成“凹”。
??再例如“3-1-2-5”,前面的“3-1-2”已經是“凹”了,最后的“5”也會形成新的“凹”,條件是這個“5”必須比中間的“1-2”大才行。
??總結上述過程是:先檢查“3”;再檢查“1”符合“凹”;再檢查“2”,比前面的“1”大,符合“凹”;再檢查“5”,比前面的“2”大,符合“凹”。
??以上是檢查一個“凹”的兩頭,還有一種是“嵌套”。一旦遇到比前面小的數字,那么以這個數字為頭,可能形成新的“凹”。例如“6 4 2 8”,其中的“6-4-2-8”是“凹”,內部的“4-2-8”也是凹。如果學過遞歸、棧,就會發現這是嵌套,所以本題用棧來做很合適。
??以“6 4 2 8”為例,用棧模擬找“凹”。當新的數比棧頂的數小,就進棧;如果比棧頂的數大,就出棧,此時找到了一個“凹”并計算價值。下圖中的圓圈數字是數在數組中的下標位置,用于計算題目要求的價值。
在這里插入圖片描述
??圖(1):6進棧。
??圖(2):4準備進棧,發現比棧頂的6小,說明可以形成凹,4進棧。
??圖(3):2準備進棧,發現比棧頂的4小,說明可以形成凹,2進棧。
??圖(4):8準備進棧,發現比棧頂的2大,這是一個凹“4-2-8”,對應下標“②–④”,彈出2,然后計算價值,j-i+1=④-②+1=3。
??圖(5):8準備進棧,發現比棧頂的4大,這是一個凹“6-4-8”,對應下標“①–④”,彈出4,然后計算價值,j-i+1=④-①+1=4。
??圖(6):8終于進棧了,數字也處理完了,結束。
??在上述過程中,只計算了長度為3和3以上的凹,并沒有計算題目中“(3)a[i]-a[j]之間不存在其他數字”的長度為2的凹,所以最后統一加上這種情況的價值(n-1)×2 = 6。
??最后統計得“6 4 2 8”的總價值是3+4+6=13。
C++代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 300008;
int a[N];                 //這里a[]是題目的數字排列
int main(){int n;  cin>>n;for(int i = 1;i <= n;i++)  cin>>a[i];   //輸入數列stack <int> st;                   //定義棧long long ans = 0;for(int i = 1;i <= n;i++){while(!st.empty() && a[st.top()] < a[i]){st.pop();if(!st.empty()){int last = st.top();ans += (i - last + 1);}}st.push(i);}ans += (n - 1) * 2;              //(3)a[i]-a[j]之間不存在其他數字的情況cout<<ans;
}

2.3 Java 棧

??Java Stack https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Stack.html
??有以下操作。
在這里插入圖片描述
??例題 排列 的Java代碼。

import java.util.Scanner;
import java.util.Stack;
public class Main {static final int N = 300008;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] a = new int[N];for(int i = 1; i <= n; i++)  a[i] = sc.nextInt();        Stack<Integer> st = new Stack<>();long ans = 0;for(int i = 1; i <= n; i++) {while(!st.empty() && a[st.peek()] < a[i]) {st.pop();if(!st.empty()) {int last = st.peek();ans += (long)(i - last + 1);}}st.push(i);}ans += (n - 1) * 2;System.out.println(ans);}
}

2.4 Python棧

??python的棧可以用以下三種方法實現:(1)list;(2)deque;(3)LifoQueue。比較它們的運行速度,list和deque一樣快,而LifoQueue慢得多,建議使用list。前面已經介紹了用list實現棧的方法。
??下面是例題 排列 的代碼。

n = int(input())
a = [int(x) for x in input().split()]
st = []                                       #定義棧,用list實現
ans = 0
for i in range(n):while len(st) != 0 and a[st[-1]] < a[i]:  #st[-1]是棧頂st.pop()                              #彈出棧頂if len(st) != 0:last = st[-1]                     #讀棧頂ans += (i - last + 1)st.append(i)                              #進棧
ans += (n - 1) * 2
print(ans)

2.5 習題

小魚的數字游戲
后綴表達式

【模板】棧

3. 二叉樹

??前面介紹的數據結構數組、隊列、棧,都是線性的,它們存儲數據的方式是把相同類型的數據按順序一個接一個串在一起。簡單的形態使線性表難以實現高效率的操作。
??二叉樹是一種層次化的、高度組織性的數據結構。二叉樹的形態使得它有天然的優勢,在二叉樹上做查詢、插入、刪除、修改、區間等操作極為高效,基于二叉樹的算法也很容易實現高效率的計算。

3.1 二叉樹概念

??二叉樹的每個節點最多有兩個子節點,分別稱為左孩子、右孩子,以它們為根的子樹稱為左子樹、右子樹。二叉樹的每一層以2的倍數遞增,所以二叉樹的第k層最多有2k-1個節點。根據每一層的節點分布情況,有以下常見的二叉樹。
??(1)滿二叉樹
??特征是每一層的節點數都是滿的。第一層只有1個節點,編號為1;第二層有2個節點,編號2、3;第三層有4個節點,編號4、5、6、7;…;第k層有 2 k ? 1 2^{k-1} 2k?1個節點,編號 2 k ? 1 、 2 k ? 1 + 1 、 . . . 、 2 k ? 1 2^{k-1}、2^{k-1}+1、...、2^k-1 2k?12k?1+1...2k?1
??一棵n層的滿二叉樹,節點一共有 1 + 2 + 4 + . . . + 2 n ? 1 = 2 n ? 1 1+2+4+...+2^{n-1} = 2^{n-1} 1+2+4+...+2n?1=2n?1個。
在這里插入圖片描述

??(2)完全二叉樹
??如果滿二叉樹只在最后一層有缺失,并且缺失的節點都在最后,稱為完全二叉樹。圖1.3演示了一棵滿二叉樹和一棵完全二叉樹。
??(3)平衡二叉樹
??任意左子樹和右子樹的高度差不大于1,稱為平衡二叉樹。若只有少部分子樹的高度差超過1,這是一棵接近平衡的二叉樹。
在這里插入圖片描述
??(4)退化二叉樹
??如果樹上每個節點都只有1個孩子,稱為退化二叉樹。退化二叉樹實際上已經變成了一根鏈表。如果絕大部分節點只有1個孩子,少數有2個孩子,也看成退化二叉樹。
??二叉樹之所以應用廣泛,得益于它的形態。高級數據結構大部分和二叉樹有關,下面列舉二叉樹的一些優勢。
??(1)在二叉樹上能進行極高效率的訪問。一棵平衡的二叉樹,例如滿二叉樹或完全二叉樹,每一層的節點數量約是上一層數量的2倍,也就是說,一棵有N個節點的滿二叉樹,樹的高度是O(logN)。從根節點到葉子節點,只需要走logN步,例如N = 100萬,樹的高度僅有logN = 20,只需要20步就能到達100萬個節點中的任意一個。但是,如果二叉樹不是滿的,而且很不平衡,甚至在極端情況下變成退化二叉樹,訪問效率會打折扣。維護二叉樹的平衡是高級數據結構的主要任務之一。
??(2)二叉樹很適合做從整體到局部、從局部到整體的操作。二叉樹內的一棵子樹可以看成整棵樹的一個子區間,求區間最值、區間和、區間翻轉、區間合并、區間分裂等,用二叉樹都很快捷。
??(3)基于二叉樹的算法容易設計和實現。例如二叉樹用BFS和DFS搜索處理都極為簡便。二叉樹可以一層一層地搜索,這是BFS。二叉樹的任意一個子節點,是以它為根的一棵二叉樹,這是一種遞歸的結構,用DFS訪問二叉樹極容易編碼。

3.2 二叉樹的存儲和編碼

3.2.1 二叉樹的存儲方法

??要使用二叉樹,首先得定義和存儲它的節點。
??二叉樹的一個節點包括三個值:節點的值、指向左孩子的指針、指向右孩子的指針。需要用一個結構體來定義二叉樹。
??二叉樹的節點有動態和靜態兩種存儲方法,競賽中一般采用靜態方法。
??(1)動態存儲二叉樹。例如寫c代碼,數據結構的教科書一般這樣定義二叉樹的節點:

struct Node{int value;           //節點的值,可以定義多個值Node *lson, *rson;   //指針,分別指向左右子節點    
};

??其中value是這個節點的值,lson和rson是指向兩個孩子的指針。動態新建一個Node時,用new運算符動態申請一個節點。使用完畢后,需要用delete釋放它,否則會內存泄漏。動態二叉樹的優點是不浪費空間,缺點是需要管理,不小心會出錯,競賽中一般不這樣用。
??(2)用靜態數組存儲二叉樹。在算法競賽中,為了編碼簡單,加快速度,一般用靜態數組來實現二叉樹。下面定義一個大小為N的結構體數組。N的值根據題目要求設定,有時節點多,例如N=100萬,那么tree[N]使用的內存是12M字節,不算大。

struct Node{                //靜態二叉樹int value;               //可以把value簡寫為vint lson, rson;          //左右孩子,可以把lson、rson簡寫為ls、rs
}tree[N];                   //可以把tree簡寫為t

??tree[i]表示這個節點存儲在結構體數組的第i個位置,lson是它的左孩子在結構體數組的位置,rson是它的右孩子在結構體數組的位置。lson和rson指向孩子的位置,也可以稱為指針。
??下圖演示了一棵二叉樹的存儲,圓圈內的字母是這個節點的value值。根節點存儲在tree[5]上,它的左孩子lson=7,表示左孩子存儲在tree[7]上,右孩子rson=3,存儲在tree[3]。
在這里插入圖片描述
??編碼時一般不用tree[0],因為0常常被用來表示空節點,例如葉子節點tree[2]沒有子節點,就把它的子節點賦值為lson = rson = 0。

3.2.2 二叉樹存儲的編碼實現

??下面寫代碼演示上圖中二叉樹的建立,并輸出二叉樹。
??(1)C++代碼。第16~21行建立二叉樹,然后用print_tree()輸出二叉樹。

#include <bits/stdc++.h>
using namespace std;
const int N=100;               //注意const不能少
struct Node{                   //定義靜態二叉樹結構體char v;                     //把value簡寫為vint ls, rs;                 //左右孩子,把lson、rson簡寫為ls、rs
}t[N];                         //把tree簡寫為t
void print_tree(int u){        //打印二叉樹if(u){cout<<t[u].v<<' ';     //打印節點u的值print_tree(t[u].ls);   //繼續搜左孩子print_tree(t[u].rs);   //繼續搜右孩子}
}
int main(){t[5].v='A'; t[5].ls=7; t[5].rs=3;t[7].v='B'; t[7].ls=2; t[7].rs=0;t[3].v='C'; t[3].ls=9; t[3].rs=6;t[2].v='D';    // t[2].ls=0; t[2].rs=0; 可以不寫,因為t[]是全局變量,已初始化為0t[9].v='E';    // t[9].ls=0; t[9].rs=0; 可以不寫t[6].v='F';    // t[6].ls=0; t[6].rs=0; 可以不寫int root = 5;  //根是tree[5]print_tree(5); //輸出: A B D C E Freturn 0;
}

??初學者可能看不懂print_tree()是怎么工作的。它是一個遞歸函數,先打印這個節點的值t[u].v,然后繼續搜它的左右孩子。上圖的打印結果是”A B D C E F”,步驟如下:
??(1)首先打印根節點A;
??(2)然后搜左孩子,是B,打印出來;
??(3)繼續搜B的左孩子,是D,打印出來;
??(4)D沒有孩子,回到B,B發現也沒有右孩子,繼續回到A;
??(5)A有右孩子C,打印出來;
??(6)打印C的左右孩子E、F。
??這個遞歸函數執行的步驟稱為“先序遍歷”,先輸出父節點,然后再搜左右孩子并輸出。還有“中序遍歷”和“后序遍歷”,將在后面講解。
(2)Java代碼

import java.util.*;
class Main {static class Node {char v;int ls, rs;}static final int N = 100;static Node[] t = new Node[N];static void print_tree(int u) {if (u != 0) {System.out.print(t[u].v + " ");print_tree(t[u].ls);print_tree(t[u].rs);}}public static void main(String[] args) {t[5] = new Node(); t[5].v = 'A'; t[5].ls = 7; t[5].rs = 3;t[7] = new Node(); t[7].v = 'B'; t[7].ls = 2; t[7].rs = 0;t[3] = new Node(); t[3].v = 'C'; t[3].ls = 9; t[3].rs = 6;t[2] = new Node(); t[2].v = 'D';t[9] = new Node(); t[9].v = 'E';t[6] = new Node(); t[6].v = 'F';int root = 5;print_tree(5); // 輸出: A B D C E F}
}

(3)Python代碼

N = 100
class Node:   # 定義靜態二叉樹結構體def __init__(self):self.v = ''              # 把value簡寫為vself.ls = 0              # 左右孩子,把lson、rson簡寫為ls、rsself.rs = 0
t = [Node() for i in range(N)]   # 把tree簡寫為t
def print_tree(u):if u:print(t[u].v, end=' ')   # 打印節點u的值print_tree(t[u].ls)print_tree(t[u].rs)
t[5].v, t[5].ls, t[5].rs = 'A', 7, 3
t[7].v, t[7].ls, t[7].rs = 'B', 2, 0
t[3].v, t[3].ls, t[3].rs = 'C', 9, 6
t[2].v = 'D'    # t[2].ls=0; t[2].rs=0; 可以不寫,因為t[]已初始化為0
t[9].v = 'E'    # t[9].ls=0; t[9].rs=0; 可以不寫
t[6].v = 'F'    # t[6].ls=0; t[6].rs=0; 可以不寫
root = 5        # 根是tree[5]
print_tree(5)   # 輸出: A B D C E F

3.2.3 二叉樹的極簡存儲方法

??如果是滿二叉樹或者完全二叉樹,有更簡單的編碼方法,連lson、rson都不需要定義,因為可以用數組的下標定位左右孩子。
??一棵節點總數量為k的完全二叉樹,設1號點為根節點,有以下性質:
??(1) p > 1 p > 1 p>1的節點,其父節點是 p / 2 p/2 p/2。例如 p = 4 p=4 p=4,父親是 4 / 2 = 2 4/2=2 4/2=2 p = 5 p=5 p=5,父親是 5 / 2 = 2 5/2=2 5/2=2
??(2)如果 2 × p > k 2×p> k 2×p>k,那么 p p p沒有孩子;如果 2 × p + 1 > k 2×p+1 > k 2×p+1>k,那么 p p p沒有右孩子。例如 k = 11 k=11 k=11 p = 6 p=6 p=6的節點沒有孩子; k = 12 k=12 k=12 p = 6 p=6 p=6的節點沒有右孩子。
??(3)如果節點 p p p有孩子,那么它的左孩子是 2 × p 2×p 2×p,右孩子是 2 × p + 1 2×p+1 2×p+1
在這里插入圖片描述
??圖中圓圈內是節點的值,圓圈外數字是節點存儲位置。
??(1)C++代碼。用 l s ( p ) ls(p) ls(p)找p的左孩子,用 r s ( p ) rs(p) rs(p)找p的右孩子。 l s ( p ) ls(p) ls(p)中把 p ? 2 p*2 p?2寫成 p < < 1 p<<1 p<<1,用了位運算。

#include <bits/stdc++.h>
using namespace std;
const int N=100;                   //注意const不能少
char t[N];                         //簡單地用一個數組定義二叉樹
int ls(int p){return p<<1;}        //定位左孩子,也可以寫成 p*2
int rs(int p){return p<<1 | 1;}    //定位右孩子,也可以寫成 p*2+1
int main(){t[1]='A';  t[2]='B';  t[3]='C';t[4]='D';  t[5]='E';  t[6]='F';  t[7]='G';t[8]='H';  t[9]='I';  t[10]='J'; t[11]='K';cout<<t[1]<<":lson="<<t[ls(1)]<<" rson="<<t[rs(1)]; //輸出  A:lson=B rson=Ccout<<endl;cout<<t[5]<<":lson="<<t[ls(5)]<<" rson="<<t[rs(5)]; //輸出  E:lson=J rson=Kreturn 0;
}

??(2)Java代碼。

import java.util.Arrays;
public class Main {static int ls(int p){ return p<<1;}static int rs(int p){ return p<<1 | 1;}public static void main(String[] args) {final int N = 100;char[] t = new char[N];t[1]='A';  t[2]='B';  t[3]='C';t[4]='D';  t[5]='E';  t[6]='F';  t[7]='G';t[8]='H';  t[9]='I';  t[10]='J'; t[11]='K';System.out.print(t[1]+":lson="+t[ls(1)]+" rson="+t[rs(1)]);//輸出A:lson=B rson=CSystem.out.println();System.out.print(t[5]+":lson="+t[ls(5)]+" rson="+t[rs(5)]);//輸出E:lson=J rson=K}
}

??(3)Python代碼。

N = 100
t = [''] * N
def ls(p):  return p << 1
def rs(p):  return (p << 1) | 1t[1] = 'A'; t[2] = 'B'; t[3] = 'C'
t[4] = 'D'; t[5] = 'E'; t[6] = 'F'; t[7] = 'G'
t[8] = 'H'; t[9] = 'I'; t[10] = 'J'; t[11] = 'K'print(t[1] + ':lson=' + t[ls(1)] + ' rson=' + t[rs(1)]) # 輸出  A:lson=B rson=C
print(t[5] + ':lson=' + t[ls(5)] + ' rson=' + t[rs(5)]) # 輸出  E:lson=J rson=K

??其實,即使二叉樹不是完全二叉樹,而是普通二叉樹,也可以用這種簡單方法來存儲。如果某個節點沒有值,那就空著這個節點不用,方法是把它賦值為一個不該出現的值,例如賦值為0或無窮大INF。這樣會浪費一些空間,好處是編程非常簡單。

3.3 例題

??二叉樹是很基本的數據結構,大量算法、高級數據結構都是基于二叉樹的。二叉樹有很多操作,最基礎的操作是搜索(遍歷)二叉樹的每個節點,有先序遍歷、中序遍歷、后序遍歷。這3種遍歷都用到了遞歸函數,二叉樹的形態天然適合用遞歸來編程。
在這里插入圖片描述
??(1)先(父)序遍歷,父節點在最前面輸出。先輸出父節點,再訪問左孩子,最后訪問右孩子。上圖的先序遍歷結果是ABDCEF。為什么?把結果分解為:A-BD-CEF。父親是A,然后是左孩子B和它帶領的子樹BD,最后是右孩子C和它帶領的子樹CEF。這是一個遞歸的過程,每個子樹也滿足先序遍歷,例如CEF,父親是C,然后是左孩子E,最后是右孩子F。
??(2)中(父)序遍歷,父節點在中間輸出。先訪問左孩子,然后輸出父節點,最后訪問右孩子。上圖的中序遍歷結果是DBAECF。為什么?把結果分解為:DB-A-ECF。DB是左子樹,然后是父親A,最后是右子樹ECF。每個子樹也滿足中序遍歷,例如ECF,先左孩子E,然后是父親C,最后是右孩子F。
??(3)后(父)序遍歷,父節點在最后輸出。先訪問左孩子,然后訪問右孩子,最后輸出父節點。上圖的后序遍歷結果是DBEFCA。為什么?把結果分解為:DB-EFC-A。DB是左子樹,然后是右子樹EFC,最后是父親A。每個子樹也滿足后序遍歷,例如EFC,先左孩子E,然后是右孩子F,最后是父親C。
??這三種遍歷,中序遍歷是最有用的,它是二叉查找樹的核心。

例題 二叉樹的遍歷
(1)C++代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Node{int v; int ls, rs;
}t[N];                          //tree[0]不用,0表示空結點
void preorder (int p){          //求先序序列if(p != 0){cout << t[p].v <<" ";   //先序輸出preorder (t[p].ls);preorder (t[p].rs);}
}
void midorder (int p){          //求中序序列if(p != 0){midorder (t[p].ls);cout << t[p].v <<" ";   //中序輸出midorder (t[p].rs);}
}
void postorder (int p){         //求后序序列if(p != 0){postorder (t[p].ls);postorder (t[p].rs);cout << t[p].v <<" ";    //后序輸出}
}
int main() {int n;	cin >> n;for (int i = 1; i <= n; i++) {int a, b; cin >> a >> b;t[i].v = i;t[i].ls = a;t[i].rs = b;}preorder(1);  cout << endl;midorder(1);  cout << endl;postorder(1); cout << endl;
}

(2)Java代碼
??下面的Java代碼和上面的C++代碼略有不同。例如在preorder()中沒有直接打印節點的值,而是用joiner.add()先記錄下來,遍歷結束后一起打印,這樣快一些。本題 n = 1 0 6 n=10^6 n=106,規模大,時間緊張。

import java.util.Scanner;
import java.util.StringJoiner;
class Main {static class Node {int v, ls, rs;Node(int v, int ls, int rs) {this.v = v;this.ls = ls;this.rs = rs;}}static final int N = 100005;static Node[] t = new Node[N];                     //tree[0]不用,0表示空結點static void preorder(int p, StringJoiner joiner) { //求先序序列if (p != 0) {joiner.add(t[p].v + "");   //不是直接打印,而是先記錄下來preorder(t[p].ls,joiner);preorder(t[p].rs,joiner);}}static void midorder(int p, StringJoiner joiner) { //求中序序列if (p != 0) {midorder(t[p].ls,joiner);joiner.add(t[p].v + "");//中序輸出midorder(t[p].rs,joiner);}}static void postorder(int p, StringJoiner joiner) { //求后序序列if (p != 0) {postorder(t[p].ls,joiner);postorder(t[p].rs,joiner);joiner.add(t[p].v + ""); //后序輸出}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();for (int i = 1; i <= n; i++) {int a = sc.nextInt(), b = sc.nextInt();t[i] = new Node(i, a, b);}StringJoiner joiner = new StringJoiner(" ");        preorder(1, joiner);        System.out.println(joiner);        joiner = new StringJoiner(" ");midorder(1, joiner);        System.out.println(joiner);joiner = new StringJoiner(" ");postorder(1, joiner);       System.out.println(joiner);}
}

(3)Python代碼

N = 100005
t = [0] * N  # tree[0]不用,0表示空結點
class Node:def __init__(self, v, ls, rs):self.v = vself.ls = lsself.rs = rsdef preorder(p):  # 求先序序列if p != 0:print(t[p].v, end=' ')  # 先序輸出preorder(t[p].ls)preorder(t[p].rs)def midorder(p):  # 求中序序列if p != 0:midorder(t[p].ls)print(t[p].v, end=' ')  # 中序輸出midorder(t[p].rs)def postorder(p):  # 求后序序列if p != 0:postorder(t[p].ls)postorder(t[p].rs)print(t[p].v, end=' ')  # 后序輸出n = int(input())
for i in range(1, n+1):a, b = map(int, input().split())t[i] = Node(i, a, b)preorder(1);  print()
midorder(1);  print()
postorder(1); print()

3.4 習題

完全二叉樹的權值
FBI樹
American Heritage
求先序排列

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/166713.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/166713.shtml
英文地址,請注明出處:http://en.pswp.cn/news/166713.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

VMware共享文件夾不能放mysql的數據

概要 使用VMware搭建了一個虛擬機&#xff0c;準備做數據庫服務器。服務器是linux系統&#xff0c;安裝了mysql和redis。為了數據安全&#xff0c;準備將mysql的數據文件放到共享文件夾中&#xff0c;嘗試多次后都沒成功。問題可能是共享文件夾中的文件的擁有者都是root&#…

MFC所有控件介紹及基本使用

一、前言 本篇文檔介紹了MFC控件的基本使用&#xff0c;同時提供了關于MFC控件使用的工程代碼&#xff0c;程序界面如下圖&#xff0c;有興趣的可以到文檔最后的鏈接處進行下載。 二、控件介紹 2.1 Button &#xff08;按鈕&#xff09; 2.2 CheckBox&#xff08;復選框&am…

【jvm】虛擬機之堆

目錄 一、堆的核心概述二、堆的內存細分&#xff08;按分代收集理論設計&#xff09;2.1 java7及以前2.2 java8及以后 三、堆內存大小3.1 說明3.2 參數設置3.3 默認大小3.4 手動設置3.5 jps3.6 jstat3.7 OutOfMemory舉例 四、年輕代與老年代4.1 說明 五、對象分配過程5.1 說明5…

電腦鍵盤推薦

一、鍵盤分類 &#xff08;1&#xff09;鍵位個數 目前有75&#xff0c;84&#xff0c;87&#xff0c;98&#xff0c;104&#xff0c;108的。 &#xff08;2&#xff09;薄膜鍵盤和機械鍵盤 薄膜鍵盤就是大多數辦公室常見的鍵盤&#xff0c;主要打一個便宜&#xff0c;耐造…

Python武器庫開發-前端篇之Html基礎語法(二十九)

前端篇之Html基礎語法(二十九) HTML 元素 HTML元素指的是HTML文檔中的標簽和內容。標簽用于定義元素的類型&#xff0c;而內容則是元素所包含的內容。HTML元素由開始標簽和結束標簽組成&#xff0c;也可以是自閉合標簽。 例如&#xff0c;下面是一個叫做<p>的HTML元素…

Android開發從0開始(服務)

Android后臺運行的解決方案&#xff0c;不需要交互&#xff0c;長期運行。 服務基礎框架&#xff1a; public class MyService extends Service { public MyService() { } Override public IBinder onBind(Intent intent) { //activity與service交互&#xff08;需要繼…

全網最全圖解Kafka適用場景

消息系統 消息系統被用于各種場景&#xff0c;如解耦數據生產者&#xff0c;緩存未處理的消息。Kafka 可作為傳統的消息系統的替代者&#xff0c;與傳統消息系統相比&#xff0c;kafka有更好的吞吐量、更好的可用性&#xff0c;這有利于處理大規模的消息。 根據經驗&#xff…

淘寶、1688代購系統;微信代購小程序,代購系統源代碼,PHP前端源碼演示

電商價格數據監測接口、品牌商品控價接口、商品數據分析接口和比價搜索API接口都是非常實用的電商接口服務&#xff0c;下面我將為您詳細介紹這些接口的用途和使用方式。 1.電商價格數據監測接口&#xff08;注冊獲取請求調用key&#xff09; taobao.item_get-獲得淘寶商品詳…

ubuntu環境刪除qtcreator方法

文章目錄 方法1方法2方法3參考不同的安裝方法,對應不同的刪除方法 方法1 apt-get或者dpkg 方法2 QtCreatorUninstaller 方法3 MaintenanceTool

2023亞太杯數學建模C題思路分析 - 我國新能源電動汽車的發展趨勢

1 賽題 問題C 我國新能源電動汽車的發展趨勢 新能源汽車是指以先進技術原理、新技術、新結構的非常規汽車燃料為動力來源( 非常規汽車燃料指汽油、柴油以外的燃料&#xff09;&#xff0c;將先進技術進行汽車動力控制和驅動相結 合的汽車。新能源汽車主要包括四種類型&#x…

js中forEach、filter、map的區別

forEach、filter、map都可以遍歷數組&#xff0c;那么三者有什么區別&#xff1f; 區別&#xff1a; forEach遍歷數組全部元素&#xff0c;利用回調函數對數組進行操作&#xff0c;不會返回新的數組,return只用于控制循環是否跳出當前循環; filter返回一個新的數組&#xff0…

全新Self-RAG框架亮相,自適應檢索增強助力超越ChatGPT與Llama2,提升事實性與引用準確性

全新Self-RAG框架亮相,自適應檢索增強助力超越ChatGPT與Llama2,提升事實性與引用準確性 1. 基本思想 大型語言模型(LLMs)具有出色的能力,但由于完全依賴其內部的參數化知識,它們經常產生包含事實錯誤的回答,尤其在長尾知識中。 為了解決這一問題,之前的研究人員提出了…

c語言編程題經典100例——(16~20例)

1&#xff0c;將一個字符串轉換為整數 在C語言中&#xff0c;可以使用庫函數 atoi() 將字符串轉換為整數。 atoi() 函數接受一個字符串作為參數&#xff0c;并返回其對應的整數。 以下是一個示例代碼&#xff0c;演示如何使用 atoi() 函數將字符串轉換為整數&#xff1a; #i…

Linux下安裝python3步驟:

1.下載Python3源碼 你需要從Python官網下載Python3的源碼包。本文以Python 3.9.9為例。你可以使用wget命令來下載源碼包到你的Linux主目錄中: wget https://www.python.org/ftp/python/3.9.9/Python-3.9.9.tgz2.編譯和安裝Python3 下載好源碼包后&#xff0c;你需要解壓它&…

【LeetCode:2824. 統計和小于目標的下標對數目 | 模擬+二分】

&#x1f680; 算法題 &#x1f680; &#x1f332; 算法刷題專欄 | 面試必備算法 | 面試高頻算法 &#x1f340; &#x1f332; 越難的東西,越要努力堅持&#xff0c;因為它具有很高的價值&#xff0c;算法就是這樣? &#x1f332; 作者簡介&#xff1a;碩風和煒&#xff0c;…

ubuntu22.04中ros2 安裝rosbridge

ros2 啟動rosbridge&#xff1a; 要啟動ROS2中的rosbridge&#xff0c;需要先安裝ROS2的rosbridge_suite軟件包。使用以下命令安裝&#xff1a; 更新過可忽略 sudo apt-get update安裝命令 sudo apt-get install ros--rosbridge-suite 注意&#xff1a; 將替換為正在使用的R…

深度學習圖像風格遷移 - opencv python 計算機競賽

文章目錄 0 前言1 VGG網絡2 風格遷移3 內容損失4 風格損失5 主代碼實現6 遷移模型實現7 效果展示8 最后 0 前言 &#x1f525; 優質競賽項目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度學習圖像風格遷移 - opencv python 該項目較為新穎&#xff0c;適合作為競賽課題…

uniapp高德、百度、騰訊地圖配置 SHA1

uniapp高德、百度、騰訊地圖配置 SHA1 當winr彈出cmd彈框后輸入 keytool -list -v -keystore debug.keystore 顯示keytool 不是內部或外部命令&#xff0c;也不是可運行的程序或批處理文件。可以先看看是否有下載jdk且配置了環境變量&#xff0c;具體操作如下&#xff1a;keyto…

please upgrade numpy version to >=1.20

升級 upgrade numpy_升級numpy-CSDN博客 pip install numpy --upgrade 沒有pip conda install numpy --upgrade 會報錯 conda list numpy來查看numpy版本 似乎這個numpy要看numpy-base這個 似乎沒有pip

【開源】基于JAVA的計算機機房作業管理系統

項目編號&#xff1a; S 017 &#xff0c;文末獲取源碼。 \color{red}{項目編號&#xff1a;S017&#xff0c;文末獲取源碼。} 項目編號&#xff1a;S017&#xff0c;文末獲取源碼。 目錄 一、摘要1.1 項目介紹1.2 項目錄屏 二、功能模塊2.1 登錄注冊模塊2.2 課程管理模塊2.3 課…