课程设计利用顺序栈遍历二叉树算法

A. 编写按层次顺序（同一层从左至右）遍历二叉树的算法

#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node
{datatype data;
struct node *lchild,*rchild;
}bitree;
bitree *Q[100];
bitree *creat()
{
bitree *root,*s;
int front,rear;
root=NULL;
char ch;
front=1;rear=0;
ch=getchar();
while(ch!='0')
{
s=NULL;
if(ch!='@')
{s=(bitree *)malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else
{
if(s&&Q[front])
if(rear%2==0)
Q[front]->lchild=s;
else
Q[front]->rchild=s;
if(rear%2==1)
front++;
}
ch=getchar();
}
return root;
}
void cengci(bitree *t)
{
bitree *Queue[100],*p;
int front=0,rear=0;
if(t)
{
p=t;
Queue[rear]=p;
rear=(rear+1)%20;
while(front!=rear)
{
p=Queue[front];
printf("%c",p->data);
front=(front+1)%100;
if(p->lchild)
{
Queue[rear]=p->lchild;
rear=(rear+1)%100;
}
if(p->rchild)
{
Queue[rear]=p->rchild;
rear=(rear+1)%20;
}
}
}
}

void main()
{struct node *tree;
tree=(bitree *)malloc(sizeof(bitree));
tree=creat();
cengci(tree);
}
遍历方法从void cengci(bitree *t) 开始的 用队列方法遍历的

B. 利用先序遍历算法建立如图所示二叉树,并对二叉树进行先序遍历.

//创建二叉树,输入先序遍历序列:ABC##DE#G##F###
//先序遍历输出节点:ABCDEGF
//作为对比参考:
//中序遍历输出节点:CBEGDFA
//后序遍历输出节点:CGEFDBA
#include<stdio.h>
#include<stdlib.h>
typedefstructNode
{
chardata;
structNode*lchild;
structNode*rchild;
}Bitree;
//用"先序遍历"算法创建二叉树
voidCreateBiTree(Bitree**bt)
{
chars;
scanf("%c",&s);//输入数据
if(s=='#')//'#'是空节点,或者称为"虚有"的节点
*bt=NULL;
else
{
*bt=(Bitree*)malloc(sizeof(Bitree));
(*bt)->data=s;
CreateBiTree(&((*bt)->lchild));
CreateBiTree(&((*bt)->rchild));
}
}
//用"先序遍历"输出节点
voidpreOrder(Bitree*ptr)
{
if(ptr!=NULL)
{
printf("%c",ptr->data);
preOrder(ptr->lchild);
preOrder(ptr->rchild);
}
}
//用"中序遍历"输出节点
voidinOrder(Bitree*ptr)
{
if(ptr!=NULL)
{
inOrder(ptr->lchild);
printf("%C",ptr->data);
inOrder(ptr->rchild);
}
}
//用"后序遍历"输出节点
voidpostOrder(Bitree*ptr)
{
if(ptr!=NULL)
{
postOrder(ptr->lchild);
postOrder(ptr->rchild);
printf("%C",ptr->data);
}
}

intmain()
{
Bitree*root;
printf("创建二叉树,输入先序遍历序列:");
CreateBiTree(&root);

printf("先序遍历输出节点:");
preOrder(root);

//以下的"中序遍历"和"后序遍历"是作为对比参考
printf("

中序遍历输出节点:");
inOrder(root);
printf("
后序遍历输出节点:");
postOrder(root);

printf("
");
return0;
}

C. 课程设计啊！！二叉树遍历问题！！！急急急啊！！！

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"conio.h"
#define LEN sizeof(struct tree)
typedef struct tree
{
char data;
struct tree *lchild,*rchild;
} ;

struct tree *creat()
{
char c;
struct tree *t;
scanf("%c",&c);
if(c==' ') return(NULL);
else
{
t=(struct tree*)malloc(LEN);
t->data=c;
t->lchild=creat();
t->rchild=creat();
return t;
}
}

void print(struct tree *t)
{
if(t!=NULL)
{
printf("%c",t->data);
print(t->lchild);
print(t->rchild);
}
}
//========NLR 先序遍历=============
void PreOrderTraverse(struct tree *t)
{
if(t)
{
printf("%c",t->data);
PreOrderTraverse(t->lchild);
PreOrderTraverse(t->rchild);
}
}
//========LNR 中序遍历===============
void InOrderTraverse(struct tree *t)
{
if(t)
{
InOrderTraverse(t->lchild);
printf("%c",t->data);
InOrderTraverse(t->rchild);
}
}
//==========LRN 后序遍历============
void PostOrderTraverse(struct tree *t)
{
if(t)
{
PostOrderTraverse(t->lchild);
PostOrderTraverse(t->rchild);
printf("%c",t->data);
}
}

main()
{
struct tree *t;
int i;
printf("Create a tree:");
t=creat();

printf("************MANU******************\n\n");
printf("1.Display the tree\n");
printf("2.PreOderTree\n");
printf("3.InOrderTree\n");
printf("4.PostOrderTre\n");
printf("0.Exit\n\n");
printf("**********************************\n\n");

do
{
printf("\nPlease input a nummer:");
scanf("%d",&i);
switch(i)
{
case 1:printf("The tree is:");
print(t);
break;
case 2:printf("The PreOderTree result is:");
PreOrderTraverse(t);
break;
case 3:printf("The InOrderTree result is:");
InOrderTraverse(t);
break;
case 4:printf("The PostOrderTree result is:");
PostOrderTraverse(t);
break;
case 0:exit(0);

}
printf("\n");
getch();
}while(i>=0&&i<=4);

}

D. 以二叉连表做存储结构，试编写按层次顺序遍历二叉树的算法

//二叉树，按层次访问
//引用如下地址的思想，设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
//http://..com/link?url=a9ltidaf-SQzCIsa
typedef struct tagMyBTree
{
int data;
struct tagMyBTree *left,*right;
}MyBTree;

void visitNode(MyBTree *node)
{
if (node)
{
printf("%d ", node->data);
}

}
void visitBTree(queue<MyBTree*> q);
void createBTree(MyBTree **tree)
{
int data = 0;
static int initdata[15] = {1,2,4,0,0,5,0,0,3,6,0,0,7,0,0};//构造成满二叉树，利于查看结果
static int i = 0;
//scanf("%d", &data);
data = initdata[i++];
if (data == 0)
{
*tree = NULL;
}
else
{
*tree = (MyBTree*)malloc(sizeof(MyBTree));
if (*tree == NULL)
{
return;
}
(*tree)->data = data;

createBTree(&(*tree)->left);

createBTree(&(*tree)->right);

}
}

void visitBTreeTest()
{
queue<MyBTree*> q;
MyBTree *tree;
createBTree(&tree);
q.push(tree);
visitBTree(q);
}

void visitBTree(queue<MyBTree*> q)
{
if (!q.empty())
{
MyBTree *t = q.front();
q.pop();
visitNode(t);
if (t->left)
{
q.push(t->left);
}
if (t->right)
{
q.push(t->right);
}

visitBTree(q);
}
}

E. 课程设计 二叉树遍历算法集成

#include"stdio.h"

#include"string.h"
#include"malloc.h"

#define Max 20 //结点的最大个数

typedef struct node{

char data;

struct node *lchild,*rchild;

}BinTNode; //自定义二叉树的结点类型

typedef BinTNode *BinTree; //定义二叉树的指针

int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数

//基于先序遍历算法创建二叉树

//要求输入先序序列，其中加入虚结点“#”以示空指针的位置

BinTree CreatBinTree(void)

{

BinTree T;

char ch;

if((ch=getchar())=='#')

return(NULL); //读入#，返回空指针

else{
T=(BinTNode *)malloc(sizeof(BinTNode));//生成结点

T->data=ch;

T->lchild=CreatBinTree(); //构造左子树

T->rchild=CreatBinTree(); //构造右子树

return(T);

}

}

//DLR 先序遍历

void Preorder(BinTree T)

{

if(T) {

printf("%c",T->data); //访问结点

Preorder(T->lchild); //先序遍历左子树

Preorder(T->rchild); //先序遍历右子树

}

}

//LDR 中序遍历

void Inorder(BinTree T)

{

if(T) {

Inorder(T->lchild); //中序遍历左子树

printf("%c",T->data); //访问结点

Inorder(T->rchild); //中序遍历右子树

}

}

//LRD 后序遍历

void Postorder(BinTree T)

{

if(T) {

Postorder(T->lchild); //后序遍历左子树

Postorder(T->rchild); //后序遍历右子树

printf("%c",T->data); //访问结点

}

}

//采用后序遍历求二叉树的深度、结点数及叶子数的递归算法

int TreeDepth(BinTree T)

{

int hl,hr,max;

if(T){

hl=TreeDepth(T->lchild); //求左深度

hr=TreeDepth(T->rchild); //求右深度

max=hl>hr? hl:hr; //取左右深度的最大值

NodeNum=NodeNum+1; //求结点数

if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。

return(max+1);

}

else return(0);

}

//利用“先进先出”（FIFO）队列，按层次遍历二叉树

void Levelorder(BinTree T)

{

int front=0,rear=1;

BinTNode *cq[Max],*p; //定义结点的指针数组cq

cq[1]=T; //根入队

while(front!=rear)

{

front=(front+1)%NodeNum;

p=cq[front]; //出队

printf("%c",p->data); //出队，输出结点的值

if(p->lchild!=NULL){

rear=(rear+1)%NodeNum;

cq[rear]=p->lchild; //左子树入队

}

if(p->rchild!=NULL){

rear=(rear+1)%NodeNum;

cq[rear]=p->rchild; //右子树入队

}

}

}

//主函数

main()

{

BinTree root;

int i,depth;

printf("\n");

printf("Creat Bin_Tree; Input preorder:"); //输入完全二叉树的先序序列，

// 用#代表虚结点，如ABD###CE##F##

root=CreatBinTree(); //创建二叉树，返回根结点

do { //从菜单中选择遍历方式，输入序号。

printf("\t********** select ************\n");

printf("\t1: Preorder Traversal\n");

printf("\t2: Iorder Traversal\n");

printf("\t3: Postorder traversal\n");

printf("\t4: PostTreeDepth,Node number,Leaf number\n");

printf("\t5: Level Depth\n"); //按层次遍历之前，先选择4，求出该树的结点数。

printf("\t0: Exit\n");

printf("\t*******************************\n");

scanf("%d",&i); //输入菜单序号（0-5）

switch (i){

case 1: printf("Print Bin_tree Preorder: ");

Preorder(root); //先序遍历

break;

case 2: printf("Print Bin_Tree Inorder: ");

Inorder(root); //中序遍历

break;

case 3: printf("Print Bin_Tree Postorder: ");

Postorder(root); //后序遍历

break;

case 4: depth=TreeDepth(root); //求树的深度及叶子数

printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);

printf(" BinTree Leaf number=%d",leaf);

break;

case 5: printf("LevePrint Bin_Tree: ");

Levelorder(root); //按层次遍历

break;

default: exit (1);

}

printf("\n");

} while(i!=0);

}

F. 排序二叉树的遍历课程设计（跪求参考）

我们刚做完的实验。希望帮到您：
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
int right=0;
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree *T)
{
TElemType ch;
scanf("%c",&ch);
if(ch==' ')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T) exit(-1);
(*T)->data=ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}

}

void PreOrderTraverse(BiTree T)
{
if(T)
{
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
if(T->rchild) right++;
}

}

void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}

}

void PostOrderTraverse(BiTree T)
{

if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
}

void DestroyBiTree(BiTree *T)
{
if(*T)
{
if((*T)->lchild)
DestroyBiTree(&((*T)->lchild));
if((*T)->rchild)
DestroyBiTree(&((*T)->rchild));
free(*T);
*T=NULL;
}
}

int main()
{
BiTree T;

printf("请输入建立二叉树的字符序列(包括空格):\n");
CreateBiTree(&T);

printf("\n先序递归遍历二叉树:\n");
PreOrderTraverse(T);

printf("\n中序递归遍历二叉树:\n");
InOrderTraverse(T);

printf("\n后序递归遍历二叉树:\n");
PostOrderTraverse(T);

DestroyBiTree(&T);
printf(":\n");
printf("\n二叉树T的右子树的结点的个数:%d",right);
printf("\n");
return 0;
}

G. 数据结构:用栈的5种基本操作实现二叉树的遍历

//需要完整的代码就到我的空间去看吧。
//下面是给出了算法，也是可以用的
//**********************************//
void preorder_nonrecursive(Bitree T) /* 先序遍历二叉树 */
{
initstack(S);
push(S,T); /* 根指针进栈 */
while(!stackempty(S))
{
while(gettop(S,p)&&p)
{ /* 向左走到尽头 */
visit(p); /* 每向前走一步都访问当前结点 */
push(S,p->;lchild);
}
pop(S,p);
if(!stackempty(S))
{ /* 向右走一步 */
pop(S,p);
push(S,p->;rchild);
}
}
}

//*********************************//
void inorder_nonrecursive(Bitree T) /*中序遍历*/
{
initstack(S); /* 初始化栈 */
push(S, T); /* 根指针入栈 */

while (!stackempty(S))
{
while (gettop(S, p) && p) /* 向左走到尽头 */
push(S, p->;lchild);
pop(S, p); /* 空指针退栈 */
if (!stackempty(S))
{
pop(S, p);
visit(p); /* 访问当前结点 */
push(S, p->;rchild); /* 向右走一步 */
}
}
}

//*****************************************//
typedef struct
{
BTNode* ptr;
enum {0,1,2} mark;
} PMType; /* 有mark域的结点指针类型 */

void postorder_nonrecursive(BiTree T) /* 后续遍历二叉树 */
{
PMType a;
initstack(S); /* S的元素为PMType类型 */
push (S,{T,0}); /* 根结点入栈 */
while(!stackempty(S))
{
pop(S,a);
switch(a.mark)
{
case 0:
push(S,{a.ptr,1}); /* 修改mark域 */
if(a.ptr->;lchild)
push(S,{a.ptr->;lchild,0}); /* 访问左子树 */
break;
case 1:
push(S,{a.ptr,2}); /* 修改mark域 */
if(a.ptr->;rchild)
push(S,{a.ptr->;rchild,0}); /* 访问右子树 */
break;
case 2:
visit(a.ptr); /* 访问结点 */
}
}
}

H. 我要做数据结构的课程设计：线索二叉树的遍历操作，各位高手帮帮忙

#include<iostream.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
char data;
struct node *lchild,*rchild;//
}BiTNode,*BiTree;
void CreatBiTree(BiTree &T)
{
char ch;
ch=getchar();
if (ch == ' ')
T = 0;
else {
T=(BiTNode*)malloc(sizeof(BiTNode));
T->data=ch;//生成根节点
CreatBiTree(T->lchild);//构造左子树
CreatBiTree(T->rchild);//构造右子树
}
}
void preorder(BiTree T)//前序遍历
{
if (T!=NULL){
printf ("%c",T->data);
preorder(T->lchild);
preorder(T->rchild);
}
}
void inorder(BiTree T)//中序遍历
{
if (T!=NULL){
inorder(T->lchild);
printf ("%c",T->data);
inorder(T->rchild);
}
}
void postorder(BiTree T)//后序遍历
{
if (T!=NULL){
postorder(T->lchild);
postorder(T->rchild);
printf ("%c",T->data);
}
}
void main ()
{
cout<<"请输入要创建的二叉树包括空格:"<<endl ;
BiTree T;
CreatBiTree(T);//创建二叉树
cout<<"前序遍历的结果为:"<<endl;
preorder(T);
cout<<endl;
cout<<"中序遍历的结果为:"<<endl;
inorder(T);
cout<<endl;
cout<<"后序遍历的结果为:"<<endl;
postorder(T);
}

I. 二叉树排序算法实现（数据结构课程设计）

#include <malloc.h>
#include<stdio.h>
#define NUM 7 //宏定义
int i; //变量类型定义
typedef struct Node{
int data ; //数据域
struct Node *next; //指针域
}Node,*LNode; //用结构体构造结点及相应的指针

typedef struct Tree{
int data ;
struct Tree *left ;
struct Tree *right ;
}Tree,*LTree ; //用结构体构造树及相应的指针

CreateList( LNode Head ) //创建单链表
{
for(int i=1 ; i <=NUM ; i++) //创建循环，依次输入NUM个数据
{
LNode temp ; //中间结点
temp = (LNode) malloc( sizeof( Node ) ); //动态存储分配

temp-> next = NULL; //中间结点初始化
scanf("%2d",&temp-> data); //输入赋值到结点temp数据域
temp-> next = Head-> next ;
Head-> next = temp ; //将temp结点插入链表

}
return 1 ;//返回1
}

InsertSqTree( LTree &root , LNode temp ) //二叉树排序原则的设定
{
if(!root) //root为NULL时执行
{
root = (LTree)malloc(sizeof(Tree)); //动态存储分配

root-> left =NULL;
root-> right=NULL; //初始化
root-> data = temp-> data ; //赋值插入
return 1 ; //函数正常执行，返回1
}
else
{
if(root-> data>= temp-> data)
return InsertSqTree( root-> left , temp ) ; //比较插入左子树
else if(root-> data <temp-> data)
return InsertSqTree( root-> right , temp ); //比较插入右子树
}
return 1 ; //如果满足，就不做处理，返回1
}

void BianLiTree(LTree root) //采用中序遍历，实现将所有数字按从左向右递增的顺序排序
{
if(root) //root不为空执行
{BianLiTree(root-> left); //左递归处理至叶子结点，当root-> left为NULL时不执行
printf("%4d ",root-> data); //输出
BianLiTree(root-> right); //处理右结点
}
}

int main()
{
LNode Head = NULL;
LTree root = NULL ; //初始化
Head = (LNode) malloc(sizeof(Node)); //动态存储分配

Head-> next = NULL ; //初始化
printf("please input numbers:\n");//输入提示语句
if(!CreateList( Head )) //建单链表成功返回1不执行下一语句
return 0; //结束函数，返回0
LNode temp = Head-> next ; //将头指针的指针域赋值予中间结点
while( temp ) //temp为NULL时停止执行
{
if(!InsertSqTree( root ,temp )) //排序正常执行，返回1不执行下一语句
return 0 ; //结束函数，返回0
Head-> next = temp-> next ; //将中间指针的指针域赋值予头结点指针域
free(temp); //释放空间
temp = Head-> next ; //将头指针的指针域赋值予中间结点，以上三句实现了temp指针后移
}
printf("the result is:\n");//输出提示语句
BianLiTree(root); //采用中序遍历，输出并观察树结点
return 1; //函数正常结，返回1
}