用二叉链表作为存储结构，建立二叉树，对二叉树进行前序、中序、后序遍历，在对建立的二叉树进行中序线索
#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); //栈顶前移 取出栈顶元素给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!='
') /* 输入二叉树先序顺序 是以完全二叉树的先序顺序
不是完全二叉树的把没有的结点以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根节点进栈
while((ch=getchar())!='
') // 算
{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('
');
printf("中序遍历输出二叉树:");
inordertraverse(ht);
putchar('
');
printf("后序遍历输出二叉树:");
postordertraverse(ht);
putchar('
');
}
else printf("空二叉树
");
}
这是先序递归和非递归建立二叉树 和 先、中、后 的遍历输出
#include "stdafx.h"
#include "stdlib.h"
#define MAX_NODE 100
#define NODE_COUNT1 8
#define NODE_COUNT2 15
int TreeValue0[NODE_COUNT1][2] = {{'0',0},{'D',1},{'B',2},{'F',3},{'A',4},{'C',5},{'E',6},{'G',7}};
int TreeValue1[NODE_COUNT1][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7}};
int TreeValue2[NODE_COUNT2][2] = {{'0',0},{'A',1},{'B',2},{'C',3},{'D',4},{'E',5},{'F',6},{'G',7},{'H',8},{'I',9},{'J',10},{'K',11},{'L',12},{'M',13},{'N',14}};
struct BTree
{
int data;
int order;
BTree *lchild;
BTree *rchild;
};
void Swap(int *p1,int *p2)
{
int t;
t = *p1;
*p1 = *p2;
*p2 = t;
}
/*
function CreateBTree()功能：创建一颗二叉树，并返回一个指向其根的指针
*/
BTree *CreateBTree(int data[][2],int n)
{
BTree *Addr[MAX_NODE];
BTree *p,
*head;
int nodeorder,//节点序号
noderoot, //节点的双亲
i;
if(n>MAX_NODE)
{
printf("参数错误！\n");
return(0);
}
for(i=1;i<=n;i++)
{
p = (BTree *)malloc(sizeof(BTree));
if(p==NULL)
{
printf("内存溢出错误！\n");
return(0);
}
else
{
p->data = data[i][0];
p->lchild = NULL;
p->rchild = NULL;
nodeorder = data[i][1];
p->order = nodeorder;
Addr[nodeorder] = p;
if(nodeorder>1)
{
noderoot = nodeorder/2;
if(nodeorder %2 == 0)
Addr[noderoot]->lchild = p;
else
Addr[noderoot]->rchild = p;
}
else
head = p;
printf("BTree[%d] = %c\t",p->order,p->data);
}
//free(p);
}
return(head);
}
/*
function FirstOrderAccess0()功能：实现二叉树的前序遍历
二叉树前序遍历的思想：
从根节点开始，沿左子树一直走到没有左孩子的节点为止，
依次访问所经过的节点，同时所经[节点]的地址进栈；
当找到没有左孩子的节点时，从栈顶退出该节点的双亲的
右孩子，此时，此节点的左子树已访问完毕；
在用上述方法遍历该节点的右子树，如此重复到栈空为止。
*/
void FirstOrderAccess0(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
top = top+1;
stack[top] = p;
p = p->lchild;//继续搜索节点P的左子树
}
if(top!=0)
{
p = stack[top];
top = top-1;
p = p->rchild;//继续搜索节点P的右子树
}
}while((top!=0)||(p!=NULL));
}
/*
function FirstOrderAccess1()功能：实现二叉树的前序遍历
二叉树前序遍历的思想：
从根节点开始，沿左子树一直走到没有左孩子的节点为止，
依次访问所经过的节点，同时所经[节点的非空右孩子]进栈；
当找到没有左孩子的节点时，从栈顶退出该节点的双亲的
右孩子，此时，此节点的左子树已访问完毕；
在用上述方法遍历该节点的右子树，如此重复到栈空为止。
*/
void FirstOrderAccess1(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
printf("BTree[%d] = %c\t",p->order,p->data);
if(p->rchild!=NULL)
stack[++top] = p->rchild;
p = p->lchild;
}
if(top!=0)
p = stack[top--];
}while((top>0)||(p!=NULL));
}
/*
function MiddleOrderAccess()功能：实现二叉树的中序遍历
二叉树中序遍历的思想：
从根节点开始，沿左子树一直走到没有左孩子的节点为止，
并将所经[节点]的地址进栈；
当找到没有左孩子的节点时，从栈顶退出该节点并访问它，
此时，此节点的左子树已访问完毕；
在用上述方法遍历该节点的右子树，如此重复到栈空为止。
*/
void MiddleOrderAccess(BTree * header)
{
BTree * stack[MAX_NODE];
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
stack[++top] = p;//节点P进栈
p = p->lchild; //继续搜索其左子树
}
if(top!=0)
{
p = stack[top--];//节点P出栈
printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
p = p->rchild;//继续搜索其左子树
}
}while((top!=0)||(p!=NULL));
}
/*
function LastOrderAccess()功能：实现二叉树的后序遍历
二叉树后序遍历的思想：
从根节点开始，沿左子树一直走到没有左孩子的节点为止，
并将所经[节点]的地址第一次进栈；
当找到没有左孩子的节点时，此节点的左子树已访问完毕；
从栈顶退出该节点，判断该节点是否为第一次进栈，如是，再
将所经[节点]的地址第二次进栈，并沿该节点的右子树一直走到
没有右孩子的节点为止，如否，则访问该节点；此时，该节点的
左、右子树都已完全遍历，且令指针p = NULL;
如此重复到栈空为止。
*/
void LastOrderAccess(BTree * header)
{
BTree * stack[MAX_NODE];//节点的指针栈
int count[MAX_NODE];//节点进栈次数数组
BTree *p;
int top;
top = 0;
p = header;
do
{
while(p!=NULL)
{
stack[++top] = p;//节点P首次进栈
count[top] = 0;
p = p->lchild; //继续搜索节点P的左子树
}
p = stack[top--];//节点P出栈
if(count[top+1]==0)
{
stack[++top] = p;//节点P首次进栈
count[top] = 1;
p = p->rchild; //继续搜索节点P的左子树
}
else
{
printf("BTree[%d] = %c\t",p->order,p->data);//访问节点P
p = NULL;
}
}while((top>0));
}
/*
function IsLeafNode()功能：判断给定二叉树的节点是否是叶子节点
*/
int IsLeafNode(BTree *node)
{
if((node->lchild==NULL)&&(node->rchild==NULL))
return(1);
else
return(0);
}
/*
function PrintLeafNode()功能：输出给定二叉树的叶子节点
*/
void PrintLeafNode(BTree *header)
{
BTree * stack[MAX_NODE];//节点的指针栈
BTree *p;
int top;
p = header;
top = 0;
do
{
while(p!=NULL)
{
stack[++top] = p;
p = p->lchild;//继续搜索节点P的左子树
}
if(top!=0)
{
p = stack[top--];
if(IsLeafNode(p))
printf("LNode[%d] = %c\t",p->order,p->data);//访问叶子节点
p = p->rchild;//继续搜索节点P的右子树
}
}while(top>0||p!=NULL);
}
/*
function HasTwoChildNode()功能：判断给定二叉树的节点是否存在两个孩子节点
*/
int HasTwoChildNode(BTree *node)
{
if((node->lchild!=NULL)&&(node->rchild!=NULL))
return(1);
else
return(0);
}
/*
function SwapChildNode()功能：交换给定二叉树的所有节点的左、右孩子
*/
void SwapChildNode(BTree *header)
{
BTree * stack[MAX_NODE];//节点的指针栈
BTree *p;
int top;
p = header;
top = 0;
do
{
while(p!=NULL)
{
stack[++top] = p;
p = p->lchild;//继续搜索节点P的左子树
}
if(top!=0)
{
p = stack[top--];
if(HasTwoChildNode(p))
Swap(&p->lchild->data,&p->rchild->data);//交换节点P的左、右孩子
p = p->rchild;//继续搜索节点P的右子树
}
}while(top>0||p!=NULL);
}
int main(int argc, char* argv[])
{
BTree * TreeHeader;
printf("二叉树创建数据结果：\n");
TreeHeader = CreateBTree(TreeValue1,NODE_COUNT1-1);
//TreeHeader = CreateBTree(TreeValue2,NODE_COUNT2-1);
if (TreeHeader==0)
{
printf("二叉树创建失败！\n");
return(0);
}
else
{
printf("\n二叉树前序遍历结果：\n");
FirstOrderAccess1(TreeHeader);
printf("\n二叉树中序遍历结果：\n");
MiddleOrderAccess(TreeHeader);
printf("\n二叉树后序遍历结果：\n");
LastOrderAccess(TreeHeader);
//printf("\n二叉树的所有叶子节点：\n");
//PrintLeafNode(TreeHeader);
//SwapChildNode(TreeHeader);
//printf("\n二叉树交换孩子的结果：\n");
//MiddleOrderAccess(TreeHeader);
printf("\n程序运行完毕!\n");
return 0;
}
}
typedef struct{
int item;
*BiTree left;
*BiTree right;
}BiTree;
以上是二叉树的定义。
前序：
a_view(BiTree* t){
if(t == NULL) return;
view(t->item);
a_view(left);
a_view(right);
}
中序：
a_view(BiTree* t){
if(t == NULL) return;
a_view(left);
view(t->item);
a_view(right);
}
后序：
a_view(BiTree* t){
if(t == NULL) return;
a_view(left);
a_view(right);
view(t->item);
}
C语言编写的数据结构
答：实验一:用二叉链表作为存储结构,建立二叉树,对二叉树进行前序、后序遍历,并对建立的二叉树进行中序线索,再中序线索遍历。实验二:根据给定的权值建立哈夫曼树,进行前序遍历。/*建... 实验一:用二叉链表作为存储结构,建立二叉树,对二叉树进行前序、后序遍历,并对建立的二叉树进行中序线索,再中序线索遍历。实验...
采用二叉链表作为存储结构,完成二叉树的建立,前序、中序和后序遍历的...
答：//求二叉树叶子节点个数
用二叉链表作为存储结构,建立二叉树,对二叉树进行前序、中序、后序遍...
答：在用上述方法遍历该节点的右子树，如此重复到栈空为止。/
利用二叉链表作为存储结构建立一棵二叉树,每个结点中存放一种水果名(由...
答：其中包括一个前序的创建；前序，中序，后序的输出；还有一个前序，中序输入一棵树，确定后序，我是用队列作的，你可以先注释掉，先解决主要问题；另外就是一些诸如求高度，节点数的小方法。我这个是整形数的，你只要改成字符串类型的就可以了，别告诉我这你都不会，那我就帮不了你了。include ...
找一个Java程序:关于二叉树的建立和排序
答：从键盘接受输入(先序)，以二叉链表作为存储结构，建立二叉树(以先序来建立)结果不是唯一
...后序遍历这棵二叉树,要求以二叉链表作为存储结构
答：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->...
如何在数据结构中,以二叉链表为存储结构,建立一棵二叉树,输出其先序...
答：include <stdlib.h> include <malloc.h> struct lbtree { char data;struct lbtree *lchild,*rchild;};struct lbtree *createbtree();void preorder(struct lbtree *root);void inorder(struct lbtree *root);void postorder(struct lbtree *root);treedepth(struct lbtree *root);numberofleaf(...
建立一棵用二叉链表方式存储的二叉树,并对其进行先序遍历,打印输出结果...
答：using namespace std;class tree { public:tree(){lchild=NULL;rchild=NULL;} char data;class tree *lchild;class tree *rchild;};void build(tree *&t)//先序建树 { char c;cin>>c;if(c=='#'){ t=NULL;} else { t=new tree;t->data=c;build(t->lchild);build(t->rchild);}...
建立二叉链表存储下图所示的二叉树,并用递归算法对其进行前序、中序...
答：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=...
急!~编写一个C++语言程序,对二叉树实现操作
答：二叉树采用二叉链表作存储结构，编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；4. 将二叉树每个结点的左右子树交换位置。【数据...
