【数据结构】二叉树基本代码总结

文章目录

1. 基本性质2. 存储方式及基本结构1. 顺序存储2. 链式存储 3. 层次遍历、顺序转链式非递归及垂直输出1. 层次遍历法一2. 层次遍历法二3. 顺序转链式非递归4. 垂直输出 4. 前序遍历的递归非递归及快速排序1. 前序遍历的递归2. 前序遍历的非递归3. 快速排序 5. 中序遍历的递归非递归及汉诺塔递归算法1. 中序遍历的递归2. 中序遍历的非递归3. 汉诺塔递归算法 6. 后序遍历的递归非递归及 深度求解、复制删除和顺转链递归1. 后序遍历的递归2. 后序遍历的非递归3. 求二叉树的深度4. 复制二叉树链表5. 删除二叉树链表6. 顺序转链式递归 7. 中序与其外二者之一结合求真实二叉树

1. 基本性质

双亲为 a_i ,左孩子为 a_2i ,右孩子为 a_2i+1孩子为 a_i ,双亲为 a_(i-1)/2第 i 层上最多有 2ⁱ 个节点深度为 k 的树最多有 2^k+1-1 个节点节点数为 n 的完全二叉树深度为 [log₂n]满二叉树 (完美二叉树) 一定是 完全二叉树，但后者不一定是前者

2. 存储方式及基本结构

1. 顺序存储

以数组的形式存储，数组下标即二叉树下标，数组内容即二叉树的内容

2. 链式存储

//基本结构(含默认构造) template <class T> struct BTnode { T data; BTnode* left, * right; BTnode(const T& item = T(), BTnode* lptr = NULL, BTnode* rptr = NULL) :data(item), left(lptr), right(rptr) {} }; //建立二叉树 template <class T> BTnode<T>* GetBtnode(const T& item, BTnode<T>* lp = NULL, BTnode<T>* rp = NULL) { BTnode<T>* p; p = new BTnode<T>(item, lp, rp); if (p == NULL) { cerr << "Memory allocation failure!" << endl; exit(1); } cout << "GetBtnode called!" << endl; return p; }

注意： 当 建立二叉树函数

是类模板中的成员时: 左右子树可以直接指向NULL是函数模板时: 不可以直接指向NULL，必须建一个声明了T的种类的节点nullp，节点内容为NULL //类模板中的成员时 //法一： BTnode<char>* nullp = NULL; BTnode<char>* c = GetBtnode('C', f, nullp); //合法 //法二： BTnode<char>* b = GetBtnode('B', NULL, NULL); //合法 //函数模板时 //法一： BTnode<char>* nullp = NULL; BTnode<char>* c = GetBtnode('C', f, nullp); //合法 //法二： BTnode<char>* b = GetBtnode('B', NULL, NULL); //非法

3. 层次遍历、顺序转链式非递归及垂直输出

1. 层次遍历法一

队列 先入队 删除和访问作为循环

//层次遍历法一 template <class T> void Level(const BTnode<T>* t) { if (t == NULL) return; queue <const BTnode<T>*> Q; Q.push(t); while (!Q.empty()) { t = Q.front(); Q.pop(); cout << t->data; if (t->left) Q.push(t->left); if (t->right) Q.push(t->right); } cout<<endl;

2. 层次遍历法二

队列 先访问和入队 出队作为循环

//层次遍历法二 template <class T> void Level(const BTnode<T>* t) { if (t == NULL) return; queue <const BTnode<T>*> Q; cout << t->data; Q.push(t); while (!Q.empty()) { t = Q.front(); Q.pop(); if (t->left) { cout << t->left->data; Q.push(t->left); } if (t->right) { cout << t->right->data; Q.push(t->right); } } cout << endl; }

3. 顺序转链式非递归

对比层次遍历法二 队列 先访建和入队 出队和+1/2作为循环

//顺序储存转链式储存非递归 template <class T> BTnode<T>* MakeLinked(const vector<T>& L) { if (L.size() == 0) return NULL; queue<BTnode<T>*> Q; BTnode<T>* parent, * child; int n = L.size(),i = 0; BTnode<T>* t = GetBtnode(L[0]); Q.push(t); while (!Q.empty()) { parent = Q.front(); Q.pop(); if (2 * i + 1 < n && L[2 * i + 1] != T()) { child = GetBtnode(L[2 * i + 1]); parent->left = child; Q.push(child); } if (2 * i + 2 < n && L[2 * i + 2] != T()) { child = GetBtnode(L[2 * i + 2]); parent->right = child; Q.push(child); } i++; while (i < n && L[i] == T()) i++; } cout << "MakeLinked(1) called!" << endl; return (t); }

4. 垂直输出

对比层次遍历法一 队列 节点和位置同步 先入队 出队访问和判断作为循环

//垂直输出 struct Loction { int xindent, ylevel; }; void Gotoxy(int x, int y) { static int level = 0, indent = 0; if (y == 0) { indent = 0; level = 0; } if (level != y) { cout << endl; indent = 0; level++; } cout.width(x - indent); indent = x; } template <class T> void PrintTree(const BTnode<T>* t, int screenwidth) { if (t == NULL) return; int level = 0, offset = screenwidth / 2; Loction fLoc, cLoc; queue<const BTnode<T>*> Q; queue<Loction> LQ; fLoc.xindent = offset; fLoc.ylevel = level; Q.push(t); LQ.push(fLoc); while (!Q.empty()) { t = Q.front(); Q.pop(); fLoc = LQ.front(); LQ.pop(); Gotoxy(fLoc.xindent, fLoc.ylevel); cout << t->data; if (fLoc.ylevel != level) { level++; offset = offset / 2; } if (t->left) { Q.push(t->left); cLoc.ylevel = fLoc.ylevel + 1; cLoc.xindent = fLoc.xindent - offset / 2; LQ.push(cLoc); } if (t->right) { Q.push(t->right); cLoc.ylevel = fLoc.ylevel + 1; cLoc.xindent = fLoc.xindent + offset / 2; LQ.push(cLoc); } } cout << endl; }

4. 前序遍历的递归非递归及快速排序

1. 前序遍历的递归

//先序遍历的递归 template <class T> void Preorder(const BTnode<T>* t) { if (t == NULL) return; cout << t->data; if (t->left) Preorder(t->left); if (t->right) Preorder(t->right); }

2. 前序遍历的非递归

栈 while (t || !S.empty()) { 若t: 访问 右入栈 指左 ； 否则: 出栈 (且取出栈) }

//前序遍历的非递归 template <class T> void SimPreorder(const BTnode<T>* t) { if (!t) return; stack<const BTnode<T>*> S; while (t || !S.empty()) { if (t) { cout << t->data; if (t->right) S.push(t->right); t = t->left; } else { t = S.top(); S.pop(); } } }

3. 快速排序

左右移 互换 取下标

//快速排序 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; } template<class T> 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 PrintQuickSoretResout(T* pa, int low, int high) { QuickSoret(pa, low, high); for (int k = low; k <= high; k++) cout << pa[k] << " "; cout << endl; }

5. 中序遍历的递归非递归及汉诺塔递归算法

1. 中序遍历的递归

//中序遍历的递归 template <class T> void Inorder(const BTnode<T>* t) { if (!t) return; if (t->left) Inorder(t->left); cout << t->data; if (t->right) Inorder(t->right); }

2. 中序遍历的非递归

栈 while (t || !S.empty()) { 若t: 入栈 指左 否者: 出栈 访问 指右 }

//中序遍历的非递归 template <class T> void SimInorder(const BTnode<T>* t) { if (!t) return; stack<const BTnode<T>*> S; while (t || !S.empty()) { if (t) { S.push(t); t = t->left; } else { t = S.top(); S.pop(); cout << t->data; t = t->right; } } }

3. 汉诺塔递归算法

对比中序遍历的递归

//汉诺塔递归算法 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); }

6. 后序遍历的递归非递归及 深度求解、复制删除和顺转链递归

1. 后序遍历的递归

//后序遍历的递归 template <class T> void Postorder(const BTnode<T>* t) { if (!t) return; if (t->left) Postorder(t->left); if (t->right) Postorder(t->right); cout << t->data; }

2. 后序遍历的非递归

栈 节点和tag同步 while (t || !S.empty()) { 若t: 入栈 指左 否则: { 出栈 若tag为1: 入栈 改1为2 指右 否则: 访问 } }

//后序遍历的非递归 template <class T> void SimPostorder(const BTnode<T>* t) { if (!t) return; int tag; const BTnode<T>* temp; stack<const BTnode<T>*> S; stack<int> tagS; while (t || !S.empty()) { if (t) { S.push(t); tagS.push(1); t = t->left; } else { temp = S.top(); tag = tagS.top(); S.pop(); tagS.pop(); if (tag == 1) { S.push(temp); tagS.push(2); t = temp->right; } else cout << temp->data; } } }

3. 求二叉树的深度

//求二叉树的深度 template<class T> int Depth(const BTnode<T>* t) { if (!t) return -1; int l = Depth(t->left); int r = Depth(t->right); return (1 + (l > r ? l : r)); }

4. 复制二叉树链表

//复制二叉树链表 template<class T> BTnode<T>* CopyTree(const BTnode<T>* t) { if (!t) return(NULL); BTnode<T>* l = CopyTree(t->left); BTnode<T>* r = CopyTree(t->right); return (GetBtnode(t->data, l, r)); }

5. 删除二叉树链表

//删除二叉树链表 template<class T> void DeleteTree(const BTnode<T>* t) { if (!t) return; DeleteTree(t->left); DeleteTree(t->right); delete t; t = NULL; }

6. 顺序转链式递归

//顺序储存转换为链式的递归 template<class T> BTnode<T>* MakeLinked(const vector<T>& L, int size, int pos) { if (pos >= size || L[pos] ==T()) return NULL; BTnode<T>* left = MakeLinked(L, size, 2 * pos + 1); BTnode<T>* right = MakeLinked(L, size, 2 * pos + 2); BTnode<T>* t = GetBtnode(L[pos], left, right); return t; }

7. 中序与其外二者之一结合求真实二叉树

以前序和中序为例 计算相差节点数 左右递归 建首

//先序和中序 template<class T> BTnode<T>* MakeLinked(const T* pL, const T* iL, int size) { if (size <= 0) return NULL; BTnode<T>* t, * left, * right; const T* rL; int k; for (rL = iL; rL < iL + size; rL++) if (*rL == *pL) break; k = rL - iL; left = MakeLinked(pL + 1,iL, k); right = MakeLinked(pL + k + 1,iL + k + 1 , size - k - 1); t = GetBtnode(*pL, left, right); return(t); }

上面就是二叉树的一些知识点，如果哪里有错的地方，还望指出。