数据结构第五章-树与二叉树 二叉树的C语言实现代码

#define _CRT_SECURE_NO_WARNINGS 1 #include "BiTree.h" //二叉树的初始化 void BTInit(BTL* T) { assert(T); *T = NULL; //BTL为一级指针类型，这里的参数T为二级指针类型，因此需要对其解引用 } //二叉树的创建——创建BST void CreatBST(BTL* T, ElemType x) { assert(T); BTN* p = (BTN*)calloc(1, sizeof(BTN));//创建结点 if (!p) { perror("CreatBST calloc fail");//空间申请失败时报错 return; } p->data = x;//将数据放入x中 p->lchild = p->rchild = NULL;//将左右指针置空 BTN* t = *T;//指向根结点的指针 while (t) { if (t->data < p->data && t->rchild) //当根<该结点,且右子树不为空树时 t = t->rchild;//继续向右子树遍历 else if (t->data > p->data && t->lchild)//当根>该结点,且左子树不为空树时 t = t->lchild;//继续向左子树遍历 else if (t->data < p->data && !t->rchild)//当根结点<该结点并且右子树为空时 { t->rchild = p;//将该结点插入右子树 return; } else if (t->data > p->data && !t->lchild)//当根结点>该结点并且左子树为空时 { t->lchild = p;//将该结点插入左子树 return; } else { printf("树中已存在结点%d，插入失败\n", p->data); return; } } *T = p;//当未进入循环时，说明该树为空树，直接将该结点作为根结点插入树中 return; } //二叉树的创建——通过遍历序列创建二叉树 BTN* BTCreat(ElemType* arr, int* pi) { //T为二级指针 //arr为存放序列的数组 //pi为数组下标 assert(arr && pi); //限制条件 if (!arr[*pi])//元素为'\0'时 return NULL;//结束创建 if (arr[*pi] == '#') { //当元素为'#'时，二叉树对应结点为空 (*pi)++;//继续向后遍历 return NULL;//返回空指针 } //创建根结点 BTN* p = (BTN*)calloc(1, sizeof(BTN)); if (!p) { perror("BTCreat calloc fail"); return; } p->data = arr[(*pi)++];//访问根结点 p->lchild = BTCreat(arr, pi);//遍历创建左子树 p->rchild = BTCreat(arr, pi);//遍历创建右子树 return p; } //二叉树的销毁 void BTDestroy(BTL* T) { assert(T); if (!(*T)) return; //通过后序遍历销毁二叉树 BTDestroy(&((*T)->lchild)); BTDestroy(&((*T)->rchild)); free(*T);//释放叶结点的内存 *T = NULL; } //访问根结点 void visit(BTN* root) { printf("%d ", root->data); } //先序遍历 void PreOrder(BTL T) { if (!T) return; visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } //中序遍历 void InOrder(BTL T) { if (!T) return; InOrder(T->lchild); visit(T); InOrder(T->rchild); } //后序遍历 void PostOrder(BTL T) { if (!T) return; PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } //层序遍历 void LevelOrder(BTL T) { if (!T) return; LQ Q; QueueInit(&Q); BTN* p = T; EnQueue(&Q, p); while (!isEmptyQueue(Q)) { DeQueue(&Q, &p); visit(p); if (p->lchild) EnQueue(&Q, p->lchild); if (p->rchild) EnQueue(&Q, p->rchild); } } //求树高 int Depth(BTL T) { if (!T) return 0; int l = Depth(T->lchild); int r = Depth(T->rchild); return l > r ? l + 1 : r + 1; } //求结点总数 int BTSize(BTL T) { if (!T) return 0; int l = BTSize(T->lchild); int r = BTSize(T->rchild); return l + r + 1; } //求第K层结点数 int BTLevelKSize(BTL T, int k) { if (!T) return 0; if (k == 1) return 1; int l = BTLevelKSize(T->lchild, k - 1); int r = BTLevelKSize(T->rchild, k - 1); return l + r; } //求叶结点数 int BTLeafSize(BTL T) { if (!T) return 0; if (!T->lchild && !T->rchild) return 1; int l = BTLeafSize(T->lchild); int r = BTLeafSize(T->rchild); return l + r; } //二叉树基本操作的测试 void test1() { BTL T;//创建二叉链表 BTInit(&T);//初始化二叉链表 ElemType arr[100] = { 0 }; int ret = scanf("%s", arr);//获取先序序列 int i = 0;//数组下标 T = BTCreat(arr, &i);//通过先序序列创建二叉树 //通过遍历获取遍历序列 printf("\n先序序列为："); PreOrder(T); printf("\n中序序列为："); InOrder(T); printf("\n后序序列为："); PostOrder(T); printf("\n层序序列为："); LevelOrder(T); int hight = Depth(T); printf("\n\n该二叉树的高度为%d\n", hight); int T_size = BTSize(T); printf("\n该二叉树总共有%d个结点\n", T_size); int k = 0; getchar();//清空缓冲区 printf("\n"); while (scanf("%d", &k) == 1) { int K_size = BTLevelKSize(T, k); printf("第%d层共有%d个结点\n\n", k, K_size); } int leaf = BTLeafSize(T); printf("\n该二叉树共有%d个叶结点\n", leaf); BTDestroy(&T); T_size= BTSize(T); printf("\n完成销毁后该二叉树总共有%d个结点\n\n", T_size); } //二叉树基本操作的测试2 void test2() { BTL T;//创建二叉链表 BTInit(&T);//初始化二叉链表 ElemType e = 0; while (scanf("%d", &e) == 1) CreatBST(&T, e);//创建BST //通过遍历获取遍历序列 printf("\n先序序列为："); PreOrder(T); printf("\n中序序列为："); InOrder(T); printf("\n后序序列为："); PostOrder(T); printf("\n层序序列为："); LevelOrder(T); int hight = Depth(T); printf("\n\n该二叉树的高度为%d\n", hight); int T_size = BTSize(T); printf("\n该二叉树总共有%d个结点\n", T_size); int k = 0; getchar();//清空缓冲区 printf("\n"); while (scanf("%d", &k) == 1) { int K_size = BTLevelKSize(T, k); printf("第%d层共有%d个结点\n\n", k, K_size); } int leaf = BTLeafSize(T); printf("\n该二叉树共有%d个叶结点\n", leaf); BTDestroy(&T); T_size = BTSize(T); printf("\n完成销毁后该二叉树总共有%d个结点\n\n", T_size); }