浙江 网站备案,花店网站开发参考文献,苏州的建筑公司网站,烟台网站制作这文章目录 9.树(1).树的基本概念#1.基本定义#2.树的广义表表示法#3.基本术语 (2).树的存储结构#1.标准形式(常用)#2.逆存储形式#3.孩子兄弟存储法 (3).并查集#1.我们到底想解决什么问题#2.并查集结点#2.Find(查)#3.Union(并)#4.例子 (4).树的遍历#1.前序遍历#2.后序遍历#3.遍历的… 文章目录 9.树(1).树的基本概念#1.基本定义#2.树的广义表表示法#3.基本术语 (2).树的存储结构#1.标准形式(常用)#2.逆存储形式#3.孩子兄弟存储法 (3).并查集#1.我们到底想解决什么问题#2.并查集结点#2.Find(查)#3.Union(并)#4.例子 (4).树的遍历#1.前序遍历#2.后序遍历#3.遍历的非递归实现i.非递归前序遍历ii.非递归后序遍历 #4.层序遍历 (5).树的线性表示#1.双亲表示法#2.层号表示法 小结 9.树 接下来我们就要走出一对一的线性结构来研究一下一对多的树形结构了树的结构其实非常常见比如我们在对文件分类的时候同一个目录下有多个文件、目录而子目录下还有更多文件这就是一个比较典型的一对多关系。
(1).树的基本概念
#1.基本定义 树是由 n ( n ≥ 0 ) n(n\ge0) n(n≥0)个结点组成的有限集T它或为空树( n 0 n0 n0)或为非空树。对于非空树T它满足以下两个条件
1.有一个特定的结点称之为根结点(root) 除根结点以外其余的结点分成 m ( m 0 ) m(m0) m(m0)个互不相交的有限集 T 0 , T 1 , T 2 , . . . , T m − 1 T_0, T_1, T_2,..., T_{m-1} T0,T1,T2,...,Tm−1其中每个集合都是一棵树称为根结点的子树 也就是说树的定义本身是一个递归定义例如下图 其中A是根结点BC和D分别构成了三棵子树你可以依次递归地判断下去直到遇到一棵空树
#2.树的广义表表示法 例如对于上面这棵树我们可以表示为A(B(E, F), C, D(G(H)))字母后接的括号内包含该结点所有的子结点
#3.基本术语
结点树中的每个独立单元结点的度(次数)一个结点的子树的个数称为结点的度类比图中结点的出度/入度叶子结点度为0的结点称为叶子结点他没有子树分支结点度不为0的结点m次完全树假设树T是一棵m次数如果T中非叶子结点的次数都为m则称树T为一棵m次完全树双亲结点和子结点结点的子树的根结点称为该结点的子结点而该结点也称为子树根结点的双亲结点父结点兄弟结点如果结点k有两个或两个以上子结点则结点k的所有子结点互为兄弟结点路径对于树种的任意两个不同的结点 k i k_i ki和 k j k_j kj如果 k i k_i ki出发能够“自上而下地”通过树种的结点到达结点 k j k_j kj则称 k i k_i ki到 k j k_j kj存在一条路径路径长度路径中所包含的边的数量称为路径长度路径的长度等于这条路径上的结点个数-1结点的祖先如果从结点 k i 0 k_{i_0} ki0到结点 k i n k_{i_n} kin有路径 ( k i 0 , k i 1 , . . . , k i n ) (k_{i_0}, k_{i_1}, ..., k_{i_n}) (ki0,ki1,...,kin)则称 k i 0 , k i 1 , . . . , k i n − 1 k_{i_0}, k_{i_1},..., k_{i_{n-1}} ki0,ki1,...,kin−1都是结点 k i n k_{i_n} kin的祖先结点的后代结点 k i 1 , k i 2 , . . . , k i n k_{i_1},k_{i_2},...,k_{i_n} ki1,ki2,...,kin都是结点 k i 0 k_{i_0} ki0的后代结点的层次将根的层次定义为0其余结点所在的层次都等于其父结点的层次1一般也有将根结点层次定义为1的空树的层次则为0这里采取ECNU数据结构课中给出的定义高度(深度)树中层次最大的结点的层次称为树的深度 我们再拿这张图举个例子 k 0 k_0 k0的层次是0 k 1 , k 4 , k 5 k_1, k_4, k_5 k1,k4,k5的层次是1以此类推并且该树的深度为3
有序树如果给定的m次树结点的各子树从左到右是有次序不可交换的那么称该树为有序树 例如在这里我们就使用了一棵有序树来表示 ( A B ) × 5 ÷ ( 2 × ( C − D ) ) (AB)\times5\div(2\times(C-D)) (AB)×5÷(2×(C−D))的值有趣的是如果你已经提前了解了二叉树的前、中、后序遍历之后你就会发现表达式树的前、中、后序遍历得到的序列正是前缀、中缀、后缀表达式比如我们用后序遍历可以得到: A B 5 ∗ 2 C D − ∗ / AB5*2CD-*/ AB5∗2CD−∗/是不是还挺神奇的之后我们会再讲到树的遍历
森林 m ( m ≥ 0 ) m(m\ge0) m(m≥0)棵互不相交的树的集合
(2).树的存储结构 说了这么多接下来我们应该看看怎么把一棵树存储起来了不过因为树是非线性结构我们必须采取一些措施把它映射到一个线性的结构上去否则我们就没有办法存储了。
#1.标准形式(常用) 我们采取如下的结构体来存储树中的结点
struct TreeNode
{int val;TreeNode* child[MAXN];
};很简单的结构首先存储自己结点的值然后存储所有子结点的指针以便于找到所有的子结点它的存储结构图如下 还是比较好理解的对吧这里向上的小箭头代表空指针意味着存储空间的此位不存在子结点不过这样的结构很有可能造成比较严重的空间浪费因此在C中我们可以采取vector来替代原生数组
struct TreeNode
{int val;vectorTreeNode* child;
};同理能够更好利用零散空间的链式存储也比较适合这种场景我们可以把存储子结点的存储结构换成链表例如
struct TreeNode
{int val;listTreeNode* child;
};带有vector的在C语言中不好实现但是使用链表的实现起来就没有那么复杂了不过这二者对于我们来说不会有很大的差异因为后续的操作多数都是要对整个包含子结点的存储结构进行遍历的因此我们可能不太需要随机访问。 这种存储结构对于双亲找子的过程非常方便我们只要知道一个结点就可以很轻松地找到它的所有子结点但是如果我们知道了一个结点希望找到它的双亲结点在这种存储方式之下就不是很容易了这个问题其实看起来就和链表的某个结点希望找到其上一个结点一样如果我们不额外耗费一点空间那肯定是需要耗费更多的时间来完成这件事的
#2.逆存储形式 我们把每个结点都存自己的子结点的过程逆转一下每个结点都存自己的双亲结点结构体变成这样
struct TreeNode
{int val;TreeNode* parent;
};这样就可以非常容易地找到自己的双亲结点了它的存储形式是这样 但是这样一来想找到自己的子结点又变得困难了起来所以怎么办呢这还不好办就像链表为了快速找到前后结点一样我们设置一个双向的结点就可以了
struct TreeNode
{int val;TreeNode* parent;vectorTreeNode* child;
};这就完美了虽然每个结点占用的空间可能比较大但是至少我们在时间上有了很大的优化无论是找子结点还是找双亲结点都可以直接通过指针跳转了
#3.孩子兄弟存储法 这回我们就不存全部的结点了我们每个结构体中只存储两个结点的指针自己的第一个子结点以及自己右边的第一个兄弟结点结构体定义如下
struct TreeNode
{int val;TreeNode* firstChild;TreeNode* nextSibling;
};这种存储方式的好处是我们可以很好地解决上面几种存储方法空间消耗很大的问题同时我们把多叉树通过这种方式转换成了二叉树我们对于二叉树的一些操作对于这种存储方式的多叉树也是可以使用的
(3).并查集
#1.我们到底想解决什么问题 我们怎么表示一个集合呢其实用什么都行比如我上学期C课上写过一个用数组实现的集合
class integerSet
{
private:int* arr;size_t _size;size_t _capacity;
public:static constexpr size_t npos -1;struct bad_integerSet : public std::exception{bad_integerSet() default;const char* what() const throw (){return bad_integerSet;}};
public:integerSet() delete;integerSet(size_t size): arr(new int[size1] {0}), _size(0), _capacity(size) {}integerSet(const integerSet s1);integerSet(integerSet s1) noexcept;~integerSet();size_t find(int elem) const;void insert(int elem);integerSet setunion(const integerSet s1) const;integerSet setdifference(const integerSet s1) const;integerSet setintsection(const integerSet s1) const;integerSet setsymmetricdifference(const integerSet s1) const;integerSet operator(const integerSet s1);int operator[](size_t _index);bool operator(const integerSet s1) const;size_t size() const;size_t capacity() const;bool isSubset(const integerSet s1) const;bool isMember(int m) const;bool isEmpty() const;void clear();void erase(int elem);
};它的实现你倒是确实可以试一试不是很困难不过如果你的集合无序有一些操作做起来会比较困难所以C的STL中提供的集合是基于红黑树(set)/哈希表(unordered_set) 实现的但是这样就有点麻烦了 我们接下来要考虑的问题是比较简单的假设说我们的一个数组中存在很多个集合并且这些集合之间不存在交集也就是说这些集合一起构成了这个数组的划分我们如何在更快的时间内表示出其中每一个元素的集合所属关系呢要明确的一点是在我们当前研究的集合中元素a在集合A中元素b在集合B中如果元素b也在集合A中那么集合A和集合B是一个集合也就是说一旦在两个集合中出现同一个元素那么这两个集合就可以直接合并那我们是不是可以用树来表达这个结构呢 例如对于三个集合{0, 6, 7, 8}, {1, 4, 9}, {2, 3, 5}假设我们把第一个元素作为根那么就有 哇哦我们用双亲存储法构建这棵树就可以把一个集合描述出来那么如果 S 1 S_1 S1中的结点4正好也属于 S 0 S_0 S0呢就比如下面这样 这种情况下出现了多对一的结构那么理论上讲我们用树就不能描述了可能需要用到图的结构但是我们好像忘了点什么事情 在我们当前研究的集合中元素a在集合A中元素b在集合B中如果元素b也在集合A中那么集合A和集合B是一个集合 既然4是 S 0 S_0 S0和 S 1 S_1 S1共有的元素那么集合 S 0 S_0 S0和集合 S 1 S_1 S1应当是一个集合所以我们直接把 S 1 S_1 S1的根合并到 S 0 S_0 S0去形成一个更大的集合这样就可以把这些数据全都加到同一个集合里面去了 在这种集合中我们怎么判定两个元素是否属于同一个集合呢这个也简单因为每个结点都可以找到自己的双亲结点所以我们只要一直判断到根结点看看两个元素是不是能够找到同一个根结点即可 所以综上我们的集合只需要两个操作Union(并) 和Find(查) 两个操作即可我们研究的这一类集合也就叫做并查集
#2.并查集结点 并查集的每个结点要怎么存呢其实比较简单对于一个数组下标是它的值数组内对应的数字是它的双亲结点而对于根结点可以存一个负数表示整个根结点下有多少个结点也可以存自己的下标这意味着如果找到下标和存储值相同的就已经找到根了 所以在这里我们采用前者前者对于一些问题的解决来说非常方便比如找出朋友圈中人数最多的朋友圈的数量需要注意的是如果我们采取前者在初始化的时候就需要我们把数组每一个元素对应的值都改成-1这样每一个元素都是自己的根对于后续我们的操作会非常方便
#2.Find(查) 先说查是因为并操作也需要先依赖于查操作所以我们可以给出如下代码
int find(vectorint dsu, int x)
{if (dsu[x] 0) {return x;}return find(dsu, dsu[x]);
}非常简单的函数如果找到一个值小于0的就直接返回如果不是则继续向着根找直到找到一个小于0的就结束了这样是不是很简单呢判断两个元素是不是在一个集合里的操作就是这么简单
#3.Union(并) 然后就是并在这里我们采取一个简单策略如果x和y需要合并那就直接把y对应的整棵树合并到x上面去代码如下
int Union(vectorint dsu, int x, int y)
{int fx{ find(dsu, x) }, fy{ find(dsu, y) };if (fx ! fy) {dsu[fx] dsu[fy];dsu[fy] fx; }return fx;
}我们首先找到两个结点对应的根如果两个对应相同的根就不需要合并但如果是不同的根我们直接把y对应的整棵树都合并进x对应的树所以在这里只要让fy指向fx把fx的值加上fy的值即可
#4.例子 就是这样并查集的代码加起来20行不到就可以实现我们需要的功能了所以来看看这个例子 这里我直接给代码了
#include iostream
#include vector
using namespace std;int find(vectorint circle, int x)
{if (circle[x] 0) {return x;}else {return circle[x] find(circle, circle[x]);}
}int Union(vectorint circle, int rootX, int rootY)
{int fx{ find(circle, rootX) }, fy{ find(circle, rootY) };if (fx ! fy) {circle[fx] circle[fy];circle[fy] fx; }return fx;
}int main()
{int N{ 0 }, M{ 0 };cin N M;vectorint circle(N 3, -1);for (int i 0; i M; i) {int cnt{ 0 }, root{ 0 }, in{ 0 };cin cnt;for (int j 0; j cnt; j) {cin in;if (j 0) {root in;}else if (in ! root) {int rt{ find(circle, in) };if (root ! rt) {root Union(circle, rt, root);}}}}int min_val{ 0 };for (auto i : circle) {if (i min_val) min_val i;}cout -min_val endl;return 0;
}return circle[x] find(circle, circle[x]);这里利用了一个压缩存储的特性如果一个元素找到的不是整棵树的根那就把它合并到根上去这样可以让一棵树变得更 “扁”从而提高并查集的查找效率。
(4).树的遍历 我们约定遍历树的时候总是从左到右例如 其中橙色箭头是向前的过程蓝色箭头是回溯的过程我们一直向左找到最左如果没有子结点了就开始回溯就这样一直搜索直到最终回到根结点上这样的过程实际上是深度优先搜索(Depth-First Search) 的搜索模式接下来我们就来看看怎么实现对于树的遍历 你有没有觉得这个问题用递归好像很好解决呢
#1.前序遍历 首先是前序遍历又称先序遍历即每次遇到一个结点首先把结点本身的值打印出来然后再打印子结点的值所以我们可以很轻松地写出递归版本的前序遍历代码
void PreOrderTraversal(const TreeNode* root)
{if (!root) {cout root-val ;for (const auto child : root) {PreOrderTraversal(child);}}
}这就结束了这就结束了因为树的定义本身是递归的所以每一个子结点都可以对应一颗子树而子树的遍历流程跟双亲结点一模一样所以我们可以用一个非常非常简单的递归函数完成前序遍历的流程
#2.后序遍历 后序遍历就是在所有的子结点打印完再打印本身的值所以体现到代码上就是
void PreOrderTraversal(const TreeNode* root)
{if (!root) {for (const auto child : root) {PreOrderTraversal(child);}cout root-val ;}
}这俩真是一个比一个简单后序遍历只是打印顺序有差异所以我们只需要把cout打印放到递归的后面就实现了这多简单啊对吧
#3.遍历的非递归实现 那么有一些很讨厌的题目要求你用非递归的方式去实现一遍前序和后序遍历这当然是可以做的这就需要我们用一个栈去手动模拟递归遍历树的流程了
i.非递归前序遍历
void NoRecursionPreOrderTraversal(const TreeNode* root)
{stackconst TreeNode* st;st.push(root);while (!st.empty()) {const TreeNode* ptr{ st.top() };st.pop();cout ptr-val ;for (int j ptr-child.size() - 1; j 0; j--) {st.push(ptr-child[j]); // 我们需要倒过来入栈才能保证后面遍历顺序正确}}
}那么对于下面这棵树我们就很容易得到它的正确遍历结果了0 1 4 5 6 2 3 7 8 9你可以自己用这段代码试试看
ii.非递归后序遍历
void NoRecursionPostOrderTraversal(const TreeNode* root, int _Msize)
{stackconst TreeNode* st;vectorint mark(_Msize * 2, 0);st.push(root);mark[0] 0;while (!st.empty()){const TreeNode* ptr{ st.top() };if (mark[st.size() - 1] 0 !ptr-child.empty()){mark[st.size() - 1] 1;for (int j ptr-child.size() - 1; j 0; j--){if (!ptr-child.empty()){st.push(ptr-child[j]);mark[st.size() - 1] 0;}}}if (st.top()-child.empty() || mark[st.size() - 1] 1) {cout st.top()-val ;st.pop();}}
}后序遍历则要复杂的多参数部分我们还要传入树的结点个数以便mark数组正常工作这里我不做过多解释这一部分可以选择性学习。
#4.层序遍历 层序遍历就是如同下图的树我们从根结点开始一层一层打印出来比如这里的层序遍历结果应该就是0 1 2 3 4 5 6 7 8 9 所以怎么写呢我们发现这个东西有点像广度优先搜索(Breath-First Search)所以我们需要采用队列来实现层序遍历
void LevelOrderTraversal(const TreeNode* root)
{queueconst TreeNode* qt;qt.push(root);while (!qt.empty()) {const TreeNode* ptr{ qt.front() };qt.pop();for (const auto c : ptr-child) {qt.push(c);}cout ptr-val ;}
}非常简单我们每次取出队首元素之后把这个结点的所有子结点全都入队然后把它打印出来即可。
(5).树的线性表示
#1.双亲表示法 双亲表示法是比较简单的表示比如我们有 n n n个结点我们依次给出这 n n n个结点的双亲结点的编号(如果是根节点双亲结点的编号为-1)然后我们需要还原出这棵树来怎么做呢 如果你比较厉害实际上双亲表示法已经足够你做完树的各种操作了在这里我们只是简单完成一下从双亲表示法到标准存储的转换理论上讲我们可以在 O ( n ) O(n) O(n)的时间复杂度内完成这个过程想法很简单我们首先新建这 n n n个结点并把它们存储起来然后去遍历存储了双亲编号的数组然后把它们添加到对应结点的child数组里面去即可所以我们可以很快写出下面的代码
TreeNode* buildTree(const vectorint parents)
{size_t n{ parents.size() };vectorTreeNode* nodes;TreeNode* root{ nullptr };for (int i 0; i n; i) {nodes.push_back(new TreeNode{ i, vectorTreeNode*{} });}for (int i 0; i n; i) {if (parents[i] ! -1) {nodes[parents[i]]-child.push_back(nodes[i]);}else root nodes[i];}return root;
}所以就是这样我们把某个子结点直接链接到对应的双亲结点上去即可。
#2.层号表示法 我们根据树的前序遍历顺序依次给出结点的值以及其所在的层号然后据此建立一棵树比如(0,A) (1,B) (2,D) (2,E) (1,C)是一棵二叉树还原的方法其实并不困难如果层号比上一个结点层号大一个则说明这个结点是上一个结点的子结点如果比上一个结点小则说明回到了已记录结点的某一层的另一棵子树上所以我们可以写出以下代码
struct TreeNode
{TreeNode* parent;char c;vectorTreeNode* child;
};struct LevelTreeNode
{int level;char c;
};void buildTree(vectorTreeNode* nodes, const vectorLevelTreeNode* lnodes)
{int current_level{ 1 }; // 用current_level记录当前层号nodes[0]-c lnodes[0]-c; // 前序遍历的第一个结点一定是根TreeNode* last_root{ nodes[0] }; // 记录上一层的根结点for (int i 1; i lnodes.size(); i) {if (lnodes[i]-level ! current_level) { // 仅在不同层的时候需要特殊处理if (lnodes[i]-level current_level) { // 如果层号变大说明所有后续结点都是子结点last_root *(last_root-child.begin() last_root-child.size() - 1); // 找到上一个根结点的双亲结点最后的子结点(其实就是当前遍历到结点对应的根)current_level lnodes[i]-level; // 层号变更}else {int dif{ current_level - lnodes[i]-level }; // 如果层号变小则开始回溯while (dif ! 0) { // 回溯到同一层last_root last_root-parent;dif--;} current_level lnodes[i]-level;}}// 标准建树操作nodes[i]-parent last_root;nodes[i]-c lnodes[i]-c;last_root-child.push_back(nodes[i]);}
}nodes是对应所有结点的vector这里只是用来保存各个结点的信息而lnodes则是一个包含层号的结点vector它内部还包含了前序遍历的顺序 在这里我们采取了一个辅助手段——保存结点的双亲结点我们前面已经很轻松地解决了双亲结点建树的问题所以只要我们能够根据层号和前序遍历顺序还原出双亲的对应关系我们就可以很轻松地把这个问题解决了。
小结 这一篇中我们比较详细地介绍了关于树的一些内容不过树的内容还远不止这些未来的两篇分别是二叉树和树的应用敬请期待。
