|
|
|
建立二叉树的方法有很多，如：按完全二叉树的形式输入字符序列，其中空格表示相应的子树为空。
|
|
|
|
近年来，在程序员考试中经常出现的二叉树建立为：已知二叉树的后序序列和中序序列或已知二叉树的前序序列和中序序列，要求考生确定一棵二叉树。
|
|
|
|
例如，一棵二叉树的中序序列和后序序列分别是DCBAEFG和DCBGFEA，请给出该二叉树的前序序列。该题可通过后序遍历确定二叉树的根结点，然后找到该数据值在前序序列中的位置，并用该位置的左部序列和后序序列中的相应序列构造左子树，用该位置的右部序列和后序序列中的相应序列构造右子树，如此不断地递归构造即可得到二叉树。建立的二叉树如下图所示。
|
|
|
|
|
|
|
|
而且，该题还可以引申到要考生证明已知二叉树的前序序列和中序序列，可唯一确定一棵二叉树；或要求考生针对已知二叉树的前序序列和中序序列，写出建立一棵二叉树的算法等。同时，要求考生证明已知二叉树的前序序列和后序序列，不能唯一确定一棵二叉树。
|
|
|
|
当然还可以通过给定的广义表建立二叉树等。可见，建立二叉树的方法很多，只要考生掌握了二叉树递归定义的本质和输入形式就可以方便地建立二叉树。
|
|
|
