建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历。
#include
#include
using namespace std;
#define MAXSIZE 100
typedef struct BiNode
{
char data;
struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
void Create(BiTree &T)//用先序遍历的顺序建立二叉链表（递归方法）
{
char ch;
cin>>ch;
if(ch=='#')
T=NULL;
else
{
T=new BiNode;
T->data=ch;
Create(T->lchild);
Create(T->rchild);
}
}
void PreOrder(BiTree &T)//先序遍历二叉树（递归）
{
if(T)
{
coutdata<<" ";
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree &T)//中序遍历二叉树（递归）
{
if(T)
{
InOrder(T->lchild);
coutdata<<" ";
InOrder(T->rchild);
}
}
void PostOrder(BiTree &T)//后序遍历二叉树（递归）
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
coutdata<<" ";
}
}
望采纳~~~
建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历，程序操作如下:
#include "stdio.h"#include "stdlib.h"
#define STACK_INIT_SIZE 10 //栈的初始长度
#define STACKINCREMENT 5 //栈的追加长度
typedef struct bitree{char data;struct bitree *lchild,*rchild;}bitree; //二叉树结点定义typedef struct {bitree **base;
bitree **top;int stacksize;}sqstack; // 链栈结点定义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针
//建立一个空栈int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //栈底指向开辟空间if(!s->base) exit(1); //抛出异常s->top=s->base; //栈顶=栈尾 表示栈空
s->stacksize=STACK_INIT_SIZE; //栈长度为开辟空间大小return 1;}//进栈int push(sqstack *s,bitree *e) {if(s->top-s->base>=s->stacksize) //如果栈满 追加开辟空间
{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s->base) exit(1); //抛出异常s->top=s->base+s->stacksize; //感觉这一句没用s->stacksize+=STACKINCREMENT;}*(s->top)=e;s->top++; //进栈 栈顶后移
return 1;}//出栈int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //栈空 返回0--s->top;*e=*(s->top); //栈顶前移 取出栈顶元素给ereturn 1;}
//取栈顶int gettop(sqstack *s,bitree **e) //去栈顶元素 注意top指向的是栈顶的后一个{if(s->top==s->base) return 0; //所以 s->top-1*e=*(s->top-1);
return 1;}/*------------------------非递归-----先序建立二叉树----------------------------------*/bitree *createprebitree()
{sqstack m;initstack(&m);while(h||m.base!=m.top){if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}else{pop(&m,&h);
h=h->rchild;}}}/*------------------------非递归-----中序输出二叉树----------------------------*/void inordertraverse(bitree *h){sqstack m;initstack(&m);while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}else {pop(&m,&h);printf("%c",h->data);h=h->rchild;}}}/*---------------------非递归----后序遍历二叉树----------------------------------*/void postordertraverse(bitree *h){sqstack m;initstack(&m);while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}else {bitree *r; //使用r结点表示访问了右子树 代替标志域gettop(&m,&h);if(h->rchild&&h->rchild!=r)
{h=h->rchild;push(&m,h);h=h->lchild;}else{pop(&m,&h);
printf("%c",h->data);r=h;h=NULL;}}}
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //栈的初始长度
#define STACKINCREMENT 5 //栈的追加长度
typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉树结点定义
typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 链栈结点定义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针
//建立一个空栈
int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //栈底指向开辟空间
if(!s->base) exit(1); //抛出异常
s->top=s->base; //栈顶=栈尾 表示栈空
s->stacksize=STACK_INIT_SIZE; //栈长度为开辟空间大小
return 1;
}
//进栈
int push(sqstack *s,bitree *e)
{if(s->top-s->base>=s->stacksize) //如果栈满 追加开辟空间
{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s->base) exit(1); //抛出异常
s->top=s->base+s->stacksize; //感觉这一句没用
s->stacksize+=STACKINCREMENT;}
*(s->top)=e;s->top++; //进栈 栈顶后移
return 1;
}
//出栈
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //栈空 返回0
--s->top;*e=*(s->top); //栈顶前移 取出栈顶元素给e
return 1;}
//取栈顶
int gettop(sqstack *s,bitree **e) //去栈顶元素 注意top指向的是栈顶的后一个
{if(s->top==s->base) return 0; //所以 s->top-1
*e=*(s->top-1);
return 1;
}
/*------------------------非递归-----先序建立二叉树----------------------------------*/
bitree *createprebitree()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=malloc(sizeof(bitree)); //加上这一句为s 初始化开辟空间
ch=getchar();
if(ch!='#'&&ch!='\n') /* 输入二叉树先序顺序 是以完全二叉树的先序顺序
不是完全二叉树的把没有的结点以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根节点进栈
while((ch=getchar())!='\n') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)); // 法
q->data=ch; //
if(p==*(s->top-1)) p->lchild=q; // 核
else p->rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL; // 的
else p->rchild=NULL; //
pop(s,&p);} // 步
//
} // 骤
return ht;
}
else return NULL;
}
/*--------------------------递归---------先序建立二叉树-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序输入二叉树中的结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示二叉树
char ch;
scanf("%c",&ch);
if(ch=='#') *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)->data=ch; //生成根结点
CreateBiTree(&(*T)->lchild); //构造左子树
CreateBiTree(&(*T)->rchild); //构造右子树
}
}
/*--------------------------非递归-------中序建立二叉树-------------------------------*/
/*--------------------------递归---------中序建立二叉树-------------------------------*/
/*--------------------------非递归-------后序建立二叉树-------------------------------*/
/*--------------------------递归---------后序建立二叉树-------------------------------*/
/*-----------------------非递归------先序输出二叉树------------------------------*/
void preordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}
else{pop(&m,&h);
h=h->rchild;}
}
}
/*------------------------非递归-----中序输出二叉树----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}
else {
pop(&m,&h);
printf("%c",h->data);
h=h->rchild;
}
}
}
/*---------------------非递归----后序遍历二叉树----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h->lchild;}
else {
bitree *r; //使用r结点表示访问了右子树 代替标志域
gettop(&m,&h);
if(h->rchild&&h->rchild!=r)
{h=h->rchild;
push(&m,h);
h=h->lchild;}
else{pop(&m,&h);
printf("%c",h->data);
r=h;h=NULL;}
}
}
}
//层次遍历二叉树 用队列 哈哈以后做
/*-------------------------------主过程-------------------------------*/
int main()
{bitree *ht;
printf("先序非递归建立一个二叉树:");
if((ht=createprebitree())!=NULL) //非递归建立
//CreateBiTree(&ht);
//if(ht!=NULL) //递归建立
{
printf("先序遍历输出二叉树:");
preordertraverse(ht);
putchar('\n');
printf("中序遍历输出二叉树:");
inordertraverse(ht);
putchar('\n');
printf("后序遍历输出二叉树:");
postordertraverse(ht);
putchar('\n');
}
else printf("空二叉树\n");
}
这是先序递归和非递归建立二叉树 和 先、中、后 的遍历输出
建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历。
财源滚滚随春到 喜气洋洋伴福来 横批：财源广进 淘你喜欢，淘你所爱，快购吧
二叉树的定义是递归的。用递归就可以实现了。
建立二叉树,前，中，后遍历：
bitree_node* creat_bitree(bitree_node *r)
{
ch=getchar();
if(ch=='#') return NULL;
else
{
r=new bitree_node;
r->data=ch;
r->lchild=creat_bitree(r->lchild);
r->rchild=creat_bitree(r->rchild);
}
return r;
}
void preorder(bitree_node *r)
{
bitree_node* p=r;
if(p==NULL) return;
else
{
cout<<p->data;
preorder(p->lchild);
preorder(p->rchild);
}
}
void inorder(bitree_node *r)
{
bitree_node* p=r;
if(p==NULL) return;
else
{
inorder(p->lchild);
cout<<p->data;
inorder(p->rchild);
}
}
void postorder(bitree_node *r)
{
bitree_node* p=r;
if(p==NULL) return;
else
{
postorder(p->lchild);
postorder(p->rchild);
cout<<p->data;
}
}
#include "stdio.h"
#include "malloc.h"
#define ELEMTYPE char
typedef struct BiTNode
{ ELEMTYPE data;
struct BiTNode *lchild,*rchild;
} BiTNode;
BiTNode *bulid() /*建树*/
{ BiTNode *q;
BiTNode *s[20];
int i,j;
char x;
printf("请按顺序输入二叉树的结点以输入0和*号结束\n");
printf("请输入你要输入的为第几个结点i=\n");
scanf("%d",&i);
printf("请输入你要输入该结点的数为x=");
getchar();
scanf("%c",&x);
while(i!=0&&x!='*')
{q=(BiTNode*)malloc(sizeof(BiTNode));
q->data=x;
q->rchild=NULL;
q->lchild=NULL;
s[i]=q;
if(i!=1)
{ j=i/2;
if(i%2==0)
s[j]->lchild=q;
else
s[j]->rchild=q;
}
printf("请输入你要输入的为第几个结点x=\n");
scanf("%d",&i);
printf("请输入你要输入该结点的数x=");
getchar();
scanf("%c",&x);
}
return s[1];
}
void preoder(BiTNode *bt) /*先序遍历*/
{ if(bt!=NULL)
{
printf("%c\n",(bt->data));
preoder(bt->lchild);
preoder(bt->rchild);
}
}
void InOrder(BiTNode *bt) /*中序遍历*/
{ if(bt!=NULL)
{ InOrder(bt->lchild);
printf("%c\n",bt->data);
InOrder(bt->rchild);
}
}
void postOrder(BiTNode *bt) /*后序遍历*/
{ if(bt!=NULL)
{ postOrder(bt->lchild);
postOrder(bt->rchild);
printf("%c\n",bt->data);
}
}
main()
{ int a;
BiTNode *bt;
bt=bulid();
k1: printf("需要先序遍历输出请输入1，中序遍历请输入2，后序遍历请输入3,结束输入0:");
scanf("%d",&a);
switch(a)
{
case(1): preoder(bt); goto k1;
case(2): InOrder(bt); goto k1;
case(3): postOrder(bt); goto k1;
case(0): break;
}
}
3
另外,虚机团上产品团购,超级便宜
建立任意二叉树的二叉链表存储,并对其进行先序、中序、后序遍历。_百度...
答：void CreateBiTree(bitree **T) { //按先序次序输入二叉树中的结点的值（一个字符），空格字符表示空树，//构造二叉链表表示二叉树 char ch;scanf("%c",&ch);if(ch=='#') *T=NULL;else{
用C语言定义二叉树的二叉链表存储结构,完成二叉树的建立,先序中序后...
答：include<malloc.h> typedef int ElemType;typedef struct LNode{ ElemType data;struct LNode *lchild,*rchild;}LNode,*TLNode;void create(TLNode * Tree){ //创建 ElemType e;scanf("%d",&e);if(e==0)Tree=NULL;else{ (*Tree)=(TLNode)malloc(sizeof(LNode));(*Tree)->data=e;pr...
二叉树的遍历
答：对任意给定的二叉树(顶点数自定)建立它的二叉链表存储结构,并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三种遍历,输出三种遍... 对任意给定的二叉树(顶点数自定)建立它的二叉链表存储结构,并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈...
...序和后序遍历这棵二叉树,要求以二叉链表作为存储结构
答：void Create(BiTree &T)//用先序遍历的顺序建立二叉链表（递归方法）{ char ch;cin>>ch;if(ch=='#')T=NULL;else { T=new BiNode;T->data=ch;Create(T->lchild);Create(T->rchild);} } void PreOrder(BiTree &T)//先序遍历二叉树（递归）{ if(T){ cout<<T->data<<" ";Pre...
建立二叉链表存储下图所示的二叉树,并用递归算法对其进行前序、中序...
答：char data;struct bitnode *lchild,*rchild;}bitnode,*bitree;//二叉树节点类型和节点指针类型 bitree create()//先序创建 { bitree root=NULL;char c;scanf("%c",&c);fflush(stdin);if(c=='#')return NULL;else { root=(bitnode*)malloc(sizeof(bitnode));root->data=c;root->lchild=...
...建立一棵含有n个结点的二叉树,采用二叉链表存储;
答：;} } void main(){ printf("构建一个二叉树（结点数为n)：\n");root=create(root);printf("前序遍历二叉树：\n");preorder(root);printf("\n");printf("中序遍历二叉树：\n");inorder(root);printf("\n");printf("后序遍历二叉树：\n");postorder(root);printf("\n");} ...
用C语言建立一棵二叉树,使用二杈链表存储,对其进行后续遍历,输出后序...
答：include<iostream.h> include<stdlib.h> define Maxsize 100 typedef int datatype;typedef struct node { datatype data;struct node* lchild;struct node* rchild;}BTNode;void CreatBTNode(BTNode *&b,char * str){ BTNode *p,*st[Maxsize];int top=-1;p=NULL;b=NULL;int j=0,k;char ...
设二叉树以二叉链表存储,试设计算法,实现二叉树的层序遍历。_百度知 ...
答：按层次遍历算法如下：include <iostream> using namespace std;typedef struct treenode { //树结点结构 int data;struct treenode *left;struct treenode *right;}TreeNode;typedef struct stack{ //栈结点结构 TreeNode *node;struct stack *next;}STACK;void Traversal(TreeNode *root){ STACK *...
运用C++如何使用二叉链表存储二叉树,遍历输出叶子节点路径,递归输出...
答：构造的二叉树结构如下：运行结果如下：代码如下：include <iostream>#include <vector>using namespace std;typedef struct tnode //定义树节点结构{int val;tnode* left;tnode* right;tnode(int x=0):val(x),left(NULL),right(NULL){}//默认构造函数}TreeNode,*pTreeNode;void getPath(Tree...
二叉链表存储结构,实现二叉树的遍历
答：前几天写的，输入二叉树的广义表形式，建立二叉树的链式存储。输出的是中序。有注释，看懂了应该其他的都能写了吧。#include<stdio.h> include<stdlib.h> int n=0; //全局变量 struct tree //二叉树结构体 { char data;struct tree *lc;struct tree *rc;};tree *creat(char a[]) ...
