详细了解C语言二叉树的建立与遍历
程序员文章站
2022-03-24 08:20:46
目录这里给一个样例树：代码：#include #include #include /* 二叉树的二...
这里给一个样例树：
代码：
#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;
}
输出结果如下
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");
}
}
}
总结
本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注的更多内容！
下一篇： 浅析java中Pair和Map的区别