数据结构与算法(九)二叉树的基本功能实现
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);
}
<查找指定结点>、<删除结点>等功能由于与上面已实现的功能的实现方法异曲同工,都是使用适合的遍历方法,所以不再实现。
而<插入结点>由于方式太多(不指定位置、指定位置),所以也不实现了。