数据结构之二叉树的存储与遍历

Love The Way You Lie 2022-04-23 08:04 197阅读 0赞

一般情况下，二叉树可以采用顺序存储结构和链式存储结构来存储。

**二叉树顺序存储结构**

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置即数组的下标要能体现出结点之间的逻辑关系，比如双亲与孩子的关系，左右孩子的兄弟关系等。如果有一棵二叉树如下图所示

![20190903102132218.png][]

将相应的下标存入到数组中对应的位置之后，其存储的情况为：

![2019090310231668.png][]

对于一般的二叉树而言，尽管层序编号不能反映其逻辑关系，但是可以将二叉树按照其完全二叉树来编号，只不过，把不存在的结点设置为“^”或者“0”。但是，如果有一棵深度为k的右斜树，只有k个结点 ，但是如果采用顺序存储结构存储的话就需要分配2^k-1个存储单元，很明显浪费了太多的存储空间。所以，顺序存储结构适合存储完全二叉树。

**二叉链表**

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，我们称这样的链表为二叉链表，即

![20190903103401250.png][]

其中data为数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。二叉链表的结点结构定义为：

//二叉树的二叉链表结点结构定义
    typedef struct _BiTreeNode
    {
        char data;                    //数据域，结点数据
        _BiTreeNode* lchild, *rchild; //指针域，左右孩子指针
    }BiTreeNode,*BiTree;

如果使用二叉链表来存储上面的二叉树，存储结构如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70][]

**二叉树的遍历**

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树的前序遍历：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

二叉树的中序遍历：若二叉树为空，则空操作返回，否则从根结点开始，中序遍历根结点的左子树，然后访问根结点，最后便利根结点的右子树。

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

二叉树的层序遍历：若二叉树为空，则空操作返回，否则从树的第一层也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

#include<stdio.h>
    #include<malloc.h>
    typedef struct _BiTreeNode
    {
        char data;
        _BiTreeNode* lchild, *rchild;
    }BiTreeNode,*BiTree;
    //先序遍历
    void PreOrderTraverse(BiTree root)
    {
        if (root == NULL)
        {
    	return;
        }
        printf("%c", root->data);			//显示结点数据
        PreOrderTraverse(root->lchild);		//再先序遍历左子树
        PreOrderTraverse(root->rchild);		//最后再先序遍历右子树
    }
    //中序遍历
    void InOrderTraverse(BiTree root)
    {
        if (root == NULL)
        {
    	return;
        }
        InOrderTraverse(root->lchild);		//先中序遍历左子树
        printf("%c", root->data);			//再显示根结点数据
        InOrderTraverse(root->rchild);		//最后再中序遍历右子树
    }
    //后序遍历
    void PostOrderTraverse(BiTree root)
    {
        if (root == NULL)
        {
    	return;
        }
        PostOrderTraverse(root->lchild);	//先后序遍历左子树
        PostOrderTraverse(root->rchild);	//再后序遍历右子树
        printf("%c", root->data);			//最后显示根结点数据
    }
    //创建二叉树
    void CreateBiTree(BiTree* root)
    {
        char e;
        scanf("%c", &e);
        if (e == '#')
        {
    	*root = NULL;
    	return;
        }
        else
        {
    	*root = (BiTreeNode*)malloc(sizeof(BiTree));
    	(*root)->data = e;			//生成根结点
    	CreateBiTree(&(*root)->lchild);		//构造左子树
    	CreateBiTree(&(*root)->rchild);		//构造右子树
        }
    }
    
    int main()
    {
        BiTree root = NULL;
        CreateBiTree(&root);
        printf("先序遍历:");
        PreOrderTraverse(root);
        printf("\n中序遍历:");
        InOrderTraverse(root);
        printf("\n后序遍历:");
        PostOrderTraverse(root);
        printf("\n");
        return 0;
    }

如果有一颗二叉树，其结构如下所示：

![20190903123227948.png][]

创建二叉树时其输入顺序以前序为准，那么其遍历结果为：

![20190903123319969.png][]

此即二叉树的遍历相关知识~

[20190903102132218.png]: /images/20220322/78536ddb86444bc682cbd74ede2d12c9.png
[2019090310231668.png]: /images/20220322/df6446951ceb49bca13ccfc941fb0db0.png
[20190903103401250.png]: /images/20220322/1a5854c603db49cea821804416a97777.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70]: /images/20220322/64fa7edbc5ee45eb923fe829e1bb00be.png
[20190903123227948.png]: /images/20220322/8a473cd40f534c5c865f9d616e98a578.png
[20190903123319969.png]: /images/20220322/b645fb5f16fa47419b3e9324185e3136.png