6.2.4　二叉树的基本操作及实现

1.二叉树的基本操作

二叉树的基本操作通常有以下几种。

（1）Initiate（bt）：建立一棵空二叉树。

（2）Create（x，lbt，rbt）：生成一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左子树和右子树的二叉树。

（3）InsertL（bt，x，parent）：将数据域信息为x的结点插入二叉树bt中作为结点parent的左孩子结点。如果结点parent原来有左孩子结点，则将结点parent原来的左孩子结点作为结点x的左孩子结点。

（4）InsertR（bt，x，parent）：将数据域信息为x的结点插入二叉树bt中作为结点parent的右孩子结点。如果结点parent原来有右孩子结点，则将结点parent原来的右孩子结点作为结点x的右孩子结点。

（5）DeleteL（bt，parent）：在二叉树bt中删除结点parent的左子树。

（6）DeleteR（bt，parent）：在二叉树bt中删除结点parent的右子树。

（7）Search（bt，x）：在二叉树bt中查找数据元素x。

（8）Traverse（bt）：按某种方式遍历二叉树bt的全部结点。

2.算法的实现

算法的实现依赖于具体的存储结构，当二叉树采用不同的存储结构时，上述各种操作的实现算法是不同的。下面讨论基于二叉链表存储结构的上述操作的实现算法。

（1）Initiate（bt）初始建立二叉树bt，并使bt指向头结点。在二叉树根结点前建立头结点，就如同在单链表前建立的头结点，可以方便后边的一些操作实现。

算法6.1 初始化建立二叉树

（2）Create（x，lbt，rbt）建立一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左右子树的二叉树。建立成功时返回所建二叉树结点的指针；建立失败时返回空指针。

算法6.2 生成二叉树

（3）InsertL（bt，x，parent）。

算法6.3 二叉树插入

（4）InsertR（bt，x，parent）功能类同于（3），算法略。

（5）DeleteL（bt，parent）在二叉树bt中删除结点parent的左子树。当parent或parent的左孩子结点为空时删除失败。删除成功时返回根结点指针；删除失败时返回空指针。

算法6.4 二叉树删除

（6）DeleteR（bt，parent）功能类同于（5），只是删除结点parent的右子树。算法略。

操作Search（bt，x）实际是遍历操作Traverse（bt）的特例，关于二叉树的遍历操作的实现，将在下一节中重点介绍。