文章目錄

• • • 1. 非遞歸：快速排序 漢諾塔
    • • 1.1 快速排序非遞歸
      • 1.2 漢諾塔非遞歸
    • 2. 判斷完全二叉樹
    • 3. 二叉鏈表交換左右孩子
    • • 3.1 遞歸
      • 3.1 非遞歸
    • 4. 01背包問題

1. 非遞歸：快速排序 漢諾塔

非遞歸思想啟發博文：https://blog.csdn.net/bobbypollo/article/details/79891556
快速排序的學習博文：https://blog.csdn.net/qq_36528114/article/details/78667034

1的重點為二者的非遞歸，代碼中的遞歸主要是在理解二者非遞歸思想時用于對比

遞歸的重要的一點就是必須先解決子問題，再基于子問題來解決當前問題。
即先進后出，
故遞歸轉非遞歸時用棧來解決。

1.1 快速排序非遞歸

//快速排序遞歸非遞歸對比 #include <iostream> #include <stack> using namespace std;//快速排序 template <class T> int Particition(T* pa, int low, int high) {int i = low, j = high;T temp = pa[i];while (i != j){while (i<j && pa[j]>temp)j--;if (i < j)pa[i++] = pa[j];while (i < j && pa[i] < temp)i++;if (i < j)pa[j--] = pa[i];}pa[i] = temp;return i; } //快速排序遞歸算法 void QuickSoret(T* pa, int low, int high) {if (low > high)return;int m = Particition(pa, low, high);QuickSoret(pa, low, m - 1);QuickSoret(pa, m + 1, high); } //快速排序非遞歸算法 template <class T> void QuickSoret2(T* pa, int low, int high) {T i,j;stack<T> S;if (low > high)return;int m;S.push(low);S.push(high);while (!S.empty()){j = S.top();S.pop();i = S.top();S.pop();m = Particition(pa, i, j);if (m - 1 > i){S.push(i);S.push(m-1);}if (m + 1 < j){S.push(m+1);S.push(j);}} } //附加驗證 template<class T> void PrintQuickSoretResout(T* pa, int low, int high) {QuickSoret2(pa, low, high);for (int k = low; k <= high; k++)cout << pa[k] << " ";cout << endl; } int main() {int paa[10] = { 2,3,6,1,4,5,9,8,7,10 };PrintQuickSoretResout(paa, 0, 9); }

1.2 漢諾塔非遞歸

這里寫的漢諾塔非遞歸比較局限，只考慮3根柱子A, B, C，且只有A上有 n 個環，要求全移到 C 上。
其他的情況還在探討中
非遞歸思想和上面 快速排序非遞歸 的思想一樣

//漢諾塔遞歸非遞歸對比算法 #include <iostream> #include <stack> using namespace std;//漢諾塔遞歸算法 void Hanoi(int n, char A, char B, char C) {if (n <= 0)return;if (n > 1)Hanoi(n - 1, A, C, B);cout << '(' << n << ")," << A << ',' << C << endl;if (n > 1)Hanoi(n - 1, B, A, C); } // 漢諾塔非遞歸算法 void Hanoi2(int n, char A, char B, char C) {if (n <= 0)return;char a, b, c;stack<char> S;S.push(A);S.push(B);S.push(C);while (!S.empty()){c = S.top();S.pop();b = S.top();S.pop();a = S.top();S.pop();cout << '(' << n-1 << ")," << a << ',' << c << endl;if (n - 1 > 1){S.push(a);S.push(c);S.push(b);n--;}} } //附加驗證 int main() {char E = 'A', F = 'B', G = 'C';Hanoi(3, E, F, G);cout << endl;return 0; }

2. 判斷完全二叉樹

每個節點有四種情況，根據完全二叉樹定義進行 標記或判斷
該博文思路相同，講解詳細：https://blog.csdn.net/qq_40938077/article/details/80471997

bool isCBTtree(const BTnode<T>* t) {if (t == NULL) //空樹是完全二叉樹return true;queue<const BTnode<T>*> Q;Q.push(t);bool tag = false;while (!Q.empty()){t = Q.front();Q.pop();if ((tag && (t->left!=NULL || t->right != NULL)) || (t->left == NULL && t->right != NULL))return false;if(t->left)Q.push(t->left);if(t->right)Q.push(t->right);if(!t->right)tag=true;}return true; }

3. 二叉鏈表交換左右孩子

3.1 遞歸

template <class T> void ChangLR1(BTnode<T>* t) {if (t->left == NULL && t->right == NULL)return;BTnode<T>* temp;temp = t->left;t->left = t->right;t->right = temp;if (t->left)ChangLR1(t->left);if (t->right)ChangLR1(t->right);cout << endl; }

3.1 非遞歸

template <class T> void ChangLR2(BTnode<T>* t) {if (t == NULL)return;queue <BTnode<T>*> Q;Q.push(t);BTnode<T>* temp;while (!Q.empty()){t = Q.front();Q.pop();temp = t->left;t->left = t->right;t->right = temp;if (t->left)Q.push(t->left);if (t->right)Q.push(t->right);}cout << endl; }

4. 01背包問題

關于01背包問題，有一篇博文講的非常妙，看完后把表手動打一遍理解更深刻：https://blog.csdn.net/qq_38410730/article/details/81667885

下面的代碼其實還可以模塊化，有機會繼續改善

#include <iostream> #include <algorithm> using namespace std;int item[5] ; int w[5] = { 0,2,3,4,5 }; int v[5] = { 0,3,4,5,6 }; int dp[5][9] = { {0} }; int Vbag = 8;void xuanzhe() {int i, j;for(i=1;i<=4;i++)for (j = 1; j <= Vbag; j++){if (j >= w[i]){dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i]] + v[i] );//item[i] = 1;}else{dp[i][j] = dp[i - 1][j];//item[i] = 0;}} }void dabiao() {int i, j;for (i = 0; i <= 4; i++){ for (j = 0; j <=8; j++)cout << dp[i][j] << " ";cout << endl;}cout << endl;for (i = 1; i <= 4; i++)cout << item[i] << " ";cout << endl; }void zhaoduilie(int i,int j) {if(i >= 0 ){if (dp[i][j] == dp[i - 1][j]){item[i] = 0;zhaoduilie(i - 1,j);}if (j - w[i] >= 0 && dp[i][j] == dp[i - 1][j - w[i]] + v[i]){item[i] = 1;zhaoduilie(i - 1,j-w[i]);}} }int main() {xuanzhe();zhaoduilie(4,8);dabiao(); }

總結

以上是生活随笔為你收集整理的【数据结构】二叉树题目代码总结 （快速排序与汉诺塔的非递归 、判断完全二叉树 、二叉链表交换左右孩子 、01背包问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。