c语言前序

Ⅰ 用c语言程实现树的遍历。分出先序,中序,后序

#include <stdio.h>
#include <stdlib.h>
#define STACK_MAX_SIZE 30
#define QUEUE_MAX_SIZE 30
#ifndef elemType
typedef char elemType;
#endif
/************************************************************************/
/* 以下是关于二叉树操作的11个简单算法 */
/************************************************************************/
struct BTreeNode{
elemType data;
struct BTreeNode *left;
struct BTreeNode *right;
};

/* 1.初始化二叉树 */
void initBTree(struct BTreeNode* *bt)
{
*bt = NULL;
return;
}

/* 2.建立二叉树(根据a所指向的二叉树广义表字符串建立) */
void createBTree(struct BTreeNode* *bt, char *a)
{
struct BTreeNode *p;
struct BTreeNode *s[STACK_MAX_SIZE];/* 定义s数组为存储根结点指针的栈使用 */
int top = -1; /* 定义top作为s栈的栈顶指针，初值为-1,表示空栈 */
int k; /* 用k作为处理结点的左子树和右子树，k = 1处理左子树，k = 2处理右子树 */
int i = 0; /* 用i扫描数组a中存储的二叉树广义表字符串，初值为0 */
*bt = NULL; /* 把树根指针置为空，即从空树开始建立二叉树 */
/* 每循环一次处理一个字符，直到扫描到字符串结束符为止 */
while(a[i] != ''){
switch(a[i]){
case ' ':
break; /* 对空格不作任何处理 */
case '(':
if(top == STACK_MAX_SIZE - 1){
printf("栈空间太小！n");
exit(1);
}
top++;
s[top] = p;
k = 1;
break;
case ')':
if(top == -1){
printf("二叉树广义表字符串错误!n");
exit(1);
}
top--;
break;
case ',':
k = 2;
break;
default:
p = malloc(sizeof(struct BTreeNode));
p->data = a[i];
p->left = p->right = NULL;
if(*bt == NULL){
*bt = p;
}else{
if( k == 1){
s[top]->left = p;
}else{
s[top]->right = p;
}
}
}
i++; /* 为扫描下一个字符修改i值 */
}
return;
}

/* 3.检查二叉树是否为空，为空则返回1,否则返回0 */
int emptyBTree(struct BTreeNode *bt)
{
if(bt == NULL){
return 1;
}else{
return 0;
}
}

/* 4.求二叉树深度 */
int BTreeDepth(struct BTreeNode *bt)
{
if(bt == NULL){
return 0; /* 对于空树，返回0结束递归 */
}else{
int dep1 = BTreeDepth(bt->left); /* 计算左子树的深度 */
int dep2 = BTreeDepth(bt->right); /* 计算右子树的深度 */
if(dep1 > dep2){
return dep1 + 1;
}else{
return dep2 + 1;
}
}
}

/* 5.从二叉树中查找值为x的结点，若存在则返回元素存储位置，否则返回空值 */
elemType *findBTree(struct BTreeNode *bt, elemType x)
{
if(bt == NULL){
return NULL;
}else{
if(bt->data == x){
return &(bt->data);
}else{ /* 分别向左右子树递归查找 */
elemType *p;
if(p = findBTree(bt->left, x)){
return p;
}
if(p = findBTree(bt->right, x)){
return p;
}
return NULL;
}
}
}

/* 6.输出二叉树(前序遍历) */
void printBTree(struct BTreeNode *bt)
{
/* 树为空时结束递归，否则执行如下操作 */
if(bt != NULL){
printf("%c", bt->data); /* 输出根结点的值 */
if(bt->left != NULL || bt->right != NULL){
printf("(");
printBTree(bt->left);
if(bt->right != NULL){
printf(",");
}
printBTree(bt->right);
printf(")");
}
}
return;
}

/* 7.清除二叉树，使之变为一棵空树 */
void clearBTree(struct BTreeNode* *bt)
{
if(*bt != NULL){
clearBTree(&((*bt)->left));
clearBTree(&((*bt)->right));
free(*bt);
*bt = NULL;
}
return;
}

/* 8.前序遍历 */
void preOrder(struct BTreeNode *bt)
{
if(bt != NULL){
printf("%c ", bt->data); /* 访问根结点 */
preOrder(bt->left); /* 前序遍历左子树 */
preOrder(bt->right); /* 前序遍历右子树 */
}
return;
}

/* 9.前序遍历 */
void inOrder(struct BTreeNode *bt)
{
if(bt != NULL){
inOrder(bt->left); /* 中序遍历左子树 */
printf("%c ", bt->data); /* 访问根结点 */
inOrder(bt->right); /* 中序遍历右子树 */
}
return;
}

/* 10.后序遍历 */
void postOrder(struct BTreeNode *bt)
{
if(bt != NULL){
postOrder(bt->left); /* 后序遍历左子树 */
postOrder(bt->right); /* 后序遍历右子树 */
printf("%c ", bt->data); /* 访问根结点 */
}
return;
}

/* 11.按层遍历 */
void levelOrder(struct BTreeNode *bt)
{
struct BTreeNode *p;
struct BTreeNode *q[QUEUE_MAX_SIZE];
int front = 0, rear = 0;
/* 将树根指针进队 */
if(bt != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = bt;
}
while(front != rear){ /* 队列非空 */
front = (front + 1) % QUEUE_MAX_SIZE; /* 使队首指针指向队首元素 */
p = q[front];
printf("%c ", p->data);
/* 若结点存在左孩子，则左孩子结点指针进队 */
if(p->left != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->left;
}
/* 若结点存在右孩子，则右孩子结点指针进队 */
if(p->right != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->right;
}
}
return;
}

/************************************************************************/

/*
int main(int argc, char *argv[])
{
struct BTreeNode *bt; /* 指向二叉树根结点的指针 */
char *b; /* 用于存入二叉树广义表的字符串 */
elemType x, *px;
initBTree(&bt);
printf("输入二叉树广义表的字符串：n");
/* scanf("%s", b); */
b = "a(b(c), d(e(f, g), h(, i)))";
createBTree(&bt, b);
if(bt != NULL)
printf(" %c ", bt->data);
printf("以广义表的形式输出：n");
printBTree(bt); /* 以广义表的形式输出二叉树 */
printf("n");
printf("前序："); /* 前序遍历 */
preOrder(bt);
printf("n");
printf("中序："); /* 中序遍历 */
inOrder(bt);
printf("n");
printf("后序："); /* 后序遍历 */
postOrder(bt);
printf("n");
printf("按层："); /* 按层遍历 */
levelOrder(bt);
printf("n");
/* 从二叉树中查找一个元素结点 */
printf("输入一个待查找的字符：n");
scanf(" %c", &x); /* 格式串中的空格跳过空白字符 */
px = findBTree(bt, x);
if(px){
printf("查找成功：%cn", *px);
}else{
printf("查找失败！n");
}
printf("二叉树的深度为：");
printf("%dn", BTreeDepth(bt));
clearBTree(&bt);
return 0;
}
*/

Ⅱ C语言中，到底先序遍历、中序遍历、后续遍历怎么看的...真的快疯掉了！求高人指点指点...泪目

先序遍历就是“根左右”，不管你现在在哪个节点，都是按这种规则。上面的题目：根是A，左是B，右是C，所以是A-》B，在当前根节点B，还是按上述规则，那么接下来到D，D之后没有子节点，返回B，遍历E-》X，X之后没有子节点，返回E，E的子节点都遍历完了，返回B，B的子节点都遍历完了，返回A，接下来遍历右子树，规则同上。
中序遍历就是“左根右”，对于A来说，先遍历B，对于B来说，先遍历D，对于D来说，已经没有左子树，所以遍历D，D没有右子树,返回B，遍历B，B有右子树E，对于E来说，先遍历X，完了返回E，E完了返回B，B完了返回A，遍历A，遍历右子树，规则同上。
后序遍历就是跟先序遍历相反的，先遍历右子树，再左子树，最后才是根。
好好思考一下。

Ⅲ c语言中排序方法

1、冒泡排序（最常用）
冒泡排序是最简单的排序方法：原理是：从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。（注意每一轮都是从a[0]开始比较的）

以从小到大排序为例，第一轮比较后，所有数中最大的那个数就会浮到最右边；第二轮比较后，所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。

2、鸡尾酒排序
鸡尾酒排序又称双向冒泡排序、鸡尾酒搅拌排序、搅拌排序、涟漪排序、来回排序或快乐小时排序, 是冒泡排序的一种变形。该算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。
原理：数组中的数字本是无规律的排放，先找到最小的数字，把他放到第一位，然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序。

3、选择排序
思路是设有10个元素a[1]-a[10]，将a[1]与a[2]-a[10]比较，若a[1]比a[2]-a[10]都小，则不进行交换。若a[2]-a[10]中有一个以上比a[1]小，则将其中最大的一个与a[1]交换，此时a[1]就存放了10个数中最小的一个。同理，第二轮拿a[2]与a[3]-a[10]比较，a[2]存放a[2]-a[10]中最小的数，以此类推。

4、插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素*
一般来说，插入排序都采用in-place在数组上实现。
具体算法描述如下：
⒈ 从第一个元素开始，该元素可以认为已经被排序
⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 将新元素插入到下一位置中
⒍ 重复步骤2~5

Ⅳ C语言前序遍历输入后序非递归遍历输出算法

//输入先序扩展序列:6500700
//后序遍历序列:576
//6
///
//57
////
//0000

//输入先序扩展序列:4210030050600
//后序遍历序列:132654
//
//4
///
//25
////
//1306
/////
//000000

#include<stdio.h>
#include<stdlib.h>
#definemax100//20//栈的大小
structbitree//二叉树的结构体
{
intdata;
structbitree*llink;//左分支
structbitree*rlink;//右分支
};

structstack_post//栈的结构体[用于后序遍历]
{
structbitree*bt;//指向二叉树
intleftOrRight;//当前节点是哪个分支,1=左分支0=右分支
};

structstack_postsk[max];//全局变量:栈(用于后序遍历)

//voidbuild(structbitree*n)
//创建二叉树:先序扩展序列+递归法
voidbuild(structbitree**n)
{
//注:structbitree**n是指针的指针
intch;
scanf("%d",&ch);
if(ch==0)
{
*n=NULL;
}
else
{
*n=(structbitree*)malloc(sizeof(structbitree));
if(*n==NULL)
{
printf("
Memoryoverflow!
");
exit(1);
}
(*n)->data=ch;
build(&((*n)->llink));
build(&((*n)->rlink));
}
//原代码
/*
n=(structbitree*)malloc(sizeof(structbitree));
scanf("%d",&ch);
if(ch==0)
n=NULL;
else
{
if(!(n=(structbitree*)malloc(sizeof(structbitree))))
{
return;
}
n->data=ch;
build(n->llink);
build(n->rlink);
}
*/
}

//后序遍历序列(非递归)
voidPost_Order(structbitree*n)
{
structbitree*p=NULL;
////structstack_postsk[max];//全局变量:栈(用于后序遍历)
inttop=0;//栈顶为0,top=1用于存放第1个数据
intleftOrRight;//当前节点是哪个分支,1=左分支0=右分支
structbitree*tmpTree;

if(n==NULL)return;
p=n;//当前二叉树的节点
leftOrRight=1;//1=左分支(默认从左分支开始遍历)
while(p!=NULL)
{
if(p->llink!=NULL)//有左分支,当前节点入栈
{
top++;
sk[top].bt=p;
sk[top].leftOrRight=leftOrRight;
p=p->llink;
leftOrRight=1;
}
elseif(p->rlink!=NULL)//有右分支,当前节点入栈
{
top++;
sk[top].bt=p;
sk[top].leftOrRight=leftOrRight;
p=p->rlink;
leftOrRight=0;
}
else//该节点是"叶子"
{
printf("%d",p->data);
while(1)//处于"回溯"状态
{
tmpTree=sk[top].bt;//看[栈顶]
if(tmpTree==NULL)//[栈]已经没有数据
{
p=NULL;//整个遍历过程结束,退出循环
break;
}
if(leftOrRight==1)//处于"左分支"回溯
{
if(tmpTree->rlink==NULL)//[栈顶]的节点没有右分支,出栈,打印
{
p=sk[top].bt;
leftOrRight=sk[top].leftOrRight;
top--;
printf("%d",p->data);
//仍然处于"回溯"状态
}
else//[栈顶]的节点有右分支,不出栈,右分支成为当前节点
{
p=tmpTree->rlink;
leftOrRight=0;//设置当前处于右分支
break;//退出"回溯"状态
}
}
else//处于"右分支"回溯
{
//[栈]有节点,出栈,打印
p=sk[top].bt;
leftOrRight=sk[top].leftOrRight;
top--;
printf("%d",p->data);
//仍然处于"回溯"状态
}
}//while(1)结束
}//if(p->llink!=NULL)else结束
}//while(p!=NULL)结束

//栈顶top=0,说明[栈]已经没有数据
printf("
核对,栈顶top=%d
",top);
}

//有错误
//原代码,后序遍历序列(非递归)
/*
voidpostorder(structbitree*n)
{
structbitree*p,*q;
inti;
p=(structbitree*)malloc(sizeof(structbitree));
p=n;
q=(structbitree*)malloc(sizeof(structbitree));
structbitree*s[max];
for(i=0;i<max;i++)
{
s[i]=(structbitree*)malloc(sizeof(structbitree));
}
inttop=-1;
do
{
while(p!=NULL)
{
if(p->rlink!=NULL)
{
top++;
s[top]=p->rlink;
}
p=p->llink;;
}
p=s[top];
top--;
if(p->rlink==NULL||p->rlink==q)
{
printf("%d",p->data);
q=p;
p=NULL;
}
else
p=p->rlink;
}while(p!=NULL||top!=-1);
}
*/

//后序遍历序列(递归)[用于对比测试]
voidpostTest(structbitree*n)
{
if(n!=NULL)
{
postTest(n->llink);
postTest(n->rlink);
printf("%d",n->data);
}
}

intmain()
{
structbitree*n;
//原代码n=(structbitree*)malloc(sizeof(structbitree));
printf("Inputthepreorder-numbersofthetree('0'forNULL):
");
//原代码build(n);
build(&n);

printf("
Postorderisbelow:");
//原代码postorder(n);//后序遍历序列(非递归)
Post_Order(n);//后序遍历序列(非递归)

printf("
后序遍历序列(递归):");
postTest(n);//用于对比测试

printf("
");
return0;
}

Ⅳ 设计一个c语言程序，实现二叉树的前序、中序、后序的递归、非递归遍历运算

#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样

typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}

void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}

void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}

void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}

void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}

void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点

}
}

void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树： ");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树： ");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf(" \n后序递归遍历二叉树：");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
printf("\n");
}

Ⅵ c语言三种排序

常用的c语言排序算法主要有三种即冒泡法排序、选择法排序、插入法排序。

一、冒泡排序冒泡排序：

是从第一个数开始，依次往后比较，在满足判断条件下进行交换。代码实现（以降序排序为例）

#include<stdio.h>

int main()

{

int array[10] = { 6,9,7,8,5,3,4,0,1,2 };

int temp;

for (int i = 0; i < 10; i++)

{//循环次数

for (int j = 0; j <10 - i-1; j++)

{

if (array[j] < array[j+1])

{//前面一个数比后面的数大时发生交换 temp = array[j];

array[j] = array[j+1];

array[j + 1] = temp;

}

}

} //打印数组 for (int i = 0; i < 10; i++) printf("%2d", array[i]); return 0;}}

二、选择排序以升序排序为例：

就是在指定下标的数组元素往后（指定下标的元素往往是从第一个元素开始，然后依次往后），找出除指定下标元素外的值与指定元素进行对比，满足条件就进行交换。与冒泡排序的区别可以理解为冒泡排序是相邻的两个值对比，而选择排序是遍历数组，找出数组元素与指定的数组元素进行对比。（以升序为例）

#include<stdio.h>

int main()

{

int array[10] = { 6,9,7,8,5,3,4,0,1,2 };

int temp, index;

for (int i = 0; i < 9; i++) {

index = i;

for (int j = i; j < 10; j++)

{

if (array[j] < array[index])

index = j;

}

if(i != index)

{

temp = array[i];

array[i] = array[index];

array[index] = temp;

}

for(int i=0;i<10:i++)

printf("%2d"array[i]）

return 0；

}

三、快速排序

是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

void QuickSort(int* arr, int size)

{

int temp, i, j;

for(i = 1; i <size; i++)

for(j=i; j>0; j--)

{

if(arr[j] <arr[j-1])

{

temp = arr[j];

arr[j]=arr[j-1];

arr[j-1]=temp;

}

}

}

Ⅶ 用C语言实现前序和中序恢复二叉树

按照你题目要求做的。。。

由于我不知道你的TNode类是怎么定义的，所以我就直接输出结果了

voidInPreToTree(charpreord[],charinord[],intpreleft,intpreright,intinleft,intinright)
{
/*请在BEGIN和END之间实现你的代码*/
/*****BEGIN*****/
introot2n,leftsize,rightsize;
if(preleft<=preright&&inleft<=inright)
{
for(root2n=inleft;root2n<=inright;root2n++)
if(preord[preleft]==inord[root2n])break;
leftsize=root2n-inleft;
rightsize=inright-root2n;
if(leftsize>0)
InPreToTree(preord,inord,preleft+1,preleft+leftsize,inleft,root2n-1);
if(rightsize>0)
InPreToTree(preord,inord,preleft+leftsize+1,preright,root2n+1,inright);
printf("%c",inord[root2n]);
}
/******END******/
/*请不要修改[BEGIN,END]区域外的代码*/
}

望采纳，谢谢

Ⅷ C语言数据结构树的前序遍历算法求指教

首先创建二叉树，个人喜欢用先序次序创建，如
int CreateBiTree(Tree *T)// 按先序次序输入二叉树中结点的值，'#'字符表示空树，构造二叉链表表示的二叉树T
{
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (Tree *)malloc(sizeof(Tree)))) return ERROR;
T->data=ch; // 生成根结点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return OK;
}
再者，调用前序遍历函数，再运用输出函数输出前序遍历的二叉树，如：
int Visit(int e ) // 输出元素e的值
{
printf("%c", e );
return OK;
}
int main()
{
Tree *T;
CreateBiTree(T); //调用按先序次序输入二叉树中结点的值（一个字符），构造二叉链
pre_order(T,Visit);//调用前序遍历二叉树算法
}

Ⅸ 输入二叉树中序和后序，求它的前序（c语言）

//有一个小问题，加一句话就行了

#include <stdio.h>
#include <string.h>
char a[10],b[10];

int work(int zi,int zj,int hi,int hj)
{

int i,j,k,fz,fh=hi;
//这句话要加，如果调试的话会发现，有些时候zi是会大于zj的，这个时候要立即返回
if(zi>zj) return 0;
printf("%c",b[hj]);//getchar();
if (zi==zj) return 0;

for (fz=zi;fz<=zj;fz++) if (a[fz]==b[hj])break;
fh=hi+(fz-zi)-1;
//导致zi>zj的原因就是如果 fz=zi的话，那么fz-1就比zi小了
work(zi,fz-1,hi,fh);
work(fz+1,zj,fh+1,hj-1);
}

//这样就OK了

//测试数据
//Sample Input

// ABCDEFG ACBFGED

//Sample Output

// DBACEGF

int main()
{
scanf("%s%s",a,b);
work(0,strlen(a)-1,0,strlen(b)-1);
while (1);
return 0;
}

Ⅹ C语言中，前序遍历，中序遍历各什么意思

前序遍历：先访问根节点，然后访问左子树，再访问右子树。
中序遍历：先访问左子树，然后访问根节点，再访问右子树。