首頁猿問要編一個前中后的遍歷函數(shù)加進去構(gòu)成...

要編一個前中后的遍歷函數(shù)加進去構(gòu)成程序，請問該怎么做？

C++ 數(shù)據(jù)結(jié)構(gòu)

胡子哥哥 2022-08-05 14:10:49

#include<iostream.h>#include<stdio.h>struct tree {char info;struct tree *left,*right;};struct tree *create_btree(struct tree *root,struct tree *r,char info);struct tree *search_btree(struct tree *root,char key);void print_btree(struct tree *r,int l);void main (){ char s[100],c,key=' ' ;struct tree *root=0 ;do {printf("Enter a letter:");gets(s);if (!root)root=create_btree(root,root,*s);elsecreate_btree(root,root,*s);} while (*s) ;print_btree(root,0);key='1';while ( key){printf("Enter a key to find:");scanf("%s",&c);root=search_btree(root,c);printf("press to continue\n");}} /* Btree.C 結(jié)束 */struct tree *create_btree(struct tree *root,struct tree *r,char info){ if (r ==0 ){ r=new (struct tree);// same as function: malloc(sizeof())if ( r == 0){ printf("Out of memory\n"); return 0 ; }r->left= 0; r->right=0; r->info=info;if (root){ if(info<root->info) root -> left=r;else root -> right=r;}else{ r->right=0; r->left = 0; }return r;} /* if = = 0 接下頁 */if (info < r->info)create_btree(r,r->left,info);if(info>=r->info)create_btree(r,r->right,info);} /* create_btree(root,r,info) */struct tree *search_btree(struct tree *root,char key){ if (!root){ printf("Emptu btree\n"); return root; }while(root->info!=key){ if(key<root->info)root=root->left;elseroot=root->right;if(root==0){ printf("Search Failure\n");break ;}} /* while(root->info!=key) */if (root !=0)printf("Successful search\n key=%c\n",root->info);return root ;} /* *search_btree(root,key) */void print_btree(struct tree *r,int l){ int i;if (r == 0) return ;print_btree(r->left,l+1);for(i=0;i<l;i++)printf(" ");printf("%c\n",r->info);print_btree(r->right,l+1);}

查看完整描述

2 回答

白衣非少年

TA貢獻1155條經(jīng)驗獲得超0個贊

這是我寫的一個關(guān)于二叉樹的查找遍歷的程序，你可以參考一下

#include<iostream>
using namespace std;
#include<stdio.h>
#include<stdlib.h>
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef char TElemType;
typedef int Status;

typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T)
{
TElemType c;
cin>>c;
if(c=='#') T=NULL;
else
{
T=new BiTNode;
T->data=c;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}

Status visitT(TElemType e)
{ int c;
printf("%c",c);
return OK;
}

Status PreOrderTraverse(BiTree T){
if(T){
cout<<T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
return OK;
}
else
return ERROR;
}

Status InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->lchild);
cout<<T->data;
InOrderTraverse(T->rchild);
return OK;
}
else
return ERROR;
}

Status PostOrderTraverse(BiTree T){
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data;
return OK;
}
else
return ERROR;
}

int NodeCount(BiTree T ){
if(T==NULL)
return 0; // 如果是空樹，則結(jié)點個數(shù)為0
else
return(1+NodeCount(T->lchild)+ NodeCount(T->rchild));
//否則結(jié)點個數(shù)為1+左子樹的結(jié)點個數(shù)+右子樹的結(jié)點個數(shù)
}

int LeafNodeCount(BiTree T ){
if(T==NULL) //如果是空樹，則葉子個數(shù)為0;
return 0;
else
{
if(NodeCount(T)==1)
return 1; //如果是葉子結(jié)點，則葉子結(jié)點個數(shù)為1（如何表示葉子結(jié)點？？？）
else
return (LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild));
//否則葉結(jié)點個數(shù)為左子樹的葉結(jié)點個數(shù)+右子樹的葉結(jié)點個數(shù)
}
}

int Depth(BiTree T){
int m,n;
if(T==NULL) //如果是空樹，則深度為0;
return 0;
else{ //否則
m=Depth(T->lchild); //(1) 計算左子樹的深度記為m；
n=Depth(T->rchild); //(2) 計算右左子樹的深度記為n；
if(m>n)
return(m+1); //二叉樹的深度為m 與n的較大者加1
else
return(n+1);

}
}

int exchange(BiTree T)
{
struct BiTNode *t;
if(T==NULL) return 0;
else
{
t=T->lchild;
if(T->lchild!=NULL)
exchange(T->lchild);
if(T->rchild!=NULL)
exchange(T->rchild);
T->lchild=T->rchild;
T->rchild=t;
return OK;
}
}

void main()
{
BiTree T;
cout<<"請按先序遍歷的順序輸入一棵二叉樹："<<endl;
CreateBiTree(T);
cout<<"先序遍歷的結(jié)果為：";
PreOrderTraverse(T);
cout<<endl;
cout<<"中序遍歷的結(jié)果為：";
InOrderTraverse(T);
cout<<endl;
cout<<"后序遍歷的結(jié)果為：";
PostOrderTraverse(T);
cout<<endl;
cout<<"結(jié)點數(shù)為：";
cout<<NodeCount(T)<<endl;
cout<<"葉子結(jié)點數(shù)為：";
cout<<LeafNodeCount(T)<<endl;
cout<<"樹的深度為：";
cout<<Depth(T)<<endl;
exchange(T);
cout<<"左右孩子交換后的結(jié)果--先序遍歷為：";
PreOrderTraverse(T);
cout<<endl;
cout<<"左右孩子交換后的結(jié)果--中序遍歷為：";
InOrderTraverse(T);
cout<<endl;
cout<<"左右孩子交換后的結(jié)果--后序遍歷為：";
PostOrderTraverse(T);
cout<<endl;
}

反對回復(fù) 2022-08-08

郎朗坤

TA貢獻1921條經(jīng)驗獲得超9個贊

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct shu{
struct shu *lp,*rp;
char ch;
}shu,*bishu,;
////////////////////////創(chuàng)建///////////////////////////////////
int creat(bishu &t)
{
char ch;
ch=getchar();
if(ch==' ')
t=NULL;
else
{
if(!(t=(struct shu *)malloc(sizeof(struct shu))))
exit(0);
(*t).ch=ch;
creat((*t).lp);
creat((*t).rp);
}
return 1;
}
///////////////////////////////遍歷(遞歸)////////////////////////
int traverse(struct shu *t)
{
if(t==NULL)
return 1;
printf("%c ",(*t).ch);
traverse((*t).lp);
traverse((*t).rp);
return 1;
}
/////////////////////////////層序遍歷////////////////////////////
int ftraverse(struct shu *t)
{
int i=1,length=1;
shu tree[100];
if(t==NULL)
return 0;
while(1)
{
if(t!=NULL)
{printf("%c ",(*t).ch);
i++;length--;
tree[i+length].rp=(*t).lp;
length++;
tree[i+length].rp=(*t).rp;
length++;
t=tree[i].rp;
}
else
{i++;t=tree[i].rp;length--;}

if(t==NULL&&length!=0)
return 0;;
}
}
/////////////////////////////遍歷（非遞歸）/////////////////////
int mtraverse(struct shu *t)
{
int i=0;
shu tree[100];
if(t==NULL)
return 1;
printf("%c ",(*t).ch);
tree[i++].rp=(*t).rp;
t=(*t).lp;
while(i!=-1)
{
if(t!=NULL)
{
printf("%c ",(*t).ch);
tree[i++].rp=(*t).rp;
t=(*t).lp;
}
else
{
t=tree[--i].rp;
}
}
return 0;
}
/////////////////////////主函數(shù)///////////////////////////////////
int main()
{
bishu t;
creat(t);
mtraverse(t);
printf("\n");
ftraverse(t);
printf("\n");
traverse(t);
system("pause");
return 0;
}