图解二叉树及二叉树遍历

灰太狼 2022-09-28 13:09 210阅读 0赞

# 二叉树及二叉树遍历 #

*  **完全二叉树**
 *  **二叉树的遍历**
 *  **遍历的性质**

## 1、完全二叉树 ##

> 对于一棵具有n个节点的二叉树（按层序编号），如果编号为i的节点与同样深度的满二叉树中编号为i的节点在二叉树的位置完全相同，则为完全二叉树。

换句话来说，如果每个节点按照满二叉树的结构逐层顺序进行编号，如果编号出现编号空挡，就说明不是完全二叉树，否则就是。如下图所示：

![这里写图片描述][SouthEast]

左边二叉树按照完全二叉树进行编号，出现了10号的空挡，右边二叉树出现了6,7号的空挡，所以以上两棵树都不是完全二叉树。

## 2、二叉树的遍历 ##

> 二叉树的遍历主要包括前序遍历、中序遍历、后序遍历和层序遍历四种，其中前三种是非常常用的，下面主要介绍前三种遍历的方法。

*  **前序遍历**

> 若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。如下图所示：

![这里写图片描述][SouthEast 1]

void PreOrderTraverse(BiTree T)
    {
        if(T==NULL)
            return;
        printf("%c", T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }

> 其实前序遍历的技巧还可以有如下方式：

![这里写图片描述][SouthEast 2]

1、从根节点的左边开始，绕过所有节点和边，画出一条封闭的、有向的遍历曲线（如上图红色所示）。

2、对于每个节点，曲线第一次从连线进入节点的位置标记为1，最后一次从节点出去的位置标记为2 。

3、如上图的标记所示，沿着遍历曲线的方向，依次经过标记为1的节点为前序遍历序列：ABEFIJCDGH 。

*  **中序遍历**

> 若二叉树为空，则空操作返回，否则从根节点开始（注意不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。如下图所示：

![这里写图片描述][SouthEast 3]

void InOrderTraverse(BiTree T)
    {
        if(T==NULL)
            return; 
        InOrderTraverse(T->lchild);
        printf("%c", T->data);
        InOrderTraverse(T->rchild);
    }

> 同样根据上一节前序遍历的技巧，同样适用于中序遍历，但是相对复杂一些：

![这里写图片描述][SouthEast 4]

1、对于所有叶子节点，在标记1和2中间加上标记0。

2、当父节点只有左子树时，在该节点右下方标记0；当父节点只有右子树时，在该节点的左下方标记0 。

3、当父节点同时有左右子树时，在其正下方标记0 。

4、沿着遍历曲线的方向，依次经过标记为0的节点为中序遍历序列：DGBAECHF 。

*  **后序遍历**

> 若二叉树为空，则空操作返回，否则从左到右先叶子后节点的方式遍历访问左右子树，最后是访问根节点。

![这里写图片描述][SouthEast 5]

void PostOrderTraverse(BiTree T)
    {
        if(T==NULL)
            return; 
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c", T->data);
    }

> 其实后序遍历的技巧和前序遍历的基本是差不多的，有如下方式：

![这里写图片描述][SouthEast 2]

沿着遍历曲线的方向，依次经过标记为2的节点为后序遍历序列：EIJFBCGHDA 。

## 3、遍历的性质 ##

> 两个二叉树遍历的性质：  
> 1、已知前序遍历和中序遍历，可以唯一的确定一个二叉树；  
> 2、已知后序遍历和中序遍历，可以唯一的确定一个二叉树；

但是，已知前序遍历和后序遍历，是不能唯一的确定一棵二叉树的。比如，前序遍历ABC，后续遍历CBA，我们可以确定A是根节点，但是无法确定那个是左子树，哪个是右子树。

![这里写图片描述][SouthEast 6]

[SouthEast]: /images/20220708/ebcf1813686f4787b4cce962167b6f09.png
[SouthEast 1]: /images/20220708/8017749c693c414e99ad0bd096a96865.png
[SouthEast 2]: /images/20220708/14e0e11da28041f1ae109492eb0a85c8.png
[SouthEast 3]: /images/20220708/5b0f9a5769ca4f5b8db1de1738917368.png
[SouthEast 4]: /images/20220708/0ed601ac090844b195b972791278354c.png
[SouthEast 5]: /images/20220708/533ef542ded443a09992e42be305643b.png
[SouthEast 6]: /images/20220708/0b23fe2c8ba24bfb83aa45679336a434.png