一棵二叉树是如何进行后根遍历的?
发布网友
发布时间：2023-09-01 11:23
共1个回答
热心网友
时间：2024-08-06 02:17
一棵树的后根遍历与这棵树所对应的二叉树的中序遍历相同。因为树转化为二叉树后是没有右子树的，所以最后访问的是树的根结点。
给定一棵树，可以找到唯一一棵二叉树与之对应，同样，森林也与一棵树存在一一对应关系。树与二叉树，森林与二叉树的转化（a）（b）（c）为三棵树，并构成一个森林，（d）（e）（f）分别为（a）（b）（c）对应的二叉树，（g）为森林对应的二叉树。
树结构有两种次序遍历树的方法：
1、先根遍历：先访问树的根节点，再依次先根遍历子树；
2、后根遍历：先依次后根遍历子树，再访问树的根节点。
因为树并不一定是二叉树，‘中’的概念不好定义，比如对于一个拥有3个子树的根节点来说，根节点除了先根和后根两种遍历方式之外还有另外两种次序。
如一种次序是先遍历根节点的第一棵子树，再访问根节点，之后再依次遍历剩余子树，另一种次序是，先遍历根节点的前两棵子树，再访问根节点，最后访问第三棵子树。对于拥有更多子树的根节点来说，依次遍历的方法更多。
扩展资料：
当对一棵数学表达式树进行中序，前序和后序遍历时，就分别得到表达式的中缀、前缀和后缀形式。中缀（infix）形式即平时所书写的数学表达式形式，在这种形式中，每个二元操作符（也就是有两个操作数的操作符）出现在左操作数之后，右操作数之前。
在使用中缀形式时，可能会产生一些歧义。例如，x+y ×z可以理解为(x+y) ×z或x+ (y ×z)。为了避免这种歧义，可对操作符赋于优先级并采用优先级规则来分析中缀表达式。
在完全括号化的中缀表达式中，每个操作符和相应的操作数都用一对括号括起来。更甚者把操作符的每个操作数也都用一对括号括起来。如( (x) + (y) )，( (x) + ( (y) * (z) ) )和( ( (x) + (y) ) * ( (y) + (z) ) ) * (w)。
参考资料来源：百度百科-中序遍历
参考资料来源：百度百科-二叉树
