数据结构与算法(九)二叉树的基本功能实现

1、二叉树的创建

首先创建一颗二叉树需要输入结点，但是如果我们输入结点的前序遍历序列为：ABDC，我们如何确定哪个是左孩子？哪个是右孩子？

因此为了能让每个结点确认是否有左、右孩子，我们需要对原二叉树进行扩展。也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一个特定值，比如“#”。

我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一颗二叉树了。之前的结点的前序遍历序列就可以变为：AB#D##C##。

创建二叉链表方法，其实就是前序遍历方法，不过对结点的处理从之前的打印数据，变为了读值、新建结点并赋值而已。

/*构造二叉链表递归算法*/
void CreateBinaryTree(LinkBinaryTree &T)
{
    T = NULL;             /*新节点先为空*/
    DataType element;    
    scanf("%c", &element);/*读值*/
 	
    if (element == '#') return;  /*如果为特定值，新结点为空，返回*/

    T = new BinaryTree;   /*新结点分配内存*/
    T->data = element;    /*赋值*/
    CreateBinaryTree(T->leftChild);  /*递归创建左子树*/
    CreateBinaryTree(T->rightChild); /*递归创建右子树*/
}

2、二叉树的深度

从最底层一层一层往上返回深度，每个结点得到它左、右子树的深度，并选择其中的最大值加一（这一层的深度）往上返回。

获取深度功能同样需要左、右子树操作后，才轮到双亲结点，所以这里使用后序遍历法。

int BinaryTreeDepth(LinkBinaryTree T)
{
    if (T == NULL) return 0; /*不存在，所以返回深度为0*/	
	
    int leftChildDepth, rightChildDepth, maxDepth;
    leftChildDepth  = BinaryTreeDepth(T->leftChild);  /*递归左子树的深度*/
    rightChildDepth = BinaryTreeDepth(T->rightChild); /*递归右子树的深度*/
    /*在左子树的深度和右子树的深度中选取最大的，并把这一层的深度加上*/
    maxDepth = (leftChildDepth > rightChildDepth) ? (leftChildDepth+1) : (rightChildDepth+1);
    return maxDepth;/*返回最大深度*/
}

3、二叉树的清空和销毁

清空操作肯定是要先清除左、右子树了之后，才到双亲结点，所以这里使用后序遍历法。

清空功能，我选择保留根结点，不然就和销毁功能一样了。

而销毁功能，需要先进行一次清空功能，再把根结点给释放即可。

/*清空二叉链表递归算法*/
void ClearBinaryTree(LinkBinaryTree &T, DataType RootData)
{
    if (T == NULL) return;
    ClearBinaryTree(T->leftChild, RootData);  /*递归清除左子树*/
    ClearBinaryTree(T->rightChild, RootData); /*递归清除右子树*/
    if (T->data == RootData) return;          /*判断结点是不是根结点，是根结点就不清除*/
    T = NULL;                                 /*置空该结点并释放*/
    free(T);
}

/*构销毁二叉链表算法*/
void DestroyBinaryTree(LinkBinaryTree &T)
{
    ClearBinaryTree(T, T->data);/*销毁前先清空二叉树*/
    T = NULL;                   /*置空根结点并释放*/
    free(T);                    
}

<查找指定结点>、<删除结点>等功能由于与上面已实现的功能的实现方法异曲同工，都是使用适合的遍历方法，所以不再实现。

而<插入结点>由于方式太多（不指定位置、指定位置），所以也不实现了。