1、由二叉树的前(先)序序列和中序序列建立该二叉树
分析:若二叉树的任意两个结点的值都不相同,则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外,由前序序列和中序序列的定义可知,前序序列中第一个结点必为根结点,而在中序序列中,根结点刚好是左、右子树的分界点,因此,可按如下方法建立二叉树:
1. 用前序序列的第一个结点作为根结点;
2. 在中序序列中查找根结点的位置,并以此为界将中序序列划分为左、右两个序列(左、右子树);
3. 根据左、右子树的中序序列中的结点个数,将前序序列去掉根结点后的序列划分为左、右两个序列,它们分别是左、右子树的前序序列;
4. 对左、右子树的前序序列和中序序列递归地实施同样方法,直到所得左、右子树为空。
假设前序序列为ABDGHCEFI,中序序列为GDHBAECIF,则得到的二叉树如下页所示
2、由后序序列和中序序列构造二叉树
根据定义,后序序列的最后一个结点,与先序序列的第一个结点一样,可将中序序列分成两个子序列,分别为这个结点的左子树的中序序列和右子树的中序序列,再取出后序序列的倒数第二个结点,并继续分割中序序列,如此递归下去,当倒着取尽后序序列中的所有结点后,便可构造一棵二叉树。
评论