課程設計利用順序棧遍歷二叉樹演算法

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
}