高分求二叉树的建立例题，以及三种遍历 求这个二叉树的三种遍历序列
\u3010\u3010\u6c42\u3011\u3011\u4e8c\u53c9\u6811\u7684\u4e09\u79cd\u904d\u5386\u4e3e\u4f8b!!!\u524d\u5e8f\u904d\u5386:1 2 4 8 9 10 11 5 3 6 7 (\u89c4\u5f8b\uff1a\u6839\u5728\u524d\uff1b\u5b50\u6811\u5728\u6839\u540e\u4e14\u5de6\u5b50\u6811\u6bd4\u53f3\u5b50\u6811\u9760\u524d)\uff1b
\u4e2d\u5e8f\u904d\u5386:8 4 10 9 11 2 5 1 6 3 7 (\u89c4\u5f8b\uff1a\u6839\u5728\u4e2d\uff1b\u5de6\u5b50\u6811\u5728\u8ddf\u5de6\u8fb9\uff0c\u53f3\u5b50\u6811\u5728\u6839\u53f3\u8fb9)\uff1b
\u540e\u5e8f\u904d\u5386:8 10 11 9 4 5 2 6 7 3 1 (\u89c4\u5f8b\uff1a\u6839\u5728\u540e\uff1b\u5b50\u6811\u5728\u6839\u524d\u4e14\u5de6\u5b50\u6811\u6bd4\u53f3\u5b50\u6811\u9760\u524d)\uff1b
\u5176\u5b83\u4f8b\u5b50\uff1a
\u524d\u5e8f\u904d\u5386:ABDECFG
\u4e2d\u5e8f\u904d\u5386:DBEAFCG
\u540e\u5e8f\u904d\u5386:DEBFGCA
\u524d\u5e8f\u904d\u5386:1 2 4 3 5 7 6
\u4e2d\u5e8f\u904d\u5386:2 4 1 5 7 3 6
\u540e\u5e8f\u904d\u5386:4 2 7 5 6 3 1
\u505a\u7c7b\u4f3c\u7684\u9898\u76ee\uff0c\u4f60\u53ef\u4ee5\u5148\u7531\u4e24\u4e2a\u904d\u5386\u753b\u51fa\u4e8c\u53c9\u6811\u3002\u901a\u8fc7\u5f62\u8c61\u7684\u4e8c\u53c9\u6811\u6765\u5199\u51fa\u53e6\u4e00\u4e2a\u904d\u5386\uff0c\u5199\u7684\u65b9\u6cd5\u5982\u4e0a\uff08\u9012\u5f52\uff09\u3002\u753b\u51fa\u4e8c\u53c9\u6811\u7684\u65b9\u6cd5\u5982\u4e0b\uff1a
\u5df2\u77e5\u4e00\u68f5\u4e8c\u53c9\u6811\u7684\u524d\u5e8f\u5e8f\u5217\u548c\u4e2d\u5e8f\u5e8f\u5217\uff0c\u6784\u9020\u8be5\u4e8c\u53c9\u6811\u7684\u8fc7\u7a0b\u5982\u4e0b\uff1a
1. \u6839\u636e\u524d\u5e8f\u5e8f\u5217\u7684\u7b2c\u4e00\u4e2a\u5143\u7d20\u5efa\u7acb\u6839\u7ed3\u70b9\uff1b
2. \u5728\u4e2d\u5e8f\u5e8f\u5217\u4e2d\u627e\u5230\u8be5\u5143\u7d20\uff0c\u786e\u5b9a\u6839\u7ed3\u70b9\u7684\u5de6\u53f3\u5b50\u6811\u7684\u4e2d\u5e8f\u5e8f\u5217\uff1b
3. \u5728\u524d\u5e8f\u5e8f\u5217\u4e2d\u786e\u5b9a\u5de6\u53f3\u5b50\u6811\u7684\u524d\u5e8f\u5e8f\u5217\uff1b
4. \u7531\u5de6\u5b50\u6811\u7684\u524d\u5e8f\u5e8f\u5217\u548c\u4e2d\u5e8f\u5e8f\u5217\u5efa\u7acb\u5de6\u5b50\u6811\uff1b
5. \u7531\u53f3\u5b50\u6811\u7684\u524d\u5e8f\u5e8f\u5217\u548c\u4e2d\u5e8f\u5e8f\u5217\u5efa\u7acb\u53f3\u5b50\u6811\u3002
\u5df2\u77e5\u4e00\u68f5\u4e8c\u53c9\u6811\u7684\u540e\u5e8f\u5e8f\u5217\u548c\u4e2d\u5e8f\u5e8f\u5217\uff0c\u6784\u9020\u8be5\u4e8c\u53c9\u6811\u7684\u8fc7\u7a0b\u5982\u4e0b\uff1a
1. \u6839\u636e\u540e\u5e8f\u5e8f\u5217\u7684\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u5efa\u7acb\u6839\u7ed3\u70b9\uff1b
2. \u5728\u4e2d\u5e8f\u5e8f\u5217\u4e2d\u627e\u5230\u8be5\u5143\u7d20\uff0c\u786e\u5b9a\u6839\u7ed3\u70b9\u7684\u5de6\u53f3\u5b50\u6811\u7684\u4e2d\u5e8f\u5e8f\u5217\uff1b
3. \u5728\u540e\u5e8f\u5e8f\u5217\u4e2d\u786e\u5b9a\u5de6\u53f3\u5b50\u6811\u7684\u540e\u5e8f\u5e8f\u5217\uff1b
4. \u7531\u5de6\u5b50\u6811\u7684\u540e\u5e8f\u5e8f\u5217\u548c\u4e2d\u5e8f\u5e8f\u5217\u5efa\u7acb\u5de6\u5b50\u6811\uff1b
5. \u7531\u53f3\u5b50\u6811\u7684\u540e\u5e8f\u5e8f\u5217\u548c\u4e2d\u5e8f\u5e8f\u5217\u5efa\u7acb\u53f3\u5b50\u6811\u3002
我上机报告的代码和截图
#include<iostream>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char BiElemType;
// 二叉树的数据结构定义
typedef struct BiNode
{
BiElemType data;
BiNode *lchild,*rchild;
}BiNode,*BiTree;
//构造一棵二叉树，并且按照前序遍历的方式赋值
Status CreateBiTree(BiTree &T)
{
BiElemType ch;
cin>>ch;
if(ch=='#')T=NULL;
else
{
if(!(T=(BiNode *)malloc(sizeof(BiNode))))exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
//先序遍历
Status preorder(BiTree T)
{
if(T)
{
if(cout<<T->data<<' ')
if(preorder(T->lchild))
if(preorder(T->rchild))return OK;
return ERROR;
}
else return OK;
}
//中序遍历
Status inorder(BiTree T)
{
if(T)
{
if(inorder(T->lchild))
if(cout<<T->data<<' ')
if(inorder(T->rchild))return OK;
return ERROR;
}
else return OK;
}
//后序遍历
Status postorder(BiTree T)
{
if(T)
{
if(postorder(T->lchild))
if(postorder(T->rchild))
if(cout<<T->data<<' ')return OK;
return ERROR;
}
else return OK;
}
int main()
{
BiTree BiT;
cout<<"以先序顺序输入二叉树的数据，以#表示空节点："<<endl;
CreateBiTree(BiT);
cout<<"以中序遍历输出：";
inorder(BiT);
cout<<endl;
cout<<"以先序遍历输出：";
preorder(BiT);
cout<<endl;
cout<<"以后序遍历输出：";
postorder(BiT);
cout<<endl;
return 0;
}
/* bu用递归法输出中序和后续*/
#include "stdio.h"
#include "stdlib.h"
#define A 25
typedef struct Btree
{ char data;
struct Btree *lchild,*rchild;
}*tree,t2ree;
t2ree *creat()
{ tree t;
char ch;
scanf("%c",&ch);
if(ch=='#')
t=NULL;
else
{ t=(t2ree *)malloc(sizeof(t2ree));
t->data=ch;
t->lchild=creat();/* 开始格式不正确啊 ，就是我用了这个creat(r->rchild),所以对导致
指针乱算*/
t->rchild=creat();
}
return t;
}
/*显示用先序遍历*/
void preorder(tree t)
{ t2ree *s[A] ;
int top=0;
do
{ while(t!=NULL)
{ printf("%c",t->data);
if(t->rchild!=NULL)
s[top++]=t->rchild ; /*是右子树的地址*/
t=t->lchild; /* 再就是这个地方我加了一个{}结果导致了错误*/
}
if(top>=0)
t=s[--top];
}while(top>=0);
}
/* 中序遍历*/
void inorder(tree t)
{
tree s[A],p;
int top=0;
p=t;
do
{ while(p!=NULL)
{ s[top++]=p;
p=p->lchild;
}
if(top>=0)
{ p=s[--top];
printf("%c",p->data);
p=p->rchild;
}
}while(top>=0);
}
/* 后续遍历*/
void postorder(tree t)
{ int top=0,s2[A],b;
tree s1[A],p;
p=t;
do
{
while(p!=NULL)
{s1[top]=p;
s2[top++]=0;
p=p->lchild;
}
if(top>=0)
{ b=s2[--top];
p=s1[top];
if(b==0)
{ s1[top]=p;
s2[top++]=1;
p=p->rchild;
}
else
{ printf("%c",p->data);
p=NULL;
}
}
}while(top>0);
}
/* 求深度*/
int deep(tree t)
{ int i=0,j=0;
if(!t)
return 0;
else
{ i=deep(t->lchild);
j=deep(t->rchild);
}
return((i>j?i:j)+1);
}
/*求叶子的个数*/
int thief(tree t)
{ int i=0,j=0;
if(!t)
return 0;
else
{i=thief(t->lchild);
j=thief(t->rchild);
}
if(i==0&j==0)
return(1);
else
return(i+j);
}
main()
{ tree s;
s=creat();
printf("\XIAN xu shu chu \n");
preorder(s);
printf("\n kai shi zhong xu :\n");
inorder(s);
printf("\n hou xu :\n");
postorder(s);
printf("\n the shen du is %d\n",deep(s));
printf("\n the ye zi is %d\n",thief(s));
getch();
}
#include<stdio.h>
#include<stdlib.h>
#define ELEMTP int
struct node
{
ELEMTP data;
struct node *lc,*rc;
};
struct node *root;
int m=0;
main()
{
int cord;
struct node* creat();
void preorderz(struct node *t);
void inorder(struct node *t);
void postorder(struct node *t);
void deletes(struct node *t,struct node *p,struct node *f);
do
{
printf("\n 主菜单 \n");
printf(" 1 建立二叉树 \n");
printf(" 2 先序非递归遍历 \n");
printf(" 3 中序递归遍历 \n");
printf(" 4 后序递归遍历，求叶节点数 \n");
printf(" 5 删除节点 \n");
printf(" 6 结束程序运行 \n");
printf("---------------------------------------\n");
printf("请输入您的选择(1, 2, 3, 4, 5, 6)");
scanf("%d",&cord);
switch(cord)
{
case 1:
{
root=creat(); // 建立二叉树
printf("建立二叉树程序以执行完，\n");
printf("请返回主菜单，用遍历算法验证程序的正确性 \n");
}break;
case 2:
{
preorderz(root);
}break;
case 3:
{
inorder(root);
}break;
case 4:
{
postorder(root);
}break;
case 5:
{
//deletes(root)
}
case 6:
{
printf("二叉树程序执行完，再见！\n");
exit(0);
}
}
}while(cord<=6);
}
struct node* creat()
{
struct node *t,*q,*s[30];
int i,j,x;
printf("i,x=");
scanf("%d%d",&i,&x);//i是按满二叉树编号，x节点应有的序号，x是节点的数据
while((i!=0)&&(x!=0))
{
q=(struct node*)malloc(sizeof(struct node));
q->data=x;
q->lc=NULL; q->rc=NULL;
s[i]=q;
if(i==1)
t=q; //t代表树根节点
else
{
j=i/2; //双亲节点的编号
if((i%2)==0)
s[j]->lc=q;
else
s[j]->rc=q;
}
printf("i,x=");
scanf("%d%d",&i,&x);
}
return(t);
}
/*void preorderz(struct node* p)//前序非递归算法
{
struct node *q,*s[30]; //s辅助栈
int top,bools;
q=p;top=0; //栈顶指针
bools=1; //bools=1为真值继续循环；bools=0为假时栈空，结束循环
do
{
while(q!=NULL)
{
printf("%6d",q->data); //访问节点
top++;
s[top]=q;
q=q->lc;
}
if(top==0)
bools=0;
else
{
q=s[top];
top--;
q=q->rc;
}
}while(bools);
printf("\n");
}//////////////////////////结束preorderz*/
void preorderz(struct node* p)//前序递归遍历
{
if(p!=NULL)
{
printf("%6d",p->data);
inorder(p->lc);
inorder(p->rc);
}
}
void inorder(struct node* p)//中序非递归遍历
{
struct node *s[30],*q;
int top,bools;
q=p;top=0;
bools=1;
do
{
while(q!=NULL)
{
top++;
s[top]=q;
q=q->lc;
}
if(top==0)
bools=0;
else
{
q=s[top];
top--;
printf("%6d",q->data);
q=q->rc;
}
}while(bools);
}
/*void inorder(struct node* p)
{
if(p!=NULL)
{
inorder(p->lc);
printf("%6d",p->data);
inorder(p->rc);
}
}//////////////////////////结束inorder*/
void postorder(struct node* p)
{
struct node *s[30],*s2[30],*q;
int top,bools;
q=p;top=0;
bools=1;
do
{
while(q!=NULL)
{
top++;
s[top]=q;
s2[top]=1;
q=q->lc;
}
if(top==0)
bools=0;
else
{
if(s2[top]==1)
{
s2[top]=2;
q=s[top];
q=q->rc;
}
else
{
q=s[top];
s2[top]=0;
top--;
printf("%6d",q->data);
q=NULL;
}
}
}while(bools);
}
void deletes(struct node *t,struct node *p,struct node *f)
{
struct node *s,*q;
int bools=1;
if(p->lc==NULL)
s=p->rc;
else if(p->rc==NULL)
{
s=p->rc;
while(s->lc!=NULL)
{
q=s;
s=s->rc;
}
if(q==p)
q->rc=s->rc;
else
q->lc=s->rc;
p->data=s->data;
free(s);
bools=0;
}
if(bools==1)
{
if(f==NULL)
t=s;
else if(f->lc==p)
f->lc=s;
else
f->rc=s;
free(p);
}
}
/*void postorder(struct node* p)
{
if(p!=NULL)
{
postorder(p->lc);
postorder(p->rc);
printf("%6d",p->data);
if(p->lc==NULL&&p->rc==NULL)
m++; //统计叶子节点
}
}//////////////////////////结束postorder*/
#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node /*二叉树结点定义*/
{
datatype data;
struct node *lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
void createbintree(bintree *t)
{/*按照前序遍历的顺序建立一棵给定的二叉树*/
char ch;
if ((ch=getchar())==' ')
*t=NULL;
else {
*t=(bintnode *)malloc(sizeof(bintnode));
(*t)->data=ch;
createbintree(&(*t)->lchild);
createbintree(&(*t)->rchild);
}
}
void preorder(bintree t)
{/*前序遍历二叉树的递归算法*/
if (t) { printf("%c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
main() /*主程序*/
{ bintree root;
printf("\n");
createbintree(&root);
printf("\n");
printf("\n前序遍历结果是: ");
preorder(root);
}
我们学校的， 你参考下，或许对你有用
这是前序的，
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
char data;
struct node *lchild;
struct node *rchild;
}node,*BinTree;
void inorder(node *p,int n)
{
if(p!=NULL)
{
int i;
inorder(p->lchild,n+1);
for(i=0;i<n;i++)
printf("----------");
printf("%c",p->data);
printf("\n");
inorder(p->rchild,n+1);
}
}
void create(BinTree *p)
{
char data;
printf("Please input a word:");
scanf("%s",&data);
if(data=='#')
p=NULL;
else
{
*p=(node *)malloc(sizeof(node));
if(*p==NULL)
{
printf("Ask for free faid!\n");
exit(1);
}
(*p)->data=data;
create(&(*p)->lchild);
create(&(*p)->rchild);
}
}
void main()
{
BinTree root;
create(&root);
inorder(root,0);
}
绛旓細绛夊紡涓ょ鍚屾椂涔樹互n/n+1,寰楋細(n/n+1)P(n)=[(n-1)/n]P(n-1)+(2n-1)/[n(n+1)].浠(n/n+1)P(n)=a(n)锛屽垯a(n)-a(n-1)=3/(n+1)-1/n.鍙犲姞锛屽緱锛歛(n)-a(1)=1/(n+1)-1/2+2鈭1/(i+1) 锛(i=2--->n)鈭碢(n)=1/n+(n+1)(p(1)-1)/2n+[2(n+...
绛旓細3.鍙湪涓夌閬嶅巻绠楁硶鐨勫熀纭涓婃敼閫犲畬鎴愮殑鍏跺畠浜屽弶鏍戠畻娉:姹傚彾瀛愪釜鏁,姹備簩鍙夋爲缁撶偣鎬绘暟,姹傚害涓1鎴栧害涓2鐨勭粨鐐规绘暟,澶嶅埗浜屽弶鏍,寤虹珛浜屽弶鏍,浜ゆ崲宸﹀彸瀛愭爲,鏌ユ壘鍊间负n鐨勬煇涓寚瀹氱粨鐐,鍒犻櫎鍊间负n鐨勬煇涓寚瀹氱粨鐐,璇稿姝ょ被绛夌瓑绛夌瓑銆傚鏋滀綘鍙互鐔熺粌鎺屾彙浜屽弶鏍戠殑閫掑綊鍜岄潪閫掑綊閬嶅巻绠楁硶,閭ｄ箞瑙ｅ喅浠ヤ笂闂灏辨槸灏忚彍涓纰熶簡銆4....
绛旓細R,F->rchild);} 鍥涖佸涓嬮潰鐨勫甫鏉冭繛閫氭棤鍚戝浘锛岀敤Prim锛堟櫘閲屽锛夌畻娉曪紝鏋勯犱竴鏍渶灏忕敓鎴愭爲銆傜敾鍑烘瀯閫犺繃绋嬬殑姣忎竴姝ャ傦紙12鍒嗭級浜 璁捐鍒嗙被鐨勬暟鎹瓨鏀惧湪鏁扮粍A3 1 4 1 5 9 2 6 5 3涓紝瑕佽繘琛屽爢鍒嗙被锛岄鍏堝緱涓哄叾寤虹珛涓涓垵濮嬪爢锛岃瘯鐢诲嚭鍒濆寤鸿鍫嗚繃绋嬩腑锛屼簩鍏冩爲鐨鍙樺寲鍜屾暟缁凙鐨勫彉鍖栥
绛旓細ch=getchar(); 鏀规垚cin >> ch 灏卞簲璇ュ彲浠ヤ簡 鍘熷洜鏄墠涓娆¤緭鍏ョ殑鍥炶溅杩樺瓨鏀惧湪閿洏缂撳瓨鍖洪噷
绛旓細lz銆備綘鐨勮繖涓棶棰橈紝灏辩畻鏄珮鎵嬪鏋滀笉鐢ㄧ幇鎴愮殑浠ｇ爜锛屽叏閮ㄨ嚜宸遍噸鍐欍傚皯璇翠篃瑕佺敤2涓皬鏃舵墠鑳藉畬鎴愩傚鏋滃啀鍔犱笂浣犺鐨勫垎鏋愭姤鍛婁箣绫荤殑銆備竴澶╁氨杩囧幓浜嗐傛垜寤鸿浣犺繕鏄湪缃戜笂鎵剧畻娉曞拰浠ｇ爜銆傝嚜宸辨暣鐞嗗嚭鏉ュ惂銆傝繖鏍蜂篃鑳藉鍒颁笢瑗裤傜湅鏉ヤ綘鑲畾鏄绠楁満涓撲笟鐨勫鐢熴傚鏋滆繖涓兘涓嶈兘鐙珛瀹屾垚锛屽懙鍛点傘傘傚埆鐨勫氨涓嶈浜嗐
绛旓細浣犺繖涓繁搴︽槸浠0寮濮嬶紝杩樻槸浠1寮濮嬨傚鏋滀粠0寮濮嬶細涓鍏辨湁K+1灞傦紝闄ょ涓灞傚锛屾瘡灞2涓妭鐐癸紝鍏辨湁2K+1銆傚鏋滀粠1寮濮嬶細涓鍏辨湁K灞傦紝闄ょ涓灞傚锛屾瘡灞2涓妭鐐癸紝鍏辨湁2K-1涓
绛旓細7.涓涓3闃舵湁鍚戝浘鐨勫害搴忓垪鏄2锛2锛4锛屽叆搴﹀簭鍒楁槸2锛0锛2锛屽嚭搴﹀簭鍒楁槸 0锛2锛2 銆8.涓鏃犲悜鍥惧瓨鍦ㄧ敓鎴鏍戠殑鍏呭垎蹇呰鏉′欢鏄 G鏄繛閫氬浘 銆9.鏈浼浜屽弶鏍鏈塶鐗囨爲鍙讹紝鍒欏畠鏈 n-1 鍒嗘敮鐐广10. 涓嬪浘鐨勭偣杩為氬害绛変簬 锛岃竟杩為氬害绛変簬___銆
绛旓細41锛庝竴涓笁瀵硅鐭╅樀An脳n宸叉寜琛屽帇缂╁瓨鍌ㄥ埌涓缁存暟缁凚涓紝鍒橞鐨勯暱搴﹁嚦灏戜负锛圕锛夈侫锛3n+1 B锛3n C锛3n-1 D锛3n-2 42锛庡箍涔夎〃((a,b),(c,d))鐨勮〃灏炬槸( A )銆侫锛(c,d) B锛((c,d)) C锛(d) D锛塪 44锛庤涓妫浜屽弶鏍涓病鏈夊害涓1鐨勭粨鐐癸紝宸茬煡鍙跺瓙缁撶偣鏁颁负n锛屾鏍...
绛旓細20. 宸茬煡6涓粨鐐圭殑浜屽弶鏍戠殑鍏堟牴閬嶅巻鏄1 2 3 4 5 6(鏁板瓧涓虹粨鐐圭殑缂栧彿,浠ヤ笅鍚),鍚庢牴閬嶅巻鏄3 2 5 6 4 1,鍒欒浜屽弶鏍戠殑鍙兘鐨勪腑鏍归亶鍘嗘槸( )A. 3 2 1 4 6 5 B. 3 2 1 5 4 6C. 2 1 3 5 4 6 D. 2 3 1 4 6 5浜.闂姹傝В(鍏2棰,姣忛5鍒,鍏辫10鍒)1.(瀵绘壘鍋囧竵) 鐜版湁80鏋...
绛旓細1.鍐呴儴鎺掑簭鍜屽閮ㄦ帓搴 2.閭绘帴琛ㄥ拰鍗佸瓧閾捐〃 3.绾挎ц〃锛屾爲锛屽浘 4.63 5.胃锛坣锛夛紝胃锛坙g n锛夛紝胃锛坣 lg n锛6.鐩存帴瀹氬潃娉曪紝闅忔満娉 7.閾捐〃 8.鏍硅妭鐐0锛屽彾鑺傜偣4,9,10,7,8锛屾渶澶у害鐨勬槸0锛岃妭鐐0鐨勫悗浠ｆ槸1,2,3 9.绌虹殑鏉′欢鏍堥《浣嶇疆鏄痬-1.婊＄殑鏉′欢鏄爤椤朵綅缃槸-1 10锛屾暟鎹粨鏋勫拰...
