济南智能网站建设咨询电话_三秦网_小程序排名优化_网络营销公司网络推广

目录

二叉树的遍历

 树和森林

树和森林的遍历

---

二叉树的遍历

二叉树的遍历分为先序、中序、后序遍历，层序遍历。这里的先、中、后是指遍历根的顺序。

先序遍历顺序：根，左子树，右子树

中序遍历顺序：左子树，根，右子树

后序遍历顺序：左子树，右子树，根

先、中、后序遍历的时间复杂度未O(n)，空间复杂度也为O(n)。n是指结点数量。

层序遍历是按照从上往下，从左往右的顺序，一层一层地遍历树中的结点。

void preOrder(BiTree root){if(root==NULL) return;else {
printf(“%c”,root->data);  /*访问根结点*/
preOrder(root->lchild);  /*先序遍历左子树*/
preOrder(root->rchild);  /*先序遍历右子树*/} /*if*/
} /*preOrder*/

 树和森林

使用孩子兄弟表示法，可以表示树和森林。

孩子兄弟表示法：是一种链表表示法，链表中每个结点有2个指针域。分别指向当前节点的第1个孩子，以及下一个兄弟结点。

树和森林可以通过孩子兄弟表示法实现与二叉树的相互转换。

表示森林时，根节点的右节点接另一颗树的根节点。

树和森林的遍历

不确定书中描述是否有误，下文按个人理解所写。

树和森林都只有先序遍历、后序遍历两种方式。（没有中序遍历，因为树、森林的子树数量不定，无法判断根结点怎样算放在中间进行遍历的） 与二叉树的先序遍历、后序遍历类似。

树的先序遍历：先访问根结点，然后依次先序遍历各子树。

树的后序遍历：后根遍历各子树，然后访问树根结点。

森林先序遍历：先序遍历第1颗树，然后先序遍历除第1颗树之外的森林。

森林后序遍历：后序遍历第1颗树，然后后序遍历除第1颗树之外的森林。