树：二叉链表的实现

傷城~ 2022-05-31 08:13 192阅读 0赞

# 二叉链表介绍 #

**二叉树每个结点最多有2个孩子，所以为它设计一个数据域和2个指针域是比较自然的想法，我们称这样的链表叫做二叉链表**。

# 二叉链表思路 #

二叉链表的数据结构，数据域，左右孩子指针域。每个树结点都有左右孩子，**如果没有孩子那么孩子指针域为NULL**。**我们用char类型的数据来模拟二叉链表的创建和遍历**。

我们知道二叉链表的**遍历有3种**，**前序遍历，中序遍历，后序遍历**。那么**创建链表的时候同样我们可以约定是前序、中序还是后序的形式进行进创建树结点**。以下图为例，我们使用**前序遍历的形式创建二叉链表**，然后将用3种遍历形式输出。**如图按照前序遍历的结果是：ABCDEG，中序遍历结果：CBDAEG，后序遍历结果：CDBGEA**。

![SouthEast][]

# 二叉链表代码 #

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    typedef char EleType;
    typedef struct BiTNode
    {
    	EleType data;//数据结点数据域
    	struct BiTNode	*lchild, *rchild;//左孩子，右孩子结点指针域
    }BiTNode,*BiTree;
    
    //约定通过前序遍历创建结点
    //每个结点都有左右孩子，孩子不存在为NULL
    void CreatBiTree(BiTree* tree)
    {
    	char c;
    	scanf("%c",&c);
    	if (' '== c)
    	{
    		*tree = NULL;
    	}
    	else
    	{
    		*tree = (BiTNode*)malloc(sizeof(BiTNode));
    		(*tree)->data = c;
    		CreatBiTree(&(*tree)->lchild);//创建左子树
    		CreatBiTree(&(*tree)->rchild);//创建右子树
    	}
    }
    void visit(EleType data,int level)
    {
    	printf("%c 第%d层\n", data,level);
    	return;
    }
    
    //前序遍历
    void PreOrderTraverse(BiTree tree,int level)
    {
    	if (NULL != tree)
    	{
    		visit(tree->data, level);
    		PreOrderTraverse(tree->lchild, level + 1);
    		PreOrderTraverse(tree->rchild, level + 1);
    	}
    }
    //中序遍历
    void MidOrderTraverse(BiTree tree, int level)
    {
    	if (NULL != tree)
    	{
    		MidOrderTraverse(tree->lchild, level + 1);
    		visit(tree->data, level);
    		MidOrderTraverse(tree->rchild, level + 1);
    	}
    }
    //后序遍历
    void PostOrderTraverse(BiTree tree, int level)
    {
    	if (NULL != tree)
    	{
    		PostOrderTraverse(tree->lchild, level + 1);
    		PostOrderTraverse(tree->rchild, level + 1);
    		visit(tree->data, level);
    	}
    }
    
    int main(int argc, char *argv[])
    {
    	BiTree tree = NULL;
    	printf("请按前序遍历的方式输入结点数据，没有结点不存在请使用空格代替：");
    	CreatBiTree(&tree);
    	printf("前序遍历：\n");
    	PreOrderTraverse(tree, 1);
    	printf("中序遍历：\n");
    	MidOrderTraverse(tree, 1);
    	printf("后序遍历：\n");
    	PostOrderTraverse(tree, 1);
    
    	return 0;
    }

# 代码运行验证 #

在创建二叉链表时，我们约定空格个位NULL孩子结点，我们以前序遍历的形式创建二叉链表输入应该是:**ABC  D  E G  **也就是**ABC2个空格D2个空格E1个空格G2个空格换行**。

![SouthEast 1][]

[SouthEast]: /images/20220531/9f547fa0c6da48088f9db36ae9c32cd8.png
[SouthEast 1]: /images/20220531/2e1494a1a4b143ec99a3c72ebc52b801.png