|
|
|
|
二叉树运算是数据结构的重要内容，为加深对二叉树内容的理解，这里给出一些应用实例。为方便描述，二叉树的顺序存储结构用一维数组R表示，而二叉链表的节点存储结构定义如下：
|
|
|
|
|
|
（1）以二叉链表为存储结构，写一个算法用括号形式（key, LT, RT）打印二叉树，其中key是根节点数据，LT和RT分别是括号形式的左右子树。并且要求：空树不打印任何信息，一个节点x的树打印形式是x，而不应是（X,）的形式。相应的算法如下：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
将已知二叉树改建为中序线序树算法的主要思路是：对二叉树进行中序遍历，若当前被访问节点的左子节点指针为空，则让它指向当前节点的前驱节点；若其前驱节点的右子节点指针为空，则让它指向当前节点。相应的算法如下：
|
|
|
|
|
|
|
|
|
|
|
|
