二叉树的建立和遍历
\u4e8c\u53c9\u6811\u7684\u5efa\u7acb\u4e0e\u904d\u5386(C\u8bed\u8a00)\u6709\u4e24\u4e2a\u9519\u8bef\uff1a1.\u5f53\u8bfb\u5165\u7684\u662f\u7a7a\u683c\u65f6\uff0cT\u8d4b\u503c\u4e3a\u7a7a\u4e0d\u9519\uff0c\u4f46\u6b64\u65f6\u5e94\u8be5\u8fd4\u56de\uff0c\u800c\u4e0d\u5e94\u8be5\u8fdb\u5165\u4e0b\u4e00\u4e2a\u5224\u65ad\u7684else\u5206\u53e5\uff0c\u697c\u4e3b\u7684\u4ee3\u7801\u5c31\u662f\u8fdb\u5165\u4e86if(ch=='#') exit(0);\u7684else\u5206\u53e5\u30022.\u53ef\u4ee5\u770b\u5230\u4e3b\u51fd\u6570\u4e2d\u5bf9createbitree\u7684\u8c03\u7528\u9700\u8981\u7528\u4e00\u4e2a\u6307\u9488\u627f\u63a5\u8fd4\u56de\u503c\uff0c\u6240\u4ee5\u6839\u636e\u9012\u5f52\u8c03\u7528\u7684\u5f62\u5f0f\u4e0d\u53d8\uff0c\u5728createbitree\u4e2d\u8c03\u7528\u81ea\u8eab\u7684\u65f6\u5019\u4e5f\u8981\u627f\u63a5\u8fd4\u56de\u503c\u3002\u6839\u636e\u697c\u4e3b\u7684\u4ee3\u7801\u4fee\u6539\u5982\u4e0b\uff1a
#include
#include
#include
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree creatbitree(BiTree t) //\u5148\u5e8f\u5efa\u7acb\u4e8c\u53c9\u6811
{
BiTree T=t;
char ch;
ch=getchar();
if(ch==' ')
T=NULL;
else {
if(ch=='#')
exit(0);
else{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=ch;
T->lchild = creatbitree(T->lchild);
T->rchild = creatbitree(T->rchild);
}
}
return T;
}
void BiTreeTra(BiTree t) //\u5148\u5e8f\u904d\u5386\u4e8c\u53c9\u6811
{
if(t)
{
printf("%c",t->data);
BiTreeTra(t->lchild);
BiTreeTra(t->rchild);
}
}
void main()
{
BiTree tree;
BiTree T=NULL;
tree=creatbitree(T);
BiTreeTra(tree);
}
#include<stdlib.h>
typedef struct node *tree_pointer;
struct node{
char ch;
tree_pointer left_child,right_child;
};
tree_pointer root=NULL;
tree_pointer create(tree_pointer ptr)
{
char ch;
scanf("%c",&ch);
if(ch==' ')
ptr=NULL;
else{
ptr=(tree_pointer)malloc(sizeof(node));
ptr->ch=ch;
ptr->left_child=create(ptr->left_child);
ptr->right_child=create(ptr->right_child);
}
return ptr;
}
void preorder(tree_pointer ptr)
{
if(ptr){
printf("%c",ptr->ch);
preorder(ptr->left_child);
preorder(ptr->right_child);
}
}
void inorder(tree_pointer ptr)
{
if(ptr){
inorder(ptr->left_child);
printf("%c",ptr->ch);
inorder(ptr->right_child);
}
}
int leaf(tree_pointer ptr)
{
if(!ptr)
return 0;
else{
if(!ptr->left_child&&!ptr->right_child)
return 1;
return leaf(ptr->left_child)+leaf(ptr->right_child);
}
}
void main()
{
printf("构建一个二叉树：\n");
root=create(root);
printf("前序遍历二叉树：\n");
preorder(root);
printf("\n");
printf("中序遍历二叉树：\n");
inorder(root);
printf("\n");
printf("二叉树的叶子结点个数为%d\n",leaf(root));
}
#include<iostream>
using namespace std;
typedef struct tree
{
char data;
struct tree *lchild,*rchild;
}bitree;
void creattree(bitree *&T)
{
char data;
cin>>data;
if(data=='#')
T=NULL;
else
{ T=new(bitree);
T->data=data;
creattree(T->lchild);
creattree(T->rchild);}
}
void preorder(bitree *T)
{
if(T)
{
cout<<T->data<<" ";
preorder(T->lchild);
preorder(T->rchild);
}
}
void inorder(bitree *T)
{if(T){
inorder(T->lchild);
cout<<T->data<<" ";
inorder(T->rchild);}
}
void fallorder(bitree *T)
{if(T){
fallorder(T->lchild);
fallorder(T->rchild);
cout<<T->data<<" ";}
}
int depth(bitree *T)
{ int ldep,rdep;
if(T==NULL)
return 0;
else
{
ldep=depth(T->lchild);
rdep=depth(T->rchild);
return ldep>rdep?ldep+1:rdep+1;
}
}
int sumleaf(bitree *T)
{
int sum=0,n,m;
if(T ){
if((!T->lchild )&&(!T->rchild ))
sum++;
n=sumleaf(T->lchild);
sum+=n;
m=sumleaf(T->rchild);
sum+=m;
}
return sum;
}
int main()
{
bitree *T=NULL;
creattree(T);
cout<<"pre:";
preorder(T);
cout<<endl;
cout<<"in :";
inorder(T);
cout<<endl;
cout<<"fal:";
fallorder(T);
cout<<endl;
cout<<"the depth:" ;
cout<<depth(T);
cout<<endl;
cout<<sumleaf(T);
return 0;
}
绛旓細浜屽弶鏍戦亶鍘鏂规硶鏈甯哥敤鐨勫ぇ鑷存湁鍥涚锛氬厛搴忛亶鍘嗭紝涔熷彨鍏堟牴閬嶅巻銆傚氨鏄厛璁块棶鏍圭粨鐐癸紝鍐嶈闂乏瀛愭爲锛屾渶鍚庤闂彸瀛愭爲銆備腑搴忛亶鍘嗭紝涔熷彨涓牴閬嶅巻銆傚氨鏄厛璁块棶宸﹀瓙鏍戯紝鍐嶈闂牴鑺傜偣锛屾渶鍚庤闂彸瀛愭爲銆傚悗搴忛亶鍘嗭紝涔熷彨鍚庢牴閬嶅巻銆傚氨鏄厛璁块棶宸﹀瓙鏍戯紝鍐嶈闂彸瀛愭爲锛屾渶鍚庤闂牴缁撶偣銆傛寜灞傛閬嶅巻锛屽氨鏄浜屽弶鏍戜粠涓...
绛旓細閬嶅巻鐨勬柟娉曟湁锛氬眰搴忛亶鍘嗐佸厛搴忛亶鍘嗐佷腑搴忛亶鍘嗐佸悗搴忛亶鍘嗙瓑锛屼互涓嬮潰鐨浜屽弶鏍涓轰緥浠嬬粛閬嶅巻 E / \ B F / \ \ A D H / / \ C G I \ K / J 1.灞傚簭閬嶅巻 鍗充粠涓婂埌涓嬫寜灞傛璁块棶璇ユ爲锛屾瘡涓灞傚崟鐙緭鍑轰竴琛岋紝姣忎竴灞傝姹傝闂殑椤哄簭涓轰粠宸﹀埌鍙炽備緥瀛愪腑灞傚簭閬嶅巻...
绛旓細//鏍堢殑鎿嶄綔:渚涢潪閫掑綊鍏堝簭閬嶅巻鐢 #include"Traverse.c" //鍔熻兘妯″潡3-voidPreOrderTraverse(BSTreeT,Status(*Visit)(ElemTypee));闈為掑綊鍏堝簭閬嶅巻浜屽弶鏍 //voidInOrderTraverse(BSTreeT,Status(*Visit)(ElemTypee));涓簭閬嶅巻浜屽弶鏍 //voidPostOrderTraverse(BSTreeT,Status(*Visit)(ElemTypee));鍚庡簭閬嶅巻浜屽弶鏍 ...
绛旓細瀵逛换鎰忕粰瀹氱殑浜屽弶鏍(椤剁偣鏁拌嚜瀹)寤虹珛瀹冪殑浜屽弶閾捐〃瀛樺偍缁撴瀯,骞跺埄鐢ㄦ爤鐨勪簲绉嶅熀鏈繍绠(缃┖鏍堛佽繘鏍堛佸嚭鏍堛佸彇鏍堥《鍏冪礌銆佸垽鏍堢┖)瀹炵幇浜屽弶鏍戠殑鍏堝簭銆佷腑搴忋佸悗搴忎笁绉閬嶅巻,杈撳嚭涓夌閬... 瀵逛换鎰忕粰瀹氱殑浜屽弶鏍(椤剁偣鏁拌嚜瀹)寤虹珛瀹冪殑浜屽弶閾捐〃瀛樺偍缁撴瀯,骞跺埄鐢ㄦ爤鐨勪簲绉嶅熀鏈繍绠(缃┖鏍堛佽繘鏍堛佸嚭鏍堛佸彇鏍堥《鍏冪礌銆佸垽...
绛旓細int createTree(); //鍒涘缓鏍 int preTravel(); //鍏堝簭閬嶅巻鏍 int inTravel(); //涓簭閬嶅巻鏍 };struct treeNode * createBT(struct treeNode *bt, int k){ char b;struct treeNode *p, *t;b = getchar();if (b != '0'){ p = (struct treeNode *)malloc(sizeof(struct tree...
绛旓細閬嶅巻搴忓垪 1锛閬嶅巻浜屽弶鏍戠殑鎵ц韪抗 涓夌閫掑綊閬嶅巻绠楁硶鐨勬悳绱㈣矾绾跨浉鍚岋紙濡備笅鍥捐櫄绾挎墍绀猴級銆傚叿浣撶嚎璺负锛氫粠鏍圭粨鐐瑰嚭鍙戯紝閫嗘椂閽堟部鐫浜屽弶鏍戝缂樼Щ鍔紝瀵规瘡涓粨鐐瑰潎閫斿緞涓夋锛屾渶鍚庡洖鍒版牴缁撶偣銆2锛庨亶鍘嗗簭鍒 A / \ B C / / \ D E F 鍥 锛1锛 涓簭搴忓垪锛坕norder traversal锛変腑搴忛亶鍘嗕簩鍙夋爲鏃讹紝瀵圭粨鐐圭殑...
绛旓細printf("鍏堝簭閫掑綊閬嶅巻浜屽弶鏍c:\n");PreOrderTraverse(c,visit);printf("灏嗘爲C鎻掑叆鏍慣涓,璇疯緭鍏ユ爲T涓爲C鐨勫弻浜茬粨鐐笴涓哄乏(0)鎴栧彸(1)瀛愭爲:");scanf("%d,%d",&e1,&i);p=Point(T,e1);//p鎸囧悜浜屽弶鏍慣涓皢T涓綔涓轰簩鍙夋爲C鐨勫弻浜茬粨鐐圭殑e1InsertChild(p,i,c);//灏嗘爲C鎻掑叆鍒颁簩鍙夋爲T涓綔涓虹粨鐐圭殑宸...
绛旓細鍓嶅簭锛欰BCDEFG 涓簭锛欳BDAFGE 鍏堟潵鐢浜屽弶鏍銆傚墠搴忎腑绗竴涓繀瀹氭槸鏍癸紝閭ｄ箞A蹇呭畾鏄牴銆傚啀鐪嬩腑搴,鏃㈢劧A鏄牴锛岄偅涔圕BD鍦ˋ宸﹁竟锛屽繀瀹氭槸A鐨勫乏瀛愭爲銆侳GE鍦ˋ鐨勫彸杈瑰繀瀹氭槸A鐨勫彸瀛愭爲銆傚湪鍒嗗埆鐪婥BD 鍜 FGE 鍓嶅簭锛欱CD 閭ｄ箞B蹇呭畾鏄乏瀛愭爲鐨勬牴銆傝屼腑搴忥細CBD锛孋蹇呭畾鍦˙宸﹁竟锛孌蹇呭畾鍦˙鍙宠竟銆傛墍浠ュ乏瀛愭爲浣...
绛旓細/*---闈為掑綊---鍏堝簭寤虹珛浜屽弶鏍---*/ bitree *createprebitree(){char ch;bitree *ht,*p,*q;sqstack *s;s=malloc(sizeof(bitree)); //鍔犱笂杩欎竴鍙ヤ负s 鍒濆鍖栧紑杈熺┖闂 ch=getchar();if(ch!='#'&&ch!='\n') /* 杈撳叆浜屽弶鏍戝厛搴忛『搴 鏄互瀹屽叏浜屽弶鏍戠殑鍏堝簭椤哄簭 涓嶆槸...
绛旓細//===鍒╃敤"鍏堣繘鍏堝嚭"锛團IFO锛夐槦鍒楋紝鎸夊眰娆閬嶅巻浜屽弶鏍=== void Levelorder(BinTree T){ int front=0,rear=1;BinTNode *cq[Max],*p; //瀹氫箟缁撶偣鐨勬寚閽堟暟缁刢q cq[1]=T; //鏍瑰叆闃 while(front!=rear){ front=(front+1)%NodeNum;p=cq[front]; //鍑洪槦 printf("%c",p->data); /...
