二叉树创建方法

陈文

（福州职业技术学院，福州 350108）

0 引言

二叉树是《数据结构与算法》课程的重要内容，它是典型的树型数据结构[1]，二叉树的结构及二叉树的算法已广泛应用各类程序设计中[2-3]。分析研究二叉树的应用，首先要基于二叉树已经创建的前提下进行。因此，二叉树的创建则是一切二叉树算法应用的基础。然而，《数据结构与算法》的教材中，往往注重介绍二叉树的遍历方法及二叉树应用等，对二叉树的创建并未给出详细的分析。由于二叉树的遍历算法是基于二叉树已经创建的前提下，而本文所介绍的二叉树创建方法，却要用到二叉树的遍历等递归思想，因此，本文所介绍的二叉树创建方法是学完二叉树遍历等相关理论后，反过来进一步总结与分析二叉树的创建思想。它是对《数据结构与算法》教材的必要说明与补充。

本文着重介绍二叉树的创建方法，阐述二叉树创建的递归原理及二叉树创建的程序框架。并结合样例验证其正确性。同时，对学习二叉树的其他算法具有辅助作用。

1 直接递归创建二叉树

1.1 二叉树创建分析

以图1 所示的二叉树为例，二叉树的创建可用递归法创建。方法如图1。

图1 二叉树样例图

首先，创建根结点root，其值为a，再依次创建左子树及右子树。即输入序列如图2。

图2

二叉树的创建递归为根结点及左右子树的创建[4]。

为了使递归程序顺利执行，必须增加递归的出口条件。不妨以“#”字符表示为空结点作为出口条件，则二叉树可形象表示为图3。……