详细了解C语言二叉树的建立与遍历

作者:LuckyLazyPig 时间:2021-08-17 10:24:01 

这里给一个样例树:

详细了解C语言二叉树的建立与遍历

代码:


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/*    二叉树的二叉链表结点结构定义     */
typedef struct BiTNode
{
   char data;
   struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree T=NULL;
/*    先序遍历建立一个二叉树    */
void Create (BiTree *T)       //    二级指针改变地址的地址
{
   char ch;
   scanf("%c",&ch);
   if(ch=='#')
       *T=NULL;
   else
   {
       *T=(BiTree)malloc(sizeof(BiTNode));
       if(!*T)
           return ;
       else
       {
           (*T)->data=ch;
           Create(&(*T)->lchild);
           Create(&(*T)->rchild);
       }
   }
}
/*    二叉树的前序递归遍历算法    */
void PreOrderTraverse(BiTree T)
{
   if(T==NULL)
       return ;
   printf("%c ",T->data);
   PreOrderTraverse(T->lchild);
   PreOrderTraverse(T->rchild);
}
/*    二叉树的中序递归遍历算法    */
void InOrderTraverse(BiTree T)
{
   if(T==NULL)
       return ;
   InOrderTraverse(T->lchild);
   printf("%c ",T->data);
   InOrderTraverse(T->rchild);
}
/*    二叉树的后序递归遍历算法    */
void PostOrderTraverse(BiTree T)
{
   if(T==NULL)
       return ;
   PostOrderTraverse(T->lchild);
   PostOrderTraverse(T->rchild);
   printf("%c ",T->data);
}
int main()
{
   printf("请按先序遍历的结果输入树,例如:ABDH#K###E##CFI###G#J##\n");
   Create(&T);
   printf("先序遍历的结果为:\n");
   PreOrderTraverse(T);
   printf("\n");
   printf("中序遍历的结果为:\n");
   InOrderTraverse(T);
   printf("\n");
   printf("后序遍历的结果为:\n");
   PostOrderTraverse(T);
   printf("\n");
   return 0;
}

输出结果如下

详细了解C语言二叉树的建立与遍历

PS:下面是一个用C++里面的取引用代替了二级指针


#include<bits/stdc++.h>
using namespace std;
/*    二叉树的二叉链表结点结构定义     */
typedef struct BiTNode
{
   char data;
   struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree T=NULL;
/*    先序遍历建立一个二叉树    */
void Create (BiTree &T)        //    C++取引用
{
   char ch;
   scanf("%c",&ch);
   if(ch=='#')
       T=NULL;
   else
   {
       T=(BiTree)malloc(sizeof(BiTNode));
       if(!T)
           return ;
       else
       {
           T->data=ch;
           Create(T->lchild);
           Create(T->rchild);
       }
   }
}
/*    二叉树的前序递归遍历算法    */
void PreOrderTraverse(BiTree T)
{
   if(T==NULL)
       return ;
   printf("%c ",T->data);
   PreOrderTraverse(T->lchild);
   PreOrderTraverse(T->rchild);
}
/*    二叉树的中序递归遍历算法    */
void InOrderTraverse(BiTree T)
{
   if(T==NULL)
       return ;
   InOrderTraverse(T->lchild);
   printf("%c ",T->data);
   InOrderTraverse(T->rchild);
}
/*    二叉树的后序递归遍历算法    */
void PostOrderTraverse(BiTree T)
{
   if(T==NULL)
       return ;
   PostOrderTraverse(T->lchild);
   PostOrderTraverse(T->rchild);
   printf("%c ",T->data);
}
int main()
{
   printf("请按先序遍历的结果输入树,例如:ABDH#K###E##CFI###G#J##\n");
   Create(T);
   printf("先序遍历的结果为:\n");
   PreOrderTraverse(T);
   printf("\n");
   printf("中序遍历的结果为:\n");
   InOrderTraverse(T);
   printf("\n");
   printf("后序遍历的结果为:\n");
   PostOrderTraverse(T);
   printf("\n");
   return 0;
}

PS:遍历的PLus版,想要的自取。


#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int cmax=1e2+5;
typedef struct BiTNode
{
char data;
struct BiTNode *lchild ,*rchild;
}BiTNode,*BiTree;
void CreateBiTree (BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return ;
}
void PreOrder(BiTree T)
{
if(T)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree T)
{
if(T)
{
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);
}
}
void PostOrder(BiTree T)
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);
}
}
//   非递归中序遍历
void InOrderTraverse(BiTree T)
{
stack<BiTree> S;
BiTree p;
S.push(T);
while(!S.empty())
{
p=new BiTNode;
while((p=S.top())&&p)
   S.push(p->lchild);
S.pop();
if(!S.empty())
{
p=S.top();
S.pop();
cout<<p->data<<"  ";
S.push(p->rchild);
}
}
}
//    先序非递归遍历
void PreOrder_Nonrecursive(BiTree T)
{
stack<BiTree> S;
BiTree p;
S.push(T);
while(!S.empty())
{
while((p=S.top())&&p)
{
cout<<p->data<<"  ";
S.push(p->lchild);
}
S.pop();
if(!S.empty())
{
p=S.top();
S.pop();
S.push(p->rchild);
}
}
}
int visit(BiTree T)
{
if(T)
{
printf("%c ",T->data);
return 1;
}
else
return 0;
}
//    非递归层次遍历
void  LeverTraverse(BiTree T)
{
queue <BiTree> Q;
BiTree p;
p=T;
if(visit(p)==1)
    Q.push(p);
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(visit(p->lchild)==1)
    Q.push(p->lchild);
if(visit(p->rchild)==1)
    Q.push(p->rchild);
}
}
//主函数
int main()
{
BiTree T;
char j;
int flag=1;
printf("本程序实现二叉树的操作。\n");
   printf("叶子结点以#表示。\n");
   printf("可以进行建立二叉树,递归先序、中序、后序遍历,非递归先序、中序遍历及非递归层序遍历等操作。\n");
   printf("请建立二叉树。\n");
   printf("建树将以三个空格后回车结束。\n");
   printf("例如:1 2 3 4 5 6       (回车)\n\n");
CreateBiTree(T);           //初始化队列
   getchar();
   printf("\n");
   printf("请选择: \n");
   printf("1.递归先序遍历\n");
   printf("2.递归中序遍历\n");
   printf("3.递归后序遍历\n");
   printf("4.非递归中序遍历\n");
   printf("5.非递归先序遍历\n");
   printf("6.非递归层序遍历\n");
   printf("0.退出程序\n");
   while(flag)
   {
       scanf(" %c",&j);
       switch(j)
       {
           case '1':if(T)
           {
               printf("递归先序遍历二叉树:");
               PreOrder(T);
               printf("\n");
           }
           else printf("二叉树为空!\n");
           break;
           case '2':if(T)
           {
               printf("递归中序遍历二叉树:");
               InOrder(T);
               printf("\n");
           }
           else printf("二叉树为空!\n");
           break;
           case '3':if(T)
           {
               printf("递归后序遍历二叉树:");
               PostOrder(T);
               printf("\n");
           }
           else printf("二叉树为空!\n");
           break;
           case '4':if(T)
           {
               printf("非递归中序遍历二叉树:");
               InOrderTraverse(T);
               printf("\n");
           }
           else printf("二叉树为空!\n");
           break;
           case '5':if(T)
           {
               printf("非递归先序遍历二叉树:");
               PreOrder_Nonrecursive(T);
               printf("\n");
           }
           else printf("二叉树为空!\n");
           break;
           case '6':if(T)
           {
               printf("非递归层序遍历二叉树:");
               LeverTraverse(T);
               printf("\n");
           }
           else printf("二叉树为空!\n");
           break;
           default:flag=0;printf("程序运行结束,按任意键退出!\n");
       }
   }
}

详细了解C语言二叉树的建立与遍历

来源:https://blog.csdn.net/weixin_45882303/article/details/107941789

标签:C语言,二叉树,遍历
0
投稿

猜你喜欢

  • javafx tableview鼠标触发更新属性详解

    2022-01-24 23:47:32
  • 使用java springboot设计实现的图书管理系统(建议收藏)

    2023-11-25 00:54:49
  • java多线程的同步方法实例代码

    2022-02-16 19:30:47
  • MyBatis分页插件PageHelper的使用与原理

    2021-06-15 09:24:35
  • C#导出生成excel文件的方法小结(xml,html方式)

    2023-10-03 16:32:26
  • C语言之如何求三次方根

    2022-04-30 03:13:52
  • Java JDK动态代理(AOP)用法及实现原理详解

    2021-11-14 16:45:21
  • Android定时器和Handler用法实例分析

    2022-11-09 22:18:08
  • Android为Tiny4412设备驱动在proc目录下添加一个可读版本信息的文件

    2022-09-24 05:37:20
  • java虚拟机钩子关闭函数addShutdownHook的操作

    2021-10-18 00:58:25
  • Java数据结构学习之二叉树

    2023-04-25 12:08:27
  • SpringCloud Eureka应用全面介绍

    2022-08-23 17:43:26
  • Spring注解@DependsOn解析

    2022-01-11 08:20:35
  • SpringBoot项目Jar包如何瘦身部署的实现

    2021-09-21 05:37:51
  • Android判断11位手机号码的方法(正则表达式)

    2022-03-06 03:17:43
  • C#实现聊天窗体以及抖动

    2021-06-07 10:40:50
  • 浅谈maven的jar包和war包区别 以及打包方法

    2022-07-20 20:14:44
  • Android自定义View仿QQ运动步数效果

    2021-06-25 00:11:37
  • C#数字图像处理之图像缩放的方法

    2023-02-12 11:09:29
  • java获取当前时间并格式化代码实例

    2021-10-06 17:06:16
  • asp之家 软件编程 m.aspxhome.com