C语言写二叉树
简介：本文是博主当初学习阶段，用C语言实现的二叉树代码。
结点类（TNode.h）
#ifndef _TNode_h_ #define _TNode_h_ // 定义二叉树结点类型 typedef struct _TNODE_ { // 数据域 char data; // 指针域(左、右孩子指针) struct _TNODE_ *lch, *rch; } TNODE; #endif
二叉树类（BinTree.h）
#ifndef _BinTree_h_ #define _BinTree_h_ #include "TNode.h" // 创建二叉树 void BinTreeCreate(TNODE **root); // 创建二叉树 void BinTreeClear(TNODE **root); // 销毁二叉树 void BinTreeDestroy(TNODE **root); // 输入二叉树 void BinTreeInput(TNODE **root); // 先序遍历 void BinTreePreorder(const TNODE *root); // 后序遍历 void BinTreePostorder(const TNODE *root); // 中序遍历 void BinTreeInorder(const TNODE *root); // 输出二叉树 void BinTreeOutput(const TNODE *root); // 求结点数 int BinTreeNumNode(const TNODE *root); // 叶子结点数 int BinTreeNumLeaf(const TNODE *root); // 分枝结点数 int BinTreeNumBranch(const TNODE *root); // 二叉树的深度 int BinTreeDepth(const TNODE *root); #endif
BinTree.c
创建二叉树
// 创建二叉树 void BinTreeCreate(TNODE **root) // 之所以要用二级指针 是因为会有更改一级指针的操作 { *root = NULL; }
清空二叉树
// 清空二叉树 void BinTreeClear(TNODE **root) { if (*root) { BinTreeClear(&(*root)->lch); // 这里要注意的是传入的是(*root)->lch的地址，这样才是一个二级地址 BinTreeClear(&(*root)->rch); // 这个是先释放左孩子，在释放右孩子 free(*root); *root = NULL; } }
销毁二叉树
// 销毁二叉树 void BinTreeDestroy(TNODE **root) { BinTreeClear(root); // 注意传的是二级指针 }
输入二叉树
void BinTreeInput(TNODE **root) { // if (*root != NULL && tag == 0) // { // BinTreeClear(root); // } tag = 1; char element; scanf (" %c", &element); if (element == '#') { *root = NULL; } else { *root = (TNODE *)malloc(sizeof(TNODE)); (*root)->data = element; BinTreeInput(&(*root)->lch); BinTreeInput(&(*root)->rch); } }
先序遍历
// 先序遍历 void BinTreePreorder(const TNODE *root) { if (root) { printf("%c", root->data); BinTreePreorder(root->lch); BinTreePreorder(root->rch); } }
后序遍历
// 后序遍历 void BinTreePostorder(const TNODE *root) { if (root) { BinTreePostorder(root->lch); BinTreePostorder(root->rch); printf("%c", root->data); } }
中序遍历
// 中序遍历 void BinTreeInorder(const TNODE *root) { if (root) { BinTreeInorder(root->lch); printf("%c", root->data); BinTreeInorder(root->rch); } }
输出二叉树
static void BinTreeOutput1(const TNODE *root, int layer) { if (root) { BinTreeOutput1(root->rch, layer + 1); for (int k = 1; k < layer; ++k) { printf(" "); } printf("%c\n", root->data); BinTreeOutput1(root->lch, layer + 1); } } void BinTreeOutput(const TNODE *root) { BinTreeOutput1(root, 1); }
求结点数
// 结点数 int BinTreeNumNode(const TNODE *root) { int num; if (root) { num = 1 + BinTreeNumNode(root->lch) + BinTreeNumNode(root->rch); } else { num = 0; } return num; }
叶子结点数
// 叶子结点数 int BinTreeNumLeaf(const TNODE *root) { int num; if (root) { if (root->lch == NULL && root->rch == NULL) { num = 1; } else { num = BinTreeNumLeaf(root->lch) + BinTreeNumLeaf(root->rch); } } else { num = 0; } return num; }
分枝结点数
// 分枝结点数 int BinTreeNumBranch(const TNODE *root) { int num = 0; if (root) { if (root->lch != NULL || root->rch != NULL) { num = 1; } num += BinTreeNumBranch(root->lch) + BinTreeNumBranch(root->rch); } else { num = 0; } return num; }
二叉树的深度
// 深度 int BinTreeDepth(const TNODE *root) { int l, r; if (root == NULL) { return 0; } else { l = BinTreeDepth(root->lch); r = BinTreeDepth(root->rch); return l > r ? l + 1 : r + 1; } }
测试程序
int main(void) { int loop = 1, num; char ch; TNODE *root; BinTreeCreate(&root); while (loop) { printf("I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > "); scanf(" %ch", &ch); ch = toupper(ch); switch (ch) { case 'I': printf("输入: "); BinTreeInput(&root); break; case 'O': printf("输出:\n"); BinTreeOutput(root); break; case 'C': BinTreeClear(&root); printf("清空\n"); break; case 'T': printf("遍历\n1-先序 2-中序 3-后序 0-返回 > "); scanf("%d", &num); if (num == 1) { printf("先序遍历: "); BinTreePreorder(root); putchar('\n'); } else if (num == 2) { printf("中序遍历: "); BinTreeInorder(root); putchar('\n'); } else if (num == 3) { printf("后序遍历: "); BinTreePostorder(root); putchar('\n'); } else if (num != 0) { printf("不正确的遍历选项!\n"); } break; case 'D': printf("数据\n1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > "); scanf("%d", &num); if (num == 1) { printf("结点数: %d\n", BinTreeNumNode(root)); } else if (num == 2) { printf("叶子结点数: %d\n", BinTreeNumLeaf(root)); } else if (num == 3) { printf("分枝结点数: %d\n", BinTreeNumBranch(root)); } else if (num == 4) { printf("深度: %d\n", BinTreeDepth(root)); } else if (num != 0) { printf("不正确的数据选项!\n"); } break; case 'Q': loop = 0; break; default: printf("不正确的操作选项!\n"); break; } } BinTreeDestroy(&root); return 0; }
运行效果
I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > x 不正确的操作选项! I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > I 输入: EIBJ##H###DF#A##G#C## I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > o 输出: C G D A F E I H B J I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > t 遍历 1-先序 2-中序 3-后序 0-返回 > 9 不正确的遍历选项! I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > T 遍历 1-先序 2-中序 3-后序 0-返回 > 0 I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > t 遍历 1-先序 2-中序 3-后序 0-返回 > 1 先序遍历: EIBJHDFAGC I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > T 遍历 1-先序 2-中序 3-后序 0-返回 > 2 中序遍历: JBHIEFADGC I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > t 遍历 1-先序 2-中序 3-后序 0-返回 > 3 后序遍历: JHBIAFCGDE I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d 数据 1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 9 不正确的数据选项! I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > D 数据 1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 0 I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d 数据 1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 1 结点数: 10 I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > D 数据 1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 2 叶子结点数: 4 I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d 数据 1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 3 分枝结点数: 6 I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d 数据 1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 4 深度: 4 I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > c 清空 I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > O 输出: I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d 数据 1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 1 结点数: 0 I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > i 输入: ABD##E##CF##G## I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > o 输出: G C F A E B D I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d 数据 1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 1 结点数: 7 I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > Q
