实现二叉树的一些基本操作_二叉树基本操作的实现

作为一种基本的数据结构，树形结构在生活中有着众多的应用，但因为研究的困难性，我们一般深入研究的是相对简单的二叉树，再想办法将一般情况的数转化为二叉树来处理。

今天我们要研究的问题是如何实现二叉树的基本操作，其中大量用到了递归算法。在实现二叉树基本操作基础上，我们会再尝试实现左右子树的交换操作，具体如下：

一、二叉树的若干基本操作

（1）二叉树的存储定义。实现任何一种数据结构首先要做的都是存储，二叉树的存储从单个节点的角度去考虑，要做的一共有三件事情：节点的元素值，节点的左孩子，节点的右孩子。而整个二叉树其实就是由若干个这样的节点组成的，不同节点之间的关系通过左右孩子来体现。故二叉树的存储定义如下：

typedef struct BTree{
    TElemType data;
    struct BTree *lchild;
    struct BTree *rchild;
}BiNode,*BiTree;

注意：给予struct BTree的两个别名中 BiNode 是等价于 struct BTree 的，仅是形式略显简单，而BiTree 是指针类型，指向一个 struct BTree 类型的变量。故之后我们定义变量时用的 BiTree 就等价于 BiNode * ，这一点不注意的话容易搞混。

（2）建立二叉树

二叉树的建立涉及到二叉树的遍历，其分为三种：前序遍历、中序遍历和后序遍历。分别是 根左右 、 左根右 、 左右根 ，大家可以方便的简记为 “根” 在哪儿就是什么遍历： “根”在前面就是前序， “根” 在中间就是中序， “根” 在后面就是后序。这里以前序为例来建立二叉树。

还有一个问题在于怎么判断节点处该不该有值。我们的处理办法是默认二叉树的每个节点都有左右孩子，遇到值就正常输入，遇到空就输入空格。最后系统判断的时候遇到某一个左右孩子都是空值的节点时，系统就知道这个分支到头了，该返回了。

Status CreateBiTree(BiTree &T)
{ // 按完全先序序列输入二叉树中结点的值
	char ch;
	scanf("%c",&ch);
 
	if(ch == ' ')	T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiNode));
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return OK;
}

关于递归，其实就是自己调用自己，大家回头要自己好好琢磨琢磨。

（3）遍历二叉树

如前所述，遍历分为前序、中序和后序。系统判断是否走到头的依据是当前节点的左右孩子是否都为空，而这一步判断是要我们体现在代码里面的。前序、中序和后序在代码上的差别其实不大，就是三行代码换了个位置罢了。这个算法的核心依然是递归，代码如下：

前序：

Status PreOrderTraverse(BiTree T,void(*Visit)(TElemType))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。
	// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
    if(!T)  return ERROR;
 
    if(T)
    {
        Visit(T->data);
        PreOrderTraverse(T->lchild,*Visit);
        PreOrderTraverse(T->rchild,*Visit);
    }
}

中序：

Status InOrderTraverse(BiTree T,void(*Visit)(TElemType))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
	// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
    if(!T)  return ERROR;
 
    if(T)
    {
        InOrderTraverse(T->lchild,*Visit);
        Visit(T->data);
        InOrderTraverse(T->rchild,*Visit);
    }
}

后序：

Status PostOrderTraverse(BiTree T,void(*Visit)(TElemType))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
	// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
    if(!T)  return ERROR;
 
    if(T)
    {
        PostOrderTraverse(T->lchild,*Visit);
        PostOrderTraverse(T->rchild,*Visit);
        Visit(T->data);
    }
}

大家可以看到，这三段代码有高度的重复性，所以理解了递归的本质，这三段代码就是小菜一碟了。

（4）统计二叉树的叶子结点数

实现这一步操作我们要考虑一件事情：叶子节点有什么特殊的地方吗？有没有什么特质能够将叶子节点和其他节点区分开来呢？很容易想到的是，叶子节点的左右孩子都为空。仅凭这一个条件就能够将所有的叶子节点找出来。而我们要做的是 “计数” 这样一个操作，那就更容易了呀，每次遇到叶子节点，我们不用费劲地去想法设法存储它，只要对计数变量 count 加1，让系统知道这里有一个叶子节点就可以了。我们关注的是 “有” ，而它具体的属性、值什么的我们并不关心。

void CountLeaf (BiTree T,int &count)
{   //统计二叉树的叶子结点数
    if(!T)
    {
        return;
    }
    else
    {
        if(!T->lchild && !T->rchild)
        {
            count++;
            return;
        }
        else
        {
            CountLeaf(T->lchild,count);
            CountLeaf(T->rchild,count);
        }
    }
}

（5）求二叉树的深度

所谓 “二叉树的深度” ，其实就是从根节点到叶子节点路径长度的最大值。这个算法依然要用到递归。首先，递归的出口显然是：如果节点为空，那么深度为0，如果左右孩子都为空，而本身不为空，那么深度为1 ，” 为了保险起见，这两个出口最好都写上去，"油多不坏菜" 嘛。接着我们考虑最一般的一个节点：左右孩子都不为空，我们可以先递归求出以左右孩子作为根节点的左右子树的深度，取其中的最大值，再加1，就得到了当前节点所在子树的深度。

int TreeDepth (BiTree T)
{ // 返回二叉树的深度
    if(!T)  return 0;//空树深度为0
 
    if(!T->lchild && !T->rchild)    return 1;
    else
    {
        int temp_l = TreeDepth(T->lchild);
        int temp_r = TreeDepth(T->rchild);
        return (temp_l>temp_r?temp_l:temp_r)+1;
    }
}

注意：本题我们说的 “深度” 指的是 “树的深度” ，代码中具体体现的是 “节点所在子树的深度” ，它是 “从下往上” 数的。而我们一般意义上的 “结点的深度” 是 “节点在祖先树中的深度”，它是 “从上往下” 数的，大家注意区分。

（6）按竖向树状打印二叉树

竖向树状就类似于书架上的书籍一样，高低参差不齐，它通过输出的高低不齐来体现节点深度的不统一，是二叉树一种很巧妙的表示方法。实现起来也很容易：只需要直到每个节点的深度即可。注意：这里不能调用之前实现的树的深度的那个算法，理由我已经说了，二者在逻辑上是不一致的。我们从根节点开始遍历，给予一个深度遍历 nlayer ，初值为1，表示根节点的深度为1，每往下走一层，nlayer 加1，对每个结点输出时，根据 nlayer 的数值输出相应数量的减号即可。

Status PrintTree(BiTree bt,int nLayer)  /* 按竖向树状打印的二叉树 */
{
    if(!bt)  return ERROR;
    else
    {
        PrintTree(bt->lchild,nLayer+1);
 
        for(int i=1;i<nLayer;i++)    printf(" -");
        printf("%c\n",bt->data);
 
        PrintTree(bt->rchild,nLayer+1);
    }
    return OK;
}

运行结果截图：

 （7）销毁二叉树

销毁二叉树的操作是最简单的递归，只要二叉树当前节点的元素值不为空，就递归左右子树，并释放当前元素所占的空间。

Status DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
    if(!T)  return ERROR;
 
    DestroyBiTree(T->lchild);
    DestroyBiTree(T->rchild);
    free(T);
 
    return OK;
}

二，交换左右子树

二叉树交换左右子树依然是通过递归来实现的，核心做法类似于我们刚学 C 时写的交换两个元素值的代码：通过一个中间变量来暂存其中一个节点，再去实现节点的交换，接着递归即可。

void exchange_tree(BiTree T)//交换左右子树
{
    BiTree t;
    if(T)
    {
        t = T->lchild;
        T->lchild = T->rchild;
        T->rchild = t;
        exchange_tree(T->lchild);
        exchange_tree(T->rchild);
    }
}

以上即为全部内容。如果本文对你有帮助的话，还请您点一个赞哦，谢谢。