二叉树遍历求解问题

《二叉树遍历求解问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、邮箱：CALF-LOVE@qq.com。有什么问题，可以大家一起讨论！二叉树的遍历首先得明白二叉树的遍历方式：参照百科里的定义：1．中序遍历的递归算法定义：　　若二叉树非空，则依次执行如下操作：　　(1)遍历左子树；　　(2)访问根结点；　　(3)遍历右子树。　　2．先序遍历的递归算法定义：　　若二叉树非空，则依次执行如下操作：　　(1)访问根结点；　　(2)遍历左子树；　　(3)遍历右子树。　　3．后序遍历得递归算法定义：　　若二叉树非空，则依次执行如下操作：　　(1)遍历左子树；　　(2)遍历右子树；　　(3)访问根结点

2、。简言之：前序：根左右　　　　中序：左根右　　后序：左右根举三个例子：例一：已知前序和中序，求后序？前序：abdgcefh中序：dgbaechf后序：？前序：根左右　　　　中序：左根右　　后序：左右根求解：根据各种遍历的方式，我们知道，中序中间的那一个一定会是根结点,前序中第一个是根结点a这样，通过比较，我们就把树以根结点分成两部分(dgb和echf)。再通过这种方式，我们就把剩下来的树找出来了。由bdg(前)和dgb(中)知b为此子树的根结点，由dg不变，再由先左后右，知d再为根结点，g为d的右子树。由cefh(前)和ec

3、hf(中)知e为此子树的根结点，c为e的左子树，fh为e的右子树。因为fh(前)和hf(中)不同，再由先左后右，知f为根，h为此子树的左结点。所有后序结果为：gdbehfca　　　aabdgechfbcdefgh邮箱：CALF-LOVE@qq.com。有什么问题，可以大家一起讨论！例二：已知后序和中序，求前序？后序：dabec中序：debac前序：？后序：左右根　　　中序：左根右　　前序：根左右求解：由后序遍历知，根结点为c，由中序遍历知，此树只有一根左子树。根据后序遍历的和中序遍历的定义，知d为最左的一个子树。由abe(后

4、)和eba(中)知e为此左子树的根结点，ba为根结点e下的右子树，则d为根结点e下的左子树。由ab(后)和ba(中)知a为以b为根结点的右子树。cccabeeedbadba例三：已知前序和后序，求中序？前序：bdg后序：gdb中序：？前序：根左右　　后序：左右根　　　中序：左根右求解：因为前序和后序的遍历方式比较特别，其中不能区分左子树和右子树，这样就会产生许多情况。对于此题，可以得到四种图：bbbbddddgggg这样得到的中序遍历就有：gdb、dgb、bgd、bdg四种情况。综上所述，二叉树的遍历求解问题，我们首先求出根

5、结点，再对剩下的结点分类。分好类之后，它们依然是一棵树。这样，再根据前面的方法，依次进行，直到分类的结果里只有一个结点。树的遍历的方式各有特点，根据它们的特点，求出我们所需要的结果，这要求我们熟练掌握各种遍历的定义。