目录

一、二叉树的顺序存储

存储方式

总代码

二、二叉树的链式存储（二叉链表）

1、存储结构

2、创建二叉树

总代码

一、二叉树的顺序存储

存储方式

//树的顺序存储typedef struct{char data;}BiTree;BiTree tree[MAXSIZE];

总代码

//二叉树的顺序存储#include<stdio.h>#include<math.h>#define MAXSIZE 20int num = 0, level = 0;//树的顺序存储typedef struct{char data;}BiTree;BiTree tree[MAXSIZE];void Init_Bitree(){int i = 0;for (i = 0; i < MAXSIZE - 1; i++){tree[i].data = ' ';}}void Create_Bitree(){int i = 0, j;printf("--------------------------------------可用'#'代替换行符------------------------------------\n");printf("请输入二叉树层数：\n");scanf_s("%d", &level);getchar();for (i = 0; i < level; i++){for (j = 0; j <= pow(2, i) - 1; j++){printf("\n请输入第%d层第%d号结点数据：\n", i + 1, j + 1);scanf_s("%c", &tree[num].data);getchar();num++;}}}void Traverse(){int i, j, count = 0;for (i = 0; i < level; i++){for (j = 0; j <= pow(2, i) - 1; j++)if (tree[count].data != ' ')//有值{printf("\n第%d个结点：%c\n", count, tree[count].data);printf("%c结点的层数：%d\t序号：%d\n", tree[count].data, i + 1, j + 1);count++;}if (count >= num)//遍历出了所有元素，不再浪费时间进行后续遍历return;}}int main(){Init_Bitree();Create_Bitree();Traverse();return 0;}

二、二叉树的链式存储（二叉链表）

二叉树的创建，通常会采用链式存储。

1、存储结构

//二叉树的链式存储typedef struct BiTree{char data;BiTree* Lchild, * Rchild;//左右子树BiTree* parent;}BiTree;BiTree* head;//根结点

2、创建二叉树

创建二叉树采用前序遍历的方式，主要思想是递归。先创建根结点，然后判断是否有左叶子结点；有的话继续创建lchild，没有的话返回；然后继续判断是否有右叶子结点，有的话创建rchild，没有的话返回。（具体实现过程可以看图）

//创建二叉树（默认前序遍历）void Create_Bitree(BiTree* T){if (str[index] == '#')//为空{index++;T->data = '#';return;}T->data = str[index++];//构造根结点T->Lchild = (BiTree*)malloc(sizeof(BiTree));T->Rchild = (BiTree*)malloc(sizeof(BiTree));Create_Bitree(T->Lchild);//构造左子树Create_Bitree(T->Rchild);//构造右子树}

总代码

//二叉树链式存储#include<stdio.h>#include<malloc.h>#include<string>int index = 0;std::string str = "ABD###C#G##";//(用数组也可以，一样的)//二叉树的链式存储typedef struct BiTree{char data;BiTree* Lchild, * Rchild;//左右子树BiTree* parent;}BiTree;BiTree* head;//根结点void Init_BiTree(){head = (BiTree*)malloc(sizeof(BiTree));head->parent = NULL;}//创建二叉树（默认前序遍历）void Create_Bitree(BiTree* T){if (str[index] == '#')//为空{index++;T->data = '#';return;}T->data = str[index++];//构造根结点T->Lchild = (BiTree*)malloc(sizeof(BiTree));T->Rchild = (BiTree*)malloc(sizeof(BiTree));Create_Bitree(T->Lchild);//构造左子树Create_Bitree(T->Rchild);//构造右子树}int main(){int i = 0;Init_BiTree();Create_Bitree(head);printf("测试创建效果：%c\n", head->Rchild->data);return 0;}