说起树，大多数人的第一反应就是二叉树及其亲戚，包括红黑树和平衡二叉树。但实际上，除了二叉树之外，普通的树结构在数据结构中也占有非常重要的部分。不仅如此，正所谓百川成海，白木成林。既然有了树结构，自然就会有对应的森林结构。因此，本文将从普通的树结构开始，讨论和介绍关于树和森林的那些事。1树的定义树实际上是很多节点的集合，只是每个节点的组成是按照树的结构来划分的。下图可以定义一个常见的树结构。再说一遍，树的结构就像一棵倒过来的树，节点的组成是有层次的。一棵树由子树组成，子树又由更小的子树组成。树的亲属关系至多只与树中的一个节点有直接关系，而与下层的多个节点有直接关系。上层的节点称为父节点，下一层的节点称为子节点。树底部没有子节点的所有节点都称为叶节点。具有相同父节点的节点是兄弟节点。树家族等级制度树是一个等级制度非常严格的大家族。树中一个节点的子树的个数称为该节点的度。所以叶子节点是度为0的节点。度不为0的节点称为内部节点。每个节点都有自己的级别，级别从高到低递增，根节点为第一级，根的子节点为第二级，以此类推。一棵树的最大层数称为树的高度（或深度）。2.树的存储结构由于普通树结构不像二叉树那样规则，可能是多叉树的组合，所以很难用常规的线性结构来存储。因此，树结构的存储需要将树族中的关系分开存储，保存各个节点之间的关系，依次还原出整个树结构。这好比一个家庭的家谱，记录着我们与父母、兄弟姐妹的关系。对于树，根据存储关系的不同，可以分为三种存储方式：父表示、子表示和子兄弟表示。ParentalRepresentation树的parentalrepresentation很明显就是通过记录每个节点的父节点来存储整棵树的层次关系。这里常用的一种存储结构是数组。将树的节点存储在连续的地址中，同时对应其父节点在数组中的序号，这样就可以保存所有节点的父节点信息。parent表示直接存储节点的父位置（对应数组的下标），所以很方便找到一个节点的父节点和祖先节点。但是无法直接获取节点的子节点的位置。如果需要查找指定节点的子节点和后代节点，需要遍历整个数组，进行多次判断。父表示子表示树的缺点很明显，所以最直接的解决办法就是简单的保存子节点。更不用说，childrepresentation就是这样的representation。但是，相对于父节点的存储，存储子节点需要考虑一个问题，即一个节点至多有一个父节点，但其子节点可能有多个。如果每个子节点都存储在一个数组中，这样的做法不是明智的选择，也没有必要。因此，在使用childnotation来存储树的结构时，往往会采用数组+链表的结构。这种结构很常见吗？与解决哈希冲突的链地址法意义相同。在这样的链式结构中，用指针来表示节点的每个子节点，每个子节点的位置通过链表依次连接起来，很方便找到每个节点的后代。但是问题还是一样，如果要找出某个节点的双亲，还需要遍历所有链表。不过，既然亲子双方都发表了自己的意见，那么简单的合并在一起，岂不是可以相得益彰，共进退？所谓父子表示法，就是将父表示和子表示结合起来。这样既能满足父母的寻找，也能满足孩子的寻找。子兄弟表示已经足以将数据信息存储在具有父子表示的树中。为什么我们需要一个子兄弟方法？事实上，子弟表示是一种非常有趣、非常有用的值表示。在子兄弟符号中，我们同意只存储每个节点的第一个孩子和下一个兄弟节点。不仅如此，节点的存储是通过链表进行的。字不清楚，还是看图吧。看起来有点怪异的形状，每个节点作为链表的一个节点，两个指针分别指向第一个子节点和下一个兄弟节点。为了不让大家一头雾水，我举个例子。以节点B为例，它的第一个子节点是E，它的下一个兄弟节点是和它同级的C。因此，节点B的两个指针分别指向E和C。小弟的表现力似乎很弱，但是如果我们调整一下右边的图，就可以看出其中的异样。看到没有，小弟表示其实就是把一棵普通的树转化成二叉树的形式。那么二叉树为什么这么重要，因为一切都离不开它。看到这里其实揭示了树和二叉树的转换关系，二叉树上的很多性质和操作也可以用在普通的树结构中。3树遍历学过二叉树的同学一定对前序遍历、中序遍历、后序遍历、中序遍历不陌生。不管是迭代还是非迭代的写法，都太基础了。某物。对于普通的树，由于每个节点的子树个数不是常数，所以不容易指定前序、中序、后序的顺序。因此，一般来说，遍历树有两种方式。根据遍历根节点的先后顺序，可以分为先根遍历和后根遍历。树的根优先遍历是先访问树的根节点，然后依次遍历根节点的每个子树。如此递归。在将一棵普通树转换成对应的二叉树时（小弟记法），其实就相当于先序遍历。不用说，树的后根遍历与先根遍历相反，先访问根节点的每个子树，再访问根节点。树的后根遍历相当于转换后的二叉树的中序遍历。如果你不相信我，试试看。4树、森林和二叉树的相互转换写到这里，突然发现忘记介绍什么是森林了。其实森林的概念很简单，就是很多棵树。对，就是这样。树、森林和二叉树本质上是相似的结构，因此可以相互转化。任何森林或树都可以表示为二叉树，任何二叉树也可以对应森林或树。树转化为二叉树，我们前面介绍过，就是通过树的子兄弟表示。当用子兄弟法表示时，每棵树都可以用唯一的二叉树来表示。但是转换后的二叉树有一个非常显着的特点。仔细观察。显然，这不是一棵平衡二叉树。而且，根节点没有右子树，我敢肯定。这是因为根节点没有兄弟节点，只有子节点，所以转换成二叉树后，肯定没有右子树。不过，这样的缺点在森林里是可以弥补的。由于森林中有很多树，所以可以使用其他树作为右子树。具体实现步骤是先将森林中的每棵树都转换为二叉树，然后将第一棵树的根节点作为转换后的二叉树的根节点。第一棵树的左子树作为转换后二叉树根节点的左子树，第二棵树作为转换后二叉树的右子树。第三棵树作为转换后的二叉树根节点右子树的右子树。等等。让我们举个例子。这里是三棵树的森林。上述三棵树转化为二叉树的形式如下。然后将绿色二叉树作为蓝色二叉树根节点的右子树，将黄色二叉树作为绿色二叉树根节点的右子树，得到森林转化为二叉树的结果树。根据以上规则，二叉树也可以转化为树和森林。5总结在数据结构中，树和森林估计不是很流行的结构，甚至很多工作多年的老coder都没有用过。在写这篇文章的时候，我也在思考树木和森林的实际用途。看来最重要的部分就是将一棵普通树转化为二叉树进行处理。但我想这就是它的价值。在很多实际场景中，数据之间的关系可能并不能直接通过二叉树来表示和存储，一开始可能需要通过多叉树或者各种畸形树结构来定义关系。这样的树肯定不适合快速处理和访问，所以往往需要将这些奇形怪状的树转化为规则的二叉树，以便进一步处理。最后，为了回归到具体的应用，还需要将二叉树分解成原来的树或森林结构，从而获得应用意义。一般来说，存在就是真理。不怕不会用，就怕想不到。本文转载自微信公众号“业余码农”，可通过以下二维码关注。转载本文请联系业余码农公众号。
