网站安全维护方案,电子商务网站开发系统,网站开发者都是英文怎样开发呢,琚宾设计公司官网文章目录 10.二叉树(1).二叉树的基本概念(2).遍历#1.前序遍历#2.中序遍历#3.后序遍历#4.非递归中序遍历 (3).中序前/后序建树#1.中序前序遍历建树#2.中序后序遍历建树 (4).递归和二叉树基本操作#1.求树高#2.求结点数#3.求叶子结点数#4.复制树#5.判断两棵树是否相等 (5).特殊二叉… 文章目录 10.二叉树(1).二叉树的基本概念(2).遍历#1.前序遍历#2.中序遍历#3.后序遍历#4.非递归中序遍历 (3).中序前/后序建树#1.中序前序遍历建树#2.中序后序遍历建树 (4).递归和二叉树基本操作#1.求树高#2.求结点数#3.求叶子结点数#4.复制树#5.判断两棵树是否相等 (5).特殊二叉树#1.满二叉树#2.完全二叉树 (6).堆#1.基本思想#2.堆的基本操作i.上浮ii.下沉iii.建堆iv.插入元素v.删除元素 #3.堆排序 小结 10.二叉树 说完了树接下来就该说说一些我们比较常用的树了二叉树就是其中之一它的基本结构如下
struct TreeNode
{int val;TreeNode* left;TreeNode* right;
};很高兴这次我们不用再存一个vector或者其他什么了这样操作起来可要方便不少呢
(1).二叉树的基本概念 二叉树是由 n ( n ≥ 0 ) n(n\ge0) n(n≥0)个结点所构成的集合这个集合或者为空或者由一个根结点及表示根结点的左、右子树的两个互不相交的结点集合所组成而根结点的左、右子树也都是二叉树 二叉树是有序树把第一个和第二个子结点或子树分别称为左子结点和右子结点或子树严格区分左右子树
(2).遍历 因为二叉树的每个结点只有左、中、右三个方向因此二叉树的遍历方式在树的基础上还包含了中序遍历所以我们接下来给出三种遍历方式的代码
#1.前序遍历 前序遍历的打印顺序是中、左、右
void PreOrderTraversal(const TreeNode* root)
{if (root) {cout root-val ;PreOrderTraversal(root-left);PreOrderTraversal(root-right);}
}#2.中序遍历 前序遍历的打印顺序是左、中、右
void InOrderTraversal(const TreeNode* root)
{if (root) {InOrderTraversal(root-left);cout root-val ; InOrderTraversal(root-right);}
}#3.后序遍历 前序遍历的打印顺序是左、右、中
void PostOrderTraversal(const TreeNode* root)
{if (root) {PostOrderTraversal(root-left);PostOrderTraversal(root-right);cout root-val ; }
}#4.非递归中序遍历 非递归的中序遍历的流程是这样的每个结点都往左子结点走把自己压入栈中一旦某个左子结点为空就回溯到上一个根即栈顶然后再遍历根的右子树这么一直重复就好了
void NoRecursionInOrderTraversal(const TreeNode* root)
{if (!root) return;stackconst TreeNode* s;const TreeNode* ptr{ root };while (ptr || !s.empty()) {if (ptr) {s.push(ptr);ptr ptr-left;}else {ptr s.top();s.pop();cout ptr-val ;ptr ptr-right;}}
}(3).中序前/后序建树 前序遍历后序遍历的结果是不能建出一棵二叉树的比如下面这个例子 T1和T2两棵树的前序遍历都是AB后序遍历都是BA因此我们靠前序后序两种序列是没有办法还原一棵树的但是如果是中序遍历呢 比如T1的中序遍历是BAT2的中序遍历是AB这样一来两棵树就可以被区别出来了在这里我不给出证明了我们需要的一点是只要我们有中序遍历结果前序或后序二选一的结果就可以还原出唯一的一棵二叉树了 还有需要注意的点根据根结点可以把中序遍历序列拆解成左子树和右子树两个部分例如左子树有 k k k个结点而右子树有 n n n个结点则在前序遍历序列中 1 ∼ k 1\sim k 1∼k 的结点即为左子树的前序遍历结果 k 1 ∼ k n k1\sim kn k1∼kn 的结点即为右子树的前序遍历结果这个是比较自然的比如我们在做前序遍历的时候我们也是首先打印根结点在把所有左子树结点打印出来之后再打印出右子树结点因此这一点在之后对我们会非常有用
#1.中序前序遍历建树 我们先来思考一下对于中序FDHGIBEAC前序ABDFGHIEC这样的结果我们要怎么还原呢首先先序遍历的第一个结点一定是根结点所以取出A前序变为BDFGHIEC中序找到A后拆分成左子树FDHGIBE和右子树C 然后递归地我们再找到前序序列中的B作为A左子树的根结点再在左子树的中序遍历中找到B拆分成B的左子树FDHGI和右子树E然后就这么一直做下去最后我们就可以得到一棵唯一的树 所以我们只要每次根据索引和位置把序列切分成左子树和右子树对应的序列再利用递归的方法分别完成左右子树的构建过程即可
void buildTree(TreeNode* root, const string preorder, const string inorder)
{if (inorder.size() 0) {root nullptr; // 切记当切分到0的时候要将对应的结点设置为空指针return;}root new TreeNode;int k{ 0 };while (preorder[0] ! inorder[k]) k;root new TreeNode{ inorder[k], nullptr, nullptr };buildTree(root-left, preorder.substr(1, k), inorder.substr(0, k));buildTree(root-right, preorder.substr(k1, preorder.size() - 1 - k), inorder.substr(k1, inorder.size() - 1 - k));
}这里采取了字符串来传入前序和中序遍历序列因为这里可以采取substr方法可以比较简单地完成整个流程当然我们用迭代器的方法就可以用vector来完成的在中序后序遍历中我会给出vector的方法
#2.中序后序遍历建树 中序后序遍历的方法其实和前序一样只是这一次我们每次都从后序遍历的最后一个结点中取出来作为根结点所以代码也很容易写出来
TreeNode* buildTree(vectorint inorder, vectorint postorder)
{if (postorder.size() 0) return nullptr;int val{ postorder[postorder.size() - 1] };TreeNode* root new TreeNode{ val, nullptr, nullptr };if (postorder.size() 1) return root;int k{ 0 };while (inorder[k] ! val) k;vectorint leftInorder{ inorder.begin(), inorder.begin() k };vectorint rightInorder{ inorder.begin() k 1, inorder.end() };postorder.resize(postorder.size() - 1); // 去掉最后一个元素比较方便后续直接使用.end()获取最后一个元素vectorint leftPostorder{ postorder.begin(), postorder.begin() leftInorder.size() };vectorint rightPostorder{ postorder.begin() leftInorder.size(), postorder.end() };root-left buildTree(leftInorder, leftPostorder);root-right buildTree(rightInorder, rightPostorder);return root;
}其实本质是一样的我们还是对整个序列进行了一系列的分割然后再完成后续的建树过程
(4).递归和二叉树基本操作 和前文中提过的多叉树一样二叉树的定义同样是递归的因此我们仍然可以利用递归的方法完成二叉树的各种操作
#1.求树高 树的高度定义为所有结点的深度的最大值我们前面认为树根的高度为0空树高度为-1所以求最大值我们可以写出下面的递归式 h e i g h t m a x { l e f t _ h e i g h t , r i g h t _ h e i g h t } 1 height max\{left\_height, right\_height\} 1 heightmax{left_height,right_height}1 所以代码也是很好写的咯让我们来试试吧
int max(int a, int b)
{return (a b) ? a : b;
}int tree_height(const TreeNode* root)
{if (!root) return -1;if ((!root-left) (!root-right)) return 0;int hL{ tree_height(root-left) };int rL{ tree_height(root-right) };return max(hL, rL) 1;
}#2.求结点数 求结点数也很简单我们只需要 c n t l e f t _ c n t r i g h t _ c n t 1 cnt left\_cnt right\_cnt 1 cntleft_cntright_cnt1
int count(const TreeNode* root)
{if (!root) return 0;return count(root-left) count(root-right) 1;
}#3.求叶子结点数 叶子结点数也是一样我们需要左子树的叶子结点数右子树的叶子结点树的值即可: l e a v e s l e f t _ l e a v e s r i g h t _ l e a v e s leaves left\_leaves right\_leaves leavesleft_leavesright_leaves
int leaves(const TreeNode* root)
{if ((!root-left) (!root-right)) return 1;return leaves(root-left) leaves(root-right);
}#4.复制树 复制树就是把一棵树完整地复制另外一棵出来那么其实也就是说遇到某个结点把左子树复制一次再把右子树复制一次就好了
TreeNode* BiTreeCopy(const TreeNode* root)
{if (!root) return nullptr;TreeNode* p{ new TreeNode{root-val, nullptr, nullptr} };p-left BiTreeCopy(root-left);p-right BiTreeCopy(root-right);return p;
}#5.判断两棵树是否相等 一样的套路左子树相等 本身相等 右子树相等
bool equal(const TreeNode* t1, const TreeNode* t2)
{if (!t1 !t2) return true;if (t1 t2) {return (t1-val t2-val) equal(t1-left, t2-left) equal(t1-right, t2-right);}return false;
}(5).特殊二叉树
#1.满二叉树 满二叉树中每一层结点数目都达到了最大比如下面这种 比如这样高度为k的满二叉树有 2 k 1 − 1 2^{k1}-1 2k1−1个结点在这里我采取根结点编号为1的策略有些地方可能采取根结点编号为0的策略但是这种情况下子结点不是很好找我们把所有结点依据从左到右从上到下按照层序依次编号的方式给每个结点分配一个编号: 为啥要考虑这个呢因为我们会发现根结点1的两个左右结点分别是2和3而2的两个结点是4和5所以说对于任意一个非叶结点编号为 k k k的结点它的两个子结点必存在并且编号为 2 k 和 2 k 1 2k和2k1 2k和2k1所以满二叉树可以在完全不浪费空间的情况下使用数组完成存储并且其编号的关系可以在不开出额外空间的情况下很轻松地存储结点的双亲结点和子结点的位置。
#2.完全二叉树 完全二叉树则是在满二叉树的基础上去除最后一层从最后一个结点开始的连续若干个结点比如 所以满二叉树也算完全二叉树对于具有 n ( n 0 ) n(n0) n(n0)个结点的完全二叉树其深度为 ⌊ log 2 n ⌋ \lfloor{\log_2n}\rfloor ⌊log2n⌋
(6).堆
#1.基本思想 堆基于完全二叉树来实现堆定义为如果树T中任一结点的值不小于(不大于)其左右结点的值则树T为一个堆如果根结点是所有结点中的最大值则这个堆称为大根堆否则如果是最小值则这个堆称为小根堆 这么做的思想其实很简单堆排序维护了一个基本有序的序列再每次插入/删除之后都能以 O ( log n ) O(\log n) O(logn)的时间复杂度代价上完成下一次维护因此堆排序的时间复杂度是 O ( n log n ) O(n\log n) O(nlogn)
#2.堆的基本操作 堆的基本操作主要是上浮和下沉两个流程上浮就是把结点放在最后的叶结点的位置然后把它逐渐上浮到合适的位置即可而下沉则是把新加入的结点放在根结点上其左右子树都是堆但是根结点本身不满足堆的性质所以我们逐渐操作把根结点下沉沉到符合条件的位置
i.上浮
void swap(int a, int b)
{int tmp{a};a b;b tmp;
}void siftup(vectorint a, int k)
{bool check{ false };while (k 1 !check) {if (a[k] a[k/2]) {swap(a[k/2], a[k]);k / 2;}else check true;}
}ii.下沉 下沉的流程要稍微复杂一点结点会首先和它的左右两个子结点进行比较先左后右直到有序/找到最后一个结点才停下来
void siftdown(vectorint a, int i)
{int n a.size() - 1;bool check{ false };int t{ 0 };while (i*2 n !check) {if (a[i] a[i*2]) t i*2;else t i;if (i*21 n) {if (a[t] a[i*21]) t i*21;}if (t ! i) {swap(a[i], a[t]);i t;}else check true;}
}iii.建堆
void buildHeap(vectorint a)
{int n a.size() - 1;for (int i n / 2; i 1; i--) {siftdown(a, i);}
}iv.插入元素
void addElement(vectorint a, int num)
{a.push_back(num);siftup(a, a.size()-1);
}v.删除元素
int deleteRoot(vectorint a)
{int tmp{ a[1] };a[1] a[a.size()-1];a.pop_back();siftdown(a, 1);return tmp;
}#3.堆排序 所以我们只需要每一次都从堆的根上拿出一个元素即可堆排序的流程非常简单
void heap_sort(vectorint a)
{vectorint ans;while (a.size() 1) {int val{ deleteRoot(a) };ans.push_back(val);}a ans;
}流程比较简单但是上面的代码并不能保证没有bug堆的这一部分思路比较简单因此我只提供一个思路
小结 这一篇我们比较粗略地介绍了一下二叉树相关的内容其实应该还有一个二叉搜索树的但是鉴于它的复杂度我决定把它放到下一篇树的应用中再来介绍
