数据结构与算法学习笔记九-二叉树的链式存储表示法和实现(C语言)

前言

1.二叉树的链式存储

2.二叉链表的表示和实现

1.定义

2.创建

4.中序遍历二叉树

5.后序遍历二叉树

6.后序遍历二叉树

7.完整代码

前言

这篇博客主要介绍二叉树的链式存储结构。

1.二叉树的链式存储

上篇文章中介绍了二叉树的顺序存储结构，在最坏的情况下，比如二叉树仅有左子树或者右子树的时候，我们仍然需要为不存在的节点分配大量的存储空间，这无疑会造成存储空间的浪费。考虑到二叉树的三要素：数据域、右子树指针、左子树指针，我们可以考虑使用链式存储来表示二叉树。

当我们使用数据域、左右子树指针表示二叉树的结构时，得到的二叉树链表成为二叉链表。我们还可以再二叉链表的基础上增加一个父结点的数据域，这样得到的二叉树链表称为三叉链表。

二叉链表和三叉链表的存储结构如下图所示：

图1.二叉链表和三叉链表的表示

2.二叉链表的表示和实现

1.定义

typedef char TelemType;
typedef int Status;
typedef struct BiTNode{TelemType data;//数据域struct BiTNode * lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

2.创建

// 创建二叉树
Status createBiTree(BiTree *tree) {TelemType data;scanf("%c", &data); // 读取节点数据if (data == '#') {*tree = NULL; // 空节点} else {*tree = (BiTNode *)malloc(sizeof(BiTNode));if (!*tree) {exit(EXIT_FAILURE); // 内存分配失败return 0;}(*tree)->data = data; // 存储节点数据createBiTree(&((*tree)->lchild)); // 递归创建左子树createBiTree(&((*tree)->rchild)); // 递归创建右子树}return 1; // 创建成功
}

3.先序遍历二叉树

// 先序遍历二叉树
Status preOrderTraverse(BiTree tree) {if (tree == NULL) {return 1; // 空树，遍历结束}// 访问根节点printf("%c ", tree->data);// 递归遍历左子树preOrderTraverse(tree->lchild);// 递归遍历右子树preOrderTraverse(tree->rchild);return 1; // 遍历成功
}

4.中序遍历二叉树

// 中序遍历二叉树
Status inOrderTraverse(BiTree tree) {if (tree == NULL) {return 1; // 空树，遍历结束}// 递归遍历左子树inOrderTraverse(tree->lchild);// 访问根节点printf("%c ", tree->data);// 递归遍历右子树inOrderTraverse(tree->rchild);return 1; // 遍历成功
}

5.后序遍历二叉树

// 后序遍历二叉树
Status postOrderTraverse(BiTree tree) {if (tree == NULL) {return 1; // 空树，遍历结束}// 递归遍历左子树postOrderTraverse(tree->lchild);// 递归遍历右子树postOrderTraverse(tree->rchild);// 访问根节点printf("%c ", tree->data);return 1; // 遍历成功
}

`6.后序遍历二叉树`

// 后序遍历二叉树
Status postOrderTraverse(BiTree tree) {if (tree == NULL) {return 1; // 空树，遍历结束}// 递归遍历左子树postOrderTraverse(tree->lchild);// 递归遍历右子树postOrderTraverse(tree->rchild);// 访问根节点printf("%c ", tree->data);return 1; // 遍历成功
}

7.完整代码

#include <stdio.h>
#include <stdlib.h>typedef char TelemType;
typedef int Status;
typedef struct BiTNode{TelemType data;//数据域struct BiTNode * lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;// 创建二叉树
Status createBiTree(BiTree *tree) {TelemType data;scanf("%c", &data); // 读取节点数据if (data == '#') {*tree = NULL; // 空节点} else {*tree = (BiTNode *)malloc(sizeof(BiTNode));if (!*tree) {exit(EXIT_FAILURE); // 内存分配失败return 0;}(*tree)->data = data; // 存储节点数据createBiTree(&((*tree)->lchild)); // 递归创建左子树createBiTree(&((*tree)->rchild)); // 递归创建右子树}return 1; // 创建成功
}// 先序遍历二叉树
Status preOrderTraverse(BiTree tree) {if (tree == NULL) {return 1; // 空树，遍历结束}// 访问根节点printf("%c ", tree->data);// 递归遍历左子树preOrderTraverse(tree->lchild);// 递归遍历右子树preOrderTraverse(tree->rchild);return 1; // 遍历成功
}// 中序遍历二叉树
Status inOrderTraverse(BiTree tree) {if (tree == NULL) {return 1; // 空树，遍历结束}// 递归遍历左子树inOrderTraverse(tree->lchild);// 访问根节点printf("%c ", tree->data);// 递归遍历右子树inOrderTraverse(tree->rchild);return 1; // 遍历成功
}// 后序遍历二叉树
Status postOrderTraverse(BiTree tree) {if (tree == NULL) {return 1; // 空树，遍历结束}// 递归遍历左子树postOrderTraverse(tree->lchild);// 递归遍历右子树postOrderTraverse(tree->rchild);// 访问根节点printf("%c ", tree->data);return 1; // 遍历成功
}int main(int argc, const char *argv[]) {BiTree tree;printf("请输入二叉树的前序序列（使用'#'表示空节点）：\n");createBiTree(&tree);printf("二叉树创建成功！\n");printf("先序遍历二叉树..\n");preOrderTraverse(tree);printf("\n中序遍历二叉树...\n");inOrderTraverse(tree);printf("\n后序遍历二叉树...\n");postOrderTraverse(tree);printf("\n");return 0;
}

例如我们要生成如下图所示的二叉树。控制台输入ABD##E##CF##G##