• 34.二叉链树的C语言实现

    目录

    （1）二叉树的数据结构

    （2）以前序序列建立二叉树

    （3）求树的结点数

    （4）求树的层数

    （5）结点查找

    （6）前序遍历（递归算法和非递归算法）

    （7）中序遍历（递归算法和非递归算法）

    （8）后序遍历（递归算法和非递归算法）

    （9）层次遍历算法

    （10）遍历过程中借助的栈和队列算法

    全部代码

    包含二叉链树的建立，计数，查找，各种遍历。

    （1）二叉树的数据结构

    1. //二叉链树的结构体定义
    2. typedef struct BiTNode{
    3.     ElemType data;  //数据域
    4.     BiTNode *lchild;  //指向左子树根节点的指针
    5. 	BiTNode *rchild;  //指向右子树根节点的指针
    6. }BiTNode, *BiTree;

    （2）以前序序列建立二叉树

    1. //前序序列建立二叉树
    2. void CreateBiTree(BiTree &T){
    3.     ElemType ch;
    4.     scanf("%c", &ch);
    5.     if (ch == '#')
    6.         T = NULL;  //保证是叶结点
    7.     else{
    8.         T = (BiTree)malloc(sizeof(BiTNode));
    9.         T->data = ch;  //生成结点
    10.         CreateBiTree(T->lchild);  //构造左子树
    11.         CreateBiTree(T->rchild);  //构造右子树    
    12.     }
    13. }

    （3）求树的结点数

    1. //求树的结点数（递归）
    2. int Number_Node(BiTree T){
    3.     if(T==NULL)
    4.         return 0;
    5.     else{
    6.         return Number_Node(T->lchild) + Number_Node(T->rchild) + 1;
    7.     }
    8. }

    （4）求树的层数

    1. //求树的层数（递归）
    2. int Depth(BiTree T){
    3.     if(T==NULL)
    4.         return 0;
    5.     else{
    6.         return (Depth(T->lchild) >= Depth(T->rchild)) ? Depth(T->lchild) + 1 : Depth(T->rchild) + 1;
    7.     }
    8. }

    （5）结点查找

    1. //查找结点，并说明它在第几层
    2. BiTree Search(BiTree T, char a, int level){
    3.     if(T == NULL)
    4.         return NULL;
    5.     else if(T->data == a){
    6.         printf("查找成功！元素在第%d层\n",level);
    7.         return T;
    8.     }
    9.     else{
    10.         Search(T->lchild, a, level + 1);
    11.         Search(T->rchild, a, level + 1);
    12.     }
    13. }

    （6）前序遍历（递归算法和非递归算法）

    1. //前序遍历（递归算法）
    2. void PreOrderTraverse(BiTree T){
    3. 	if (T!=NULL){
    4. 		printf("%c", T->data);
    5. 		PreOrderTraverse(T->lchild);
    6. 		PreOrderTraverse(T->rchild);
    7. 	}
    8. }
    9.  
    10. //前序遍历（非递归算法）
    11. void PreOrderTraverse2(BiTree T){
    12.     BiTree p = T; //p是遍历指针
    13.     Sqstack S;
    14.     InitStack(S);
    15.     while(p != NULL|| !IsStackEmpty(S)){
    16.         if(p){
    17.             printf("%c", p->data);
    18.             InsertSqstack(S, p);
    19.             p = p->lchild;
    20.         }
    21.         else{
    22.             p = DeleteSqstack(S, p);
    23.             p = p->rchild;
    24.         }
    25.     }
    26. }

    （7）中序遍历（递归算法和非递归算法）

    1. //中序遍历（递归算法）
    2. void InOrderTraverse(BiTree T){
    3. 	if (T!=NULL){
    4. 		InOrderTraverse(T->lchild);
    5.         printf("%c", T->data);
    6. 		InOrderTraverse(T->rchild);
    7. 	}
    8. }
    9.  
    10. //中序遍历（非递归算法）
    11. void InOrderTraverse2(BiTree T){
    12.     BiTree p = T; //p是遍历指针
    13.     Sqstack S;
    14.     InitStack(S);
    15.     while(p||!IsStackEmpty(S)){
    16.         if(p){
    17.             InsertSqstack(S, p);
    18.             p = p->lchild;
    19.         }
    20.         else{
    21.             p = DeleteSqstack(S, p);
    22.             printf("%c", p->data);
    23.             p = p->rchild;
    24.         }
    25.     }
    26. }

    （8）后序遍历（递归算法和非递归算法）

    1. //后序遍历（递归算法）
    2. void PostOrderTraverse(BiTree T){
    3. 	if (T!=NULL){
    4. 		PostOrderTraverse(T->lchild);
    5. 		PostOrderTraverse(T->rchild);
    6.         printf("%c", T->data);
    7. 	}
    8. }
    9.  
    10. //后序遍历（非递归算法）
    11. void PostOrderTraverse2(BiTree T){
    12.     Sqstack S;
    13.     InitStack(S);
    14.     BiTree p = T;
    15.     BiTree r = NULL;
    16.     while(p||!IsStackEmpty(S)){
    17.         if(p){
    18.             InsertSqstack(S, p);
    19.             p = p->lchild;
    20.         }
    21.         else{
    22.             p = S.data[S.top];  //读栈顶元素（但不出栈）
    23.             if(p->rchild&&p->rchild!=r){
    24.                 p = p->rchild;
    25.             }
    26.             else{
    27.                 p = DeleteSqstack(S, p);
    28.                 printf("%c", p->data);
    29.                 r = p;
    30.                 p = NULL;
    31.             }
    32.         }
    33.     }
    34. }

    （9）层次遍历算法

    1. //层次遍历
    2. void LevelOrder(BiTree T){
    3.     Queue q;
    4.     InitQueue(q);
    5.     BiTree p = T;
    6.     InsertQueue(q, p);
    7.     while(!IsQueueEmpty(q)){
    8.         p = DeleteQueue(q, p);
    9.         printf("%c", p->data);
    10.         if(p->lchild!=NULL)
    11.             InsertQueue(q, p->lchild);
    12.         if(p->rchild!=NULL)
    13.             InsertQueue(q, p->rchild);
    14.     }
    15. }

    （10）遍历过程中借助的栈和队列算法

    1. //（循环）队列和栈的数据结构
    2. typedef struct Queue{
    3. 	BiTree data[MAXSIZE];
    4.     int front, rear;  //头尾指针，队头指针指向第一个元素，队尾指针指向队尾元素的下一个元素
    5.     int tag;
    6. }Queue;
    7. typedef struct Sqstack{
    8.     BiTree data[MAXSIZE];
    9.     int top;  //栈顶指针指向栈顶元素
    10. }Sqstack;
    11.  
    12. //初始化
    13. int InitQueue(Queue &a){
    14.     a.front = 0;
    15.     a.rear = 0;
    16.     a.tag = 0;  //初始队列是空
    17.     return 1;
    18. }
    19. int InitStack(Sqstack &a){
    20.     a.top = -1;  //初始栈顶指针是-1
    21.     return 1;
    22. }
    23.  
    24. //判断栈和队列是否为空
    25. bool IsStackEmpty(Sqstack S){
    26.     if(S.top ==-1)
    27.         return true;
    28.     else
    29.         return false;
    30. }
    31. bool IsQueueEmpty(Queue q){
    32.     if(q.tag == 0 && q.front==q.rear)
    33.         return true;
    34.     else
    35.         return false;
    36. }
    37.  
    38. //插入
    39. int InsertQueue(Queue &a, BiTree x){
    40.     if(a.front == a.rear && a.tag == 1){
    41.         printf("当前队列已满！");
    42.         return 0;
    43.     }
    44.     else{
    45.         a.data[a.rear] = x;
    46.         a.tag = 1;  //插入队列tag置1
    47.         a.rear = (a.rear + 1) % MAXSIZE;
    48.         return 1;
    49.     }  
    50. }
    51. int InsertSqstack(Sqstack &a, BiTree x){
    52.     if(a.top == MAXSIZE-1){
    53.         printf("当前栈已满！");
    54.         return 0;
    55.     }
    56.     else{
    57.         a.top = a.top + 1;
    58.         a.data[a.top] = x;
    59.         return 1;
    60.     } 
    61. }
    62.  
    63. //删除
    64. BiTree DeleteQueue(Queue &a,BiTree x){
    65.     if(a.front == a.rear && a.tag == 0){
    66.         printf("当前队列已空！");
    67.     }
    68.     else{
    69.         x = a.data[a.front];
    70.         a.tag = 0;  //删除队列tag置0
    71.         a.front = (a.front + 1) % MAXSIZE;  //front指针+1
    72.         return x;
    73.     }  
    74. }
    75. BiTree DeleteSqstack(Sqstack &a, BiTree x){
    76.     if(a.top == -1){
    77.         printf("当前栈已空！");
    78.     }
    79.     else{
    80.         x = a.data[a.top];
    81.         a.top = a.top - 1;
    82.         return x;
    83.     }  
    84. }

    全部代码

    本次验证的二叉树如下图：

    注意：输入的是扩展二叉树，也就是要告诉计算机什么是叶结点，否则将一直递归，当输入“#”时，指针指向NULL，说明是叶结点。例如对于上图，输入的是ABD##E##C##。

    1. #include
    2. #include
    3. #include
    4. #define MAXSIZE 100
    5. #define ElemType char
    6.  
    7. //二叉链树的结构体定义
    8. typedef struct BiTNode{
    9.     ElemType data;  //数据域
    10.     BiTNode *lchild;  //指向左子树根节点的指针
    11. 	BiTNode *rchild;  //指向右子树根节点的指针
    12. }BiTNode, *BiTree;
    13.  
    14. //（循环）队列和栈的数据结构
    15. typedef struct Queue{
    16. 	BiTree data[MAXSIZE];
    17.     int front, rear;  //头尾指针，队头指针指向第一个元素，队尾指针指向队尾元素的下一个元素
    18.     int tag;
    19. }Queue;
    20. typedef struct Sqstack{
    21.     BiTree data[MAXSIZE];
    22.     int top;  //栈顶指针指向栈顶元素
    23. }Sqstack;
    24.  
    25. //初始化
    26. int InitQueue(Queue &a){
    27.     a.front = 0;
    28.     a.rear = 0;
    29.     a.tag = 0;  //初始队列是空
    30.     return 1;
    31. }
    32. int InitStack(Sqstack &a){
    33.     a.top = -1;  //初始栈顶指针是-1
    34.     return 1;
    35. }
    36.  
    37. //判断栈和队列是否为空
    38. bool IsStackEmpty(Sqstack S){
    39.     if(S.top ==-1)
    40.         return true;
    41.     else
    42.         return false;
    43. }
    44. bool IsQueueEmpty(Queue q){
    45.     if(q.tag == 0 && q.front==q.rear)
    46.         return true;
    47.     else
    48.         return false;
    49. }
    50.  
    51. //插入
    52. int InsertQueue(Queue &a, BiTree x){
    53.     if(a.front == a.rear && a.tag == 1){
    54.         printf("当前队列已满！");
    55.         return 0;
    56.     }
    57.     else{
    58.         a.data[a.rear] = x;
    59.         a.tag = 1;  //插入队列tag置1
    60.         a.rear = (a.rear + 1) % MAXSIZE;
    61.         return 1;
    62.     }  
    63. }
    64. int InsertSqstack(Sqstack &a, BiTree x){
    65.     if(a.top == MAXSIZE-1){
    66.         printf("当前栈已满！");
    67.         return 0;
    68.     }
    69.     else{
    70.         a.top = a.top + 1;
    71.         a.data[a.top] = x;
    72.         return 1;
    73.     } 
    74. }
    75.  
    76. //删除
    77. BiTree DeleteQueue(Queue &a,BiTree x){
    78.     if(a.front == a.rear && a.tag == 0){
    79.         printf("当前队列已空！");
    80.     }
    81.     else{
    82.         x = a.data[a.front];
    83.         a.tag = 0;  //删除队列tag置0
    84.         a.front = (a.front + 1) % MAXSIZE;  //front指针+1
    85.         return x;
    86.     }  
    87. }
    88. BiTree DeleteSqstack(Sqstack &a, BiTree x){
    89.     if(a.top == -1){
    90.         printf("当前栈已空！");
    91.     }
    92.     else{
    93.         x = a.data[a.top];
    94.         a.top = a.top - 1;
    95.         return x;
    96.     }  
    97. }
    98.  
    99. //前序序列建立二叉树
    100. void CreateBiTree(BiTree &T){
    101.     ElemType ch;
    102.     scanf("%c", &ch);
    103.     if (ch == '#')
    104.         T = NULL;  //保证是叶结点
    105.     else{
    106.         T = (BiTree)malloc(sizeof(BiTNode));
    107.         T->data = ch;  //生成结点
    108.         CreateBiTree(T->lchild);  //构造左子树
    109.         CreateBiTree(T->rchild);  //构造右子树    
    110.     }
    111. }
    112.  
    113. //求树的结点数（递归）
    114. int Number_Node(BiTree T){
    115.     if(T==NULL)
    116.         return 0;
    117.     else{
    118.         return Number_Node(T->lchild) + Number_Node(T->rchild) + 1;
    119.     }
    120. }
    121.  
    122. //求树的层数（递归）
    123. int Depth(BiTree T){
    124.     if(T==NULL)
    125.         return 0;
    126.     else{
    127.         return (Depth(T->lchild) >= Depth(T->rchild)) ? Depth(T->lchild) + 1 : Depth(T->rchild) + 1;
    128.     }
    129. }
    130.  
    131. //查找结点，并说明它在第几层
    132. BiTree Search(BiTree T, char a, int level){
    133.     if(T == NULL)
    134.         return NULL;
    135.     else if(T->data == a){
    136.         printf("查找成功！元素在第%d层\n",level);
    137.         return T;
    138.     }
    139.     else{
    140.         Search(T->lchild, a, level + 1);
    141.         Search(T->rchild, a, level + 1);
    142.     }
    143. }
    144.  
    145. //前序遍历（递归算法）
    146. void PreOrderTraverse(BiTree T){
    147. 	if (T!=NULL){
    148. 		printf("%c", T->data);
    149. 		PreOrderTraverse(T->lchild);
    150. 		PreOrderTraverse(T->rchild);
    151. 	}
    152. }
    153. //前序遍历（非递归算法）
    154. void PreOrderTraverse2(BiTree T){
    155.     BiTree p = T; //p是遍历指针
    156.     Sqstack S;
    157.     InitStack(S);
    158.     while(p != NULL|| !IsStackEmpty(S)){
    159.         if(p){
    160.             printf("%c", p->data);
    161.             InsertSqstack(S, p);
    162.             p = p->lchild;
    163.         }
    164.         else{
    165.             p = DeleteSqstack(S, p);
    166.             p = p->rchild;
    167.         }
    168.     }
    169. }
    170.  
    171. //中序遍历（递归算法）
    172. void InOrderTraverse(BiTree T){
    173. 	if (T!=NULL){
    174. 		InOrderTraverse(T->lchild);
    175.         printf("%c", T->data);
    176. 		InOrderTraverse(T->rchild);
    177. 	}
    178. }
    179. //中序遍历（非递归算法）
    180. void InOrderTraverse2(BiTree T){
    181.     BiTree p = T; //p是遍历指针
    182.     Sqstack S;
    183.     InitStack(S);
    184.     while(p||!IsStackEmpty(S)){
    185.         if(p){
    186.             InsertSqstack(S, p);
    187.             p = p->lchild;
    188.         }
    189.         else{
    190.             p = DeleteSqstack(S, p);
    191.             printf("%c", p->data);
    192.             p = p->rchild;
    193.         }
    194.     }
    195. }
    196.  
    197. //后序遍历（递归算法）
    198. void PostOrderTraverse(BiTree T){
    199. 	if (T!=NULL){
    200. 		PostOrderTraverse(T->lchild);
    201. 		PostOrderTraverse(T->rchild);
    202.         printf("%c", T->data);
    203. 	}
    204. }
    205. //后序遍历（非递归算法）
    206. void PostOrderTraverse2(BiTree T){
    207.     Sqstack S;
    208.     InitStack(S);
    209.     BiTree p = T;
    210.     BiTree r = NULL;
    211.     while(p||!IsStackEmpty(S)){
    212.         if(p){
    213.             InsertSqstack(S, p);
    214.             p = p->lchild;
    215.         }
    216.         else{
    217.             p = S.data[S.top];  //读栈顶元素（但不出栈）
    218.             if(p->rchild&&p->rchild!=r){
    219.                 p = p->rchild;
    220.             }
    221.             else{
    222.                 p = DeleteSqstack(S, p);
    223.                 printf("%c", p->data);
    224.                 r = p;
    225.                 p = NULL;
    226.             }
    227.         }
    228.     }
    229. }
    230.  
    231. //层次遍历
    232. void LevelOrder(BiTree T){
    233.     Queue q;
    234.     InitQueue(q);
    235.     BiTree p = T;
    236.     InsertQueue(q, p);
    237.     while(!IsQueueEmpty(q)){
    238.         p = DeleteQueue(q, p);
    239.         printf("%c", p->data);
    240.         if(p->lchild!=NULL)
    241.             InsertQueue(q, p->lchild);
    242.         if(p->rchild!=NULL)
    243.             InsertQueue(q, p->rchild);
    244.     }
    245. }
    246.  
    247. int main(){
    248.     BiTree T;
    249.     printf("输入二叉树的前序序列，#代表空子树:\n");
    250.     CreateBiTree(T);
    251.     printf("二叉树创建成功！\n");
    252.     printf("二叉树的前序遍历序列是：");
    253.     PreOrderTraverse(T);
    254.     printf("\n");
    255.     printf("二叉树的中序遍历序列是：");
    256.     InOrderTraverse(T);
    257.     printf("\n");
    258.     printf("二叉树的后序遍历序列是：");
    259.     PostOrderTraverse(T);
    260.     printf("\n");
    261.     printf("二叉树的层次遍历序列是：");
    262.     LevelOrder(T);
    263.     printf("\n");
    264.     Search(T, 'D', 1);  //第1个结点在第1层
    265.     printf("二叉树的元素个数是：%d\n", Number_Node(T));
    266.     printf("二叉树的深度是：%d\n", Depth(T));
    267.  
    268.     printf("二叉树的前序遍历序列（非递归）是：");
    269.     PreOrderTraverse2(T);
    270.     printf("\n");
    271.     printf("二叉树的中序遍历序列（非递归）是：");
    272.     InOrderTraverse2(T);
    273.     printf("\n");
    274.     printf("二叉树的后序遍历序列（非递归）是：");
    275.     PostOrderTraverse2(T);
    276.     printf("\n");
    277.     return 0;
    278. }

    输出：

    1. 输入二叉树的前序序列，#代表空子树:
    2. ABD##E##C##
    3. 二叉树创建成功！
    4. 二叉树的前序遍历序列是：ABDEC
    5. 二叉树的中序遍历序列是：DBEAC
    6. 二叉树的后序遍历序列是：DEBCA
    7. 二叉树的层次遍历序列是：ABCDE
    8. 查找成功！元素在第3层
    9. 二叉树的元素个数是：5
    10. 二叉树的深度是：3
    11. 二叉树的前序遍历序列（非递归）是：ABDEC
    12. 二叉树的中序遍历序列（非递归）是：DBEAC
    13. 二叉树的后序遍历序列（非递归）是：DEBCA
  • 相关阅读:
    APS计划排程结果的量化评价
    电脑截图怎么转换成文字？学会这个方法，轻松实现
    前端三剑客：html、css、javascript
    教育类《中学政史地》收稿方向-投稿邮箱
    Spring Boot
    在Spring Boot中使用Thymeleaf开发Web页面
    uniapp的async、await用法介绍
    win10+Android（华为）系统原生日历同步方案+Sol日历桌面显示
    pytest allure 生成报告过程
    深度学习入门(6) - 3DV 三维视觉
  • 原文地址：https://blog.csdn.net/qq_54708219/article/details/133581706