二叉樹的課程設計

⑴ C++二叉樹的課程設計

《數據結構》實驗三——二叉樹排序演算法
*試編寫演算法，對一棵二叉樹根結點不變，將左、右子樹進行交換，樹中每個結點的左、右子樹進行交換。*/
Exchange(pBiNode BiTree)
{
pBiNode p;
if(BiTree)
{
p = BiTree->lChild;
BiTree->lChild = BiTree->rChild;
BiTree->rChild = p;
Exchange(BiTree->lChild);
Exchange(BiTree->rChild);
}
}
/*這個演算法要求同學必須掌握*/
《數據結構》實驗三——動態查找
*
1.試按表(10,8,9,12,20,5,6,15,19,25)中元素的排列次序，將所有元素插入一棵初始為空的二叉排序樹中，使之仍是一棵二叉排序樹，請設計演算法
2.在已構建的二叉排序樹中插入元素40，使之依然為二叉排序樹
*/

#include <malloc.h>
typedef struct node
{
int data;
struct node * lChild,*rChild;
}node,*BTNode;
BTNode Create(BTNode BiTree)
{
int n;
BTNode p,q;
scanf("%d",&n);
for(;n != 0;)
{
p = (BTNode)malloc(sizeof(struct node));
p->data = n;
p->lChild = NULL;
p->rChild = NULL;
if(!BiTree)
BiTree = p;
else
{ q = BiTree;
while(q->data != n)
{
if(q->data > n)
if(q->lChild != NULL)
q = q->lChild;
else
q->lChild = p;
else if(q->rChild != NULL)
q = q->rChild;
else
q->rChild = p;
}
}
scanf("%d",&n);
}
return BiTree;
}
InOrderTraverse(BTNode BiTree)
{
if(BiTree)
{
InOrderTraverse(BiTree->lChild);
printf("%4d",BiTree->data);
InOrderTraverse(BiTree->rChild);
}
}
Insert(BTNode BiTree,int n)
{
BTNode p,q = BiTree;
while(q->data != n)
{
if(q->data > n)
if(q->lChild != NULL)
q = q->lChild;
else
{
p = (BTNode)malloc(sizeof(struct node));
p->data = n;
p->lChild = p->rChild = NULL;
q->lChild = p;
}
else if(q->rChild != NULL)
q = q->rChild;
else
{
p = (BTNode)malloc(sizeof(struct node));
p->data = n;
p->lChild = p->rChild = NULL;
q->rChild = p;
}
}

}
main()
{
BTNode BTRoot;
BTRoot = NULL;
BTRoot = Create(BTRoot);
printf("\n Sorted numbers are:\n");
InOrderTraverse(BTRoot);
Insert(BTRoot,40);
printf("\nAfter instert numbers are:\n");
InOrderTraverse(BTRoot);
printf("\n");
}
*將序列（13,15,22,8,34,19,21）插入到一個初始時是空的哈希表中，哈希函數採用hash(x)=1+(x MOD 7)。使用線性探測法解決沖突*/

#define N 8
struct number
{
int data;
int flag; /*沖突與否標志*/
}hx[N] = {0};
Create_hxTable(struct number a[])
{
int i,j,n;
for(i = 1;i < 8;i++)
{
scanf("%d",&n);
j= 1 + n % 7;
while(a[j].flag)
j = (j + 1) % N;
a[j].data = n;
a[j].flag = 1;
}
}
main()
{
int i;
Create_hxTable(hx);
for(i = 0;i < N;i++)
{
if(hx[i].flag)
printf("%3d",hx[i].data);
else
printf(" * ");
}
printf("\n");
}
Joseph演算法實現
#include <malloc.h>
typedef struct s
{
int no,password;
struct s *next;
}*node;
node create_cycle(int n)
{
node head,end,p;
int i;
head = NULL;
end = NULL;
printf("Please input %d passwords(password > 0)\n",n);
for(i = 1;i <= n;i++)
{
p = (node)malloc(sizeof(struct s));
scanf("%d",&p->password);
p->no = i;
if(!head)
{
head = p;
end = p;
}
else
{
end->next = p;
end = p;
}
}
end->next = head;
head = end;
return head;
}
void out_link(node head,int n,int m)
{
int i,j,k = m;
node p = head,q;
for(i = 1;i < n;i++)
{
for(j = 1;j < k;j++)
p = p->next;
q = p->next;
k = q->password;
p->next = q->next;
printf("%3d",q->no);
free(q);
}
printf("%3d",p->no);
free(p);
}
void main()
{
node head;
int n,m;
printf("Please input numbers of people and init_password\n");
scanf("%d%d",&n,&m);
head = create_cycle(n);
printf("Out link sequence is:\n");
out_link(head,n,m);
printf("\n");
}
串操作：判斷子串
int find(char *c1,char *c2)
{
int flag = -1,i,j;
for(i = 0;*(c1 + i);i++)
{
j = 0;
if(*(c1 + i) == *(c2 + j))
{
flag = i;
for(;*(c1 + i) && *(c2 + j) && *(c1 + i) == *(c2 + j);i++,j++) ;
/*空循環，繼續判斷是否匹配*/
if(*(c2 + j) == '\0') /*找到匹配的串*/
break;
else
flag = -1;
}

}
return flag;
}
void main()
{
char c1[30],c2[30];
int f;
scanf("%s%s",c1,c2);
f = find(c1,c2);
if(f == -1)
printf("No\n");
else
printf("Yes! Position is %d\n",f + 1);
}
/*找二叉樹的葉節點及統計葉節點個數*/

int ShowLeaves(pBiNode BiTree)
{
static int i = 0;
if(BiTree)
{
ShowLeaves(BiTree->lChild);
ShowLeaves(BiTree->rChild);
if((BiTree->lChild==NULL)&&(BiTree->rChild==NULL))
{
printf("%c",BiTree->data);
i++;
}
}
return i;
}
/*求二叉樹的深度*/
int Depth(pBiNode BiTree)
{
int dep1,dep2;
if(BiTree==NULL)return 0;
else
{
dep1=Depth(BiTree->lChild);
dep2=Depth(BiTree->rChild);
return dep1>dep2? dep1+1: dep2+1;
}
}
二叉樹的創建和遍歷(遞歸)
#include <malloc.h>
typedef struct BiNode
{
char data;
struct BiNode *lChild,*rChild;
}BiNode,*pTree;
CreateTree(pTree *BTRoot)
{
char ch;
scanf("%c",&ch);
if(ch == '#')
(*BTRoot) = NULL;
else
{
(*BTRoot) = (pTree)malloc(sizeof(BiNode));
(*BTRoot)->data = ch;
CreateTree(&((*BTRoot)->lChild));
CreateTree(&((*BTRoot)->rChild));
}
}
PreOrderTraverse(pTree pRoot)
{
if(pRoot)
{
printf("%c ",pRoot->data);
PreOrderTraverse(pRoot->lChild);
PreOrderTraverse(pRoot->rChild);
}

}
InOrderTraverse(pTree pRoot)
{
if(pRoot)
{
InOrderTraverse(pRoot->lChild);
printf("%c ",pRoot->data);
InOrderTraverse(pRoot->rChild);
}

}
PostOrderTraverse(pTree pRoot)
{
if(pRoot)
{

PostOrderTraverse(pRoot->lChild);
PostOrderTraverse(pRoot->rChild);
printf("%c ",pRoot->data);
}

}
main()
{
pTree root = NULL;
CreateTree(&root);
printf("\n\nPreOrder is :\n");
PreOrderTraverse(root);
printf("\n\nInOrder is :\n");
InOrderTraverse(root);
printf("\n\nPostOrder is :\n");
PostOrderTraverse(root);
printf("\n");
}
循環鏈表的建立及兩循環鏈表的鏈接

#include <malloc.h>
typedef struct s
{
int num;
struct s *next;
}*ls;
ls creat()
{
ls head,p,end;
int i;
static int n = 501;
head = (ls)malloc(sizeof(struct s));
head->next = NULL;
end = head;

for(i = 1;i <= 10;i++)
{ p = (ls)malloc(sizeof(struct s));
p->num = n++;
end->next = p;
end = p;
}
p->next = head;
return head;
}
ls link_two(ls h1,ls h2)
{
ls end1,end2,p;
for(p = h1->next;p->next != h1;p = p->next)

end1 = p;
for(p = h2->next;p->next != h2;p = p->next)

end2 = p;
end1->next = h2->next;
end2->next = h1;
free(h2);
return h1;
}

main()
{
ls head1,head2,head,p;
head1 = creat();
head2 = creat();
head = link_two(head1,head2);
for(p = head->next;p != head;p = p->next)
printf("%5d",p->num);
}
與課堂上講的稍修改了下，把n改為了靜態變數static int n = 501;
creat()函數不帶參數

單鏈表的建立、節點查找、插入、刪除等操作實現
#include <malloc.h>
typedef struct s
{
int num;
struct s *next;
}*ls;
ls creat()
{
ls head,p,end;
int i,n = 501;
head = (ls)malloc(sizeof(struct s));
head->next = NULL;
end = head;

for(i = 1;i <= 10;i++)
{ p = (ls)malloc(sizeof(struct s));
p->num = n++;
end->next = p;
end = p;
}
p->next = NULL;
return head;
}

ls find_front(ls head,ls e)
{
ls p;
p = head->next;
for(;p->next && p->next->num != e->num;p = p->next)

if(p->next->num == e->num)

return p;

else return NULL;
}
void insert_front(ls head,ls e,ls f)
{
ls p;
p = find_front(head,e);
f->next = p->next;
p->next = f;
}

main()
{
ls head,p,e,f;
head = creat();
for(p = head->next;p;p = p->next)
printf("%5d",p->num);
printf("\n");
e = (ls)malloc(sizeof(struct s));
f = (ls)malloc(sizeof(struct s));
scanf("%d%d",&e->num,&f->num);
e->next = NULL;
f->next = NULL;
/*p = find_front(head,e);*/
insert_front(head,e,f);
printf("Inerted!\n");
for(p = head->next;p;p = p->next)
printf("%5d",p->num);

}

節點刪除
void delete(ls head,ls e)
{
ls p,q;
p = find_front(head,e);
q = p->next;
p->next = p->next->next;
free(q);
}
堆棧操作（檢驗符號匹配實例）
#include <malloc.h>
#include <stdio.h>
typedef struct stack
{
char c;
struct stack *next;
}*node;

node push(node top,node new) /*入棧*/
{
if(top == NULL)
top = new;
else
{
new->next = top;
top = new;
}
return top;
}
node pop(node top) /*出棧*/
{
node p;
if(!top)
{
printf("NULL stack\n");
return NULL;
}

else
{
p = top;
top = top->next;
free(p);
return top;
}

}
char top_data(node top) /*取棧頂數據*/
{
char ch = 0;
if(!top)
return 0;
else
ch = top->c;
return ch;
}
void main()
{
char ch;
node top = NULL,p;
for(;(ch = getchar()) != '\n';) /*輸入表達式*/
{
if(ch == '(' ||ch == '[' ||ch == '{')
{
p = (node)malloc(sizeof(struct stack));
p->c = ch;
p->next = NULL;
top =push(top,p);
}
else if(ch == ')')
{
if(top_data(top) != '(')
{
printf("No\n");
exit();
}
else
top = pop(top);
}
else if(ch == ']')
{
if(top_data(top) != '[')
{
printf("No\n");
exit();
}
else
top = pop(top);
}
else if(ch == '}')
{
if(top_data(top) != '{')
{
printf("No\n");
exit();
}
else
top = pop(top);
}
}
if(top)
printf("No\n");
else
printf("Yes\n");

}

⑵ 【數據結構】課程設計:二叉樹的設計與遍歷

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
//定義二叉樹鏈表
struct Bitree
{
char c;
struct Bitree *lchild,*rchild;
};
//定義隊列
struct Quene
{
struct Bitree *p;//指向數的節點的指針
struct Quene *next;
};
//定義哈夫曼樹的結構
struct Huffman
{
int weight;//權值
int tag;
int parent,lchild,rchild;
char ch;
};

struct Bitree *creatBt()
{
struct Bitree *btree;
char ch;
cin>>ch;
// "訪問"操作為生成根結點
if(ch!='#')
{
btree=(struct Bitree * )malloc(sizeof(struct Bitree )) ;
btree->c=ch;
btree->lchild=creatBt(); // 遞歸建(遍歷)左子樹
btree->rchild=creatBt(); // 遞歸建(遍歷)右子樹
}
if(ch=='#')
{
btree=NULL;
}
return btree;
}
//先序遍歷遞歸
void preOrder1(struct Bitree *btree)
{
struct Bitree *p;
p=btree;
if(p!=NULL)
{
cout<<p->c<<" ";
preOrder1(p->lchild);
preOrder1(p->rchild);
}
}
//中序遍歷遞歸
void inOrder1(struct Bitree *btree)
{
struct Bitree *p;
p=btree;

if(p->lchild!=NULL)
inOrder1(p->lchild);
cout<<p->c<<" ";
if(p->rchild!=NULL)
inOrder1(p->rchild);
}
//後序遍歷遞歸
void postOrder1(struct Bitree *btree)
{
struct Bitree *p;
p=btree;

if(p->lchild!=NULL)
postOrder1(p->lchild);
if(p->rchild!=NULL)
postOrder1(p->rchild);
cout<<p->c<<" ";

}
//非遞歸先序遍歷
void preOrder2(struct Bitree *btree)
{
struct Bitree *p, *node[MAX];
int top=0;
p=btree;
do
{
while(p!=NULL)
{
cout<<p->c<<" ";
node[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{
top--;
p=node[top];
p=p->rchild;
}
}
while(top>0||p!=NULL);
}
//非遞歸中序遍歷
void inOrder2(struct Bitree *btree)
{
struct Bitree *p, *node[MAX];
int top=0;
p=btree;
do// while(top>0||p!=NULL)
{
while(p!=NULL)
{
node[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{
top--;
p=node[top];
cout<<p->c<<" ";
p=p->rchild;
}
} while(top>0||p!=NULL);
}
//非遞歸後序遍歷
void postOrder2(struct Bitree *btree)
{
struct Bitree *p, *node[MAX];
int top=0;
p=btree;
while(top>0||p!=NULL)
{
while(p!=NULL)
{
node[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{
top--;
p=node[top];
if(p->rchild==NULL)
cout<<p->c<<" ";
p=p->rchild;
}
}
p=btree;
cout<<p->c<<" ";
}
//二叉樹的高度
int btHeigh(struct Bitree *btree)
{
struct Bitree *p;
p=btree;
int hl=0, h2=0, max=0;
if(p!=NULL)
{
hl=btHeigh(p->lchild); //求左子樹的深度
h2=btHeigh(p->rchild); //求右子樹的深度
max=hl>h2?hl: h2;
return(max+1);// 返回樹的深度
}
else
return 0;
}
//求二叉樹的葉子個數
int numLeave(struct Bitree *btree)
{
struct Bitree *p;
p=btree;
int static n=0;//靜態變數計數
if(p!=NULL)
{
if(p->lchild==NULL&&p->rchild==NULL)
n++; //若root所指結點為葉子, 則累加
numLeave(p->lchild);
numLeave(p->rchild);
return n;
}
else
return 0;
}
//藉助隊列實現二叉樹的層次遍歷。
void btQuene(struct Bitree *btree)
{
struct Quene *head,*rear,*temp;
head=(struct Quene*)malloc(sizeof(struct Quene));//給隊列頭指針分配器空間
head->p=btree;
head->next=NULL;
rear=head;
while(head!=NULL)
{
if(head->p->lchild!=NULL)
{
temp=(struct Quene *)malloc(sizeof(struct Quene));//中間變數暫時保存數的結點
temp->p=head->p->lchild;
temp->next=NULL;
rear->next=temp;//將新結點連接在前一個結點的後面
rear=temp;
}
if(head->p->rchild!=NULL)
{
temp=(struct Quene *)malloc(sizeof(struct Quene));
temp->p=head->p->rchild;
temp->next=NULL;
rear->next=temp;
rear=temp;
}
temp=head;
cout<<head->p->c;
head=head->next;
free(temp);
}
}
//建立哈夫曼樹
void creatHfm()
{
struct Huffman *HF;
int num;
int i,j,x1,x2,m1,m2;
cout<<"輸入字元個數；";
cin>>num;
if(num<=1)
{
cout<<"不能建立哈夫曼樹！"<<endl;
return ;
}
HF=new struct Huffman[2*num-1];
char c;
//構造葉子結點數為num,權值為weight的哈夫曼樹HF[]
for(i=0;i<num;i++)
{
cout<<"請輸入第"<<i+1<<"個字元值:";
cin>>c;
HF[i].ch=c;
cout<<"請輸入該字元的權值:";
cin>>HF[i].weight;
HF[i].parent=-1;
HF[i].lchild=-1;
HF[i].rchild=-1;
HF[i].tag=0;
}
//構造非葉子結點
for(i=0;i<num-1;i++)//合並n-1次
{
m1=m2=32767;//m1是最小值單元，m2為次小值
x1=x2=0;//x1，x2為下標號
for(j=0;j<num+1;j++)//找最小權值和次小權值
{
if(HF[i].weight<m1&&HF[j].tag==0)
{
m2=m1;
x2=x1;
m1=HF[j].weight;
x1=j;
}
else if(HF[j].weight<m2&&HF[j].tag==0)
{
m2=HF[j].weight;
x2=j;
}
}
//將兩棵子樹合並成一棵新樹
HF[x1].parent=num+i;//x1,x2對應的子樹分別作為n+i的左右子樹
HF[x2].parent=num+i;
HF[x1].tag=1;
HF[x2].tag=1;
HF[num+i].weight=HF[x1].weight+HF[x2].weight;//新書跟的權值為左右樹根的權值之和
HF[num+i].lchild=x1;//n+i的做孩子是x1
HF[num+i].rchild=x2;
}
cout<<"哈夫曼樹創建成功!"<<endl;
}

//刪除值為x的結點，並釋放相應的空間
void btFree(struct Bitree *btree,char x)
{
struct Bitree *p;
p=btree;
if(p!=NULL)
{
if(p->c==x)
{
free(p);
cout<<"釋放成功！"<<endl;
}
else
{
btFree(p->lchild,x);
btFree(p->rchild,x);
}

}
else
cout<<"空間釋放失敗！"<<endl;
}
void main()
{
int key;
int depth;
int numLea;
struct Bitree *btree;
cout<<"輸入數的節點，'#'表示空節點:"<<endl;
btree=creatBt();
cout<<"二叉樹創建成功!"<<endl;
cout<<endl;

cout<<"***********************************"<<endl;
cout<<" 選擇菜單 "<<endl;
cout<<"1、遞歸先序遍歷二叉樹 "<<endl;
cout<<"2、遞歸中序遍歷二叉樹 "<<endl;
cout<<"3、遞歸後序遍歷二叉樹 "<<endl;
cout<<"4、非遞歸先序遍歷二叉樹 "<<endl;
cout<<"5、非遞歸中序遍歷二叉樹 "<<endl;
cout<<"6、非遞歸後序遍歷二叉樹 "<<endl;
cout<<"7、求二叉樹的高度 "<<endl;
cout<<"8、求二叉樹的葉子結點個數 "<<endl;
cout<<"9、隊列實現二叉樹層次遍歷"<<endl;
cout<<"10、建立哈夫曼樹 "<<endl;
cout<<"11、釋放空間 "<<endl;
cout<<"***********************************"<<endl;
for(;key!=0;)
{
cout<<"輸入選項，(0表示結束操作):";
cin>>key;
switch(key)
{

case 1:
cout<<"遞歸先序遍歷結果是:";
preOrder1(btree);
cout<<endl;
break;
case 2:
cout<<"遞歸中序遍歷結果是:";
inOrder1(btree);
cout<<endl;
break;
case 3:
cout<<"遞歸後序遍歷結果是:";
postOrder1(btree);
cout<<endl;
break;
case 4:
cout<<"非遞歸先序遍歷結果是:";
preOrder2(btree);
cout<<endl;
break;
case 5:
cout<<"非遞歸中序遍歷結果是:";
inOrder2(btree);
cout<<endl;
break;
case 6:
cout<<"非遞歸後序遍歷結果是:";
postOrder2(btree);
cout<<endl;
break;
case 7:
depth=btHeigh(btree);
cout<<"二叉樹的高度為";
cout<<depth<<endl;
break;
case 8:
numLea=numLeave(btree);
cout<<"二叉樹的葉子結點數為";
cout<<numLea<<endl;
break;
case 9:
cout<<"層次遍歷的結果為:";
btQuene(btree);
cout<<endl;
break;
case 10:
creatHfm();
break;
case 11:
char c;
cout<<"輸入要釋放的結點:";
cin>>c;
btFree(btree,c);
break;
default:
printf("\n輸入選項錯誤！\n ");
}
}
}

⑶ 寫一份 數據結構課程設計報告。兩個部分為：二叉樹的遍歷和查找（折半查找）的實現

二叉樹的遍歷

#include<iostream>
#include<cstring>
#definemaxLength32
usingnamespacestd;
typedefstructbinaryNode
{
chardata;
structbinaryNode*lchild,*rchild;
}binaryNode;
voidcreateByPreAndIn(charpreArray[],charinArray[],binaryNode*&parent,intpreStart,intpreEnd,intinStart,intinEnd);
voidcreateByLastAndIn(charlastArray[],charinArray[],binaryNode*&parent,intlastEnd,intlastStart,intinStart,intinEnd);
voidpreOrderVisit(binaryNode*root);
voidinOrderVisit(binaryNode*root);
voidlastOrderVisit(binaryNode*root);
voidrugged(binaryNode*root,int);
voidbrackets(binaryNode*root);
voidlevel(binaryNode*root);
voiddisplay(binaryNode*root);
intmain(void)
{
charpreArray[maxLength],inArray[maxLength],lastArray[maxLength];
binaryNode*root;
cout<<"構造二叉樹，輸入構造方式。(1代表前中序，其它數字代表後中序):";
intway;
cin>>way;
if(way==1)
{
cout<<"輸入前序遍歷序列:";
cin>>preArray;
cout<<"輸入中序遍歷序列:";
cin>>inArray;

createByPreAndIn(preArray,inArray,root,0,strlen(preArray)-1,0,strlen(inArray)-1);
}
elseif(way==2)
{
cout<<"輸入後序遍歷序列:";
cin>>lastArray;
cout<<"輸入中序遍歷序列:";
cin>>inArray;
createByLastAndIn(lastArray,inArray,root,0,strlen(lastArray)-1,0,strlen(inArray)-1);
}//initialization
cout<<"構造完成,下列是該二叉樹的表示方式"<<endl;
display(root);
cout<<"按enter鍵繼續...";
cin.get();cin.get();

return0;
}
voidcreateByPreAndIn(charpreArray[],charinArray[],binaryNode*&parent,intpreStart,intpreEnd,intinStart,intinEnd)
{
if(preStart<=preEnd)
{
parent=newbinaryNode;
parent->data=preArray[preStart],parent->lchild=parent->rchild=NULL;
intmiddle=inStart;
while(inArray[middle]!=preArray[preStart]&&middle<=inEnd)
middle++;
createByPreAndIn(preArray,inArray,parent->lchild,preStart+1,preStart+middle-inStart,inStart,middle-1);
createByPreAndIn(preArray,inArray,parent->rchild,preStart+middle-inStart+1,preEnd,middle+1,inEnd);
}
}
voidcreateByLastAndIn(charlastArray[],charinArray[],binaryNode*&parent,intlastStart,intlastEnd,intinStart,intinEnd)
{
if(lastStart<=lastEnd)
{
parent=newbinaryNode;
parent->data=lastArray[lastEnd],parent->lchild=parent->rchild=NULL;
intmiddle=inStart;
while(inArray[middle]!=lastArray[lastEnd]&&middle<=inEnd)
middle++;
createByLastAndIn(lastArray,inArray,parent->lchild,lastEnd-inEnd+inStart,lastEnd-inEnd+middle-1,inStart,middle-1);
createByLastAndIn(lastArray,inArray,parent->rchild,lastEnd-inEnd+middle,lastEnd-1,middle+1,inEnd);
}
}
voidpreOrderVisit(binaryNode*root)
{
if(root)
{
std::cout<<root->data;
preOrderVisit(root->lchild);
preOrderVisit(root->rchild);
}
}
voidinOrderVisit(binaryNode*root)
{
if(root)
{
inOrderVisit(root->lchild);
std::cout<<root->data;
inOrderVisit(root->rchild);
}
}
voidlastOrderVisit(binaryNode*root)
{
if(root)
{
lastOrderVisit(root->lchild);
lastOrderVisit(root->rchild);
cout<<root->data;
}
}
voidrugged(binaryNode*root,intindent)
{
if(root)
{
for(intj=0;j<indent;j++)
std::cout<<"-";
indent++;
std::cout<<root->data;
std::cout<<std::endl;
rugged(root->lchild,indent+1);
rugged(root->rchild,indent+1);
}
}
voidlevel(binaryNode*root)
{
intfront=-1,rear=0;
binaryNode*buff[maxLength],*visit;
buff[rear]=root;
while(front!=rear)
{
front=(front+1)%maxLength;
visit=buff[front];
if(visit->lchild)
{
rear=(rear+1)%maxLength;
buff[rear]=visit->lchild;
}
if(visit->rchild)
{
rear=(rear+1)%maxLength;
buff[rear]=visit->rchild;
}
cout<<visit->data;
}
}
voidbrackets(binaryNode*root)
{
if(root)
{
std::cout<<root->data;
if(root->lchild||root->rchild)
std::cout<<'(';
brackets(root->lchild);
if(root->lchild&&root->rchild)
std::cout<<',';
brackets(root->rchild);
if(root->lchild||root->rchild)
std::cout<<')';
}
}
voiddisplay(binaryNode*root)
{
cout<<"前序遍歷:";
preOrderVisit(root);
cout<<endl;
cout<<"中序遍歷:";
inOrderVisit(root);
cout<<endl;
cout<<"後序遍歷:";
lastOrderVisit(root);
cout<<endl;
cout<<"層次遍歷:"<<endl;
level(root);
cout<<endl;
cout<<"凹入表示法:"<<endl;
rugged(root,0);
cout<<endl;
cout<<"括弧表示法:"<<endl;
brackets(root);
cout<<endl;
}

⑷ C語言課程設計，二叉樹，源程序已給出，求三種便利程序和注釋以及流程圖！

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

struct tree //定義結構體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 pretra(struct tree *head);
void midtra(struct tree *head);
void afttra(struct tree *head);

main ()
{
char s[100],c,key=' ' ;
struct tree *root=0 ;
do
{
printf("Enter a letter:");
gets(s);
//下面這個條件是我添加的，如果沒有這個條件最後會多一個info為NULL也就是0的值，因為是先gets(s)->賦值，最後才判斷*s是否為空
if(*s==0)
break;
if (!root)
root=create_btree(root,root,*s);
else
create_btree(root,root,*s);
}while(*s) ;

//printf("%d",root->left);

print_btree(root,0);
printf("前序遍歷:\n");
pretra(root);
printf("\n");
printf("中序遍歷:\n");
midtra(root);
printf("\n");
printf("後序遍歷:\n");
afttra(root);
printf("\n");
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 結束 */
//創建二叉樹,實際上創建的是一個有序二叉樹
struct tree *create_btree(struct tree *root,struct tree *r,char info)
{
if (r ==0 ) //也就是r==NULL
{
//r=new(struct tree);// same as function: malloc(sizeof())
r=(struct tree *)malloc(sizeof(struct tree)); //我這用前面那句老是編譯不過
if ( r == 0) //如果內存申請失敗，就報錯然後退出
{
printf("Out of memory\n");
return 0;
}
r->left=0; //初始化這個新結點
r->right=0;
r->info=info; //將輸入的字元賦值給這個結點
if (root) //如果root不為空
{
if(info<root->info) //如果info小於root的info，則新結點為root的左結點
root -> left=r;
else //否則為右結點
root -> right=r;
}
else
{
r->right=0; //如果root為空，那麼新結點的左右結點都設置為空
r->left=0;
}
return r; //返回新結點的指針的地址
} /* if = = 0 接下頁 */
if (info < r->info) //如果輸入的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) //如果跟結點為空，輸出該二叉樹是一個空二叉樹,並返回NULL
{
printf("Emptu btree\n");
return root;
}
while(root->info!=key) //如果當前結點不是要查找的結點
{
if(key<root->info) //如果要查找的結點小於當前結點，當前結點指向當前結點的左結點
root=root->left;
else
root=root->right; //如果key大於當前結點，則當前結點指向當前結點的右結點
if(root==0) //如果root為空，列印查找失敗
{
printf("Search Failure\n");
break ;
}
} /* while(root->info!=key) */
if (root !=0) //如果root不為空，也就是上面找到了root->info==key的值
printf("Successful search\n key=%c\n",root->info); //那麼返回找到的值
return root ; //分會該值的指針，如果沒找到是NULL,找到的話就是找到結點的指針
} /* *search_btree(root,key) */

//二叉樹的輸出
void print_btree(struct tree *r,int l)
{
int i;
if (r == 0)
return ; //如果r指針為空，該次調用返回
print_btree(r->left,l+1); //調用傳入結點的左子結點
for(i=0;i<l;i++) //列印l*2個空格
printf(" ");
printf("%c\n",r->info); //列印出該結點的info值
print_btree(r->right,l+1); //調用傳入結點的又子結點
}

void pretra(struct tree *head) //前序遍歷
{
if(NULL==head)
{
printf("這是一個空的二叉樹!\n");
return;
}
else
{
printf("%c",head->info);
if(head->left!=NULL)
pretra(head->left);
if(head->right!=NULL)
pretra(head->right);
}
}

void midtra(struct tree *head) //中序遍歷
{
if(NULL==head)
{
printf("這是一個空的二叉樹!\n");
return;
}
else
{
if(head->left!=NULL)
midtra(head->left);
printf("%c",head->info);
if(head->right!=NULL)
midtra(head->right);
}
}

void afttra(struct tree *head) //後序遍歷
{
if(NULL==head)
{
printf("這是一個空的二叉樹!\n");
return;
}
else
{
if(head->left!=NULL)
afttra(head->left);
if(head->right!=NULL)
afttra(head->right);
printf("%c",head->info);
}
}

⑸ 線索二叉樹課程設計

//二叉樹的二叉鏈表存儲的基本操作(22個)
Status InitBiTree(BiTree &T)
{ // 操作結果: 構造空二叉樹T
T=NULL;
return OK;
}

void DestroyBiTree(BiTree &T)
{ // 初始條件: 二叉樹T存在。操作結果: 銷毀二叉樹T
if(T) // 非空樹
{
if(T->lchild) // 有左孩子
DestroyBiTree(T->lchild); // 銷毀左孩子子樹
if(T->rchild) // 有右孩子
DestroyBiTree(T->rchild); // 銷毀右孩子子樹
free(T); // 釋放根結點
T=NULL; // 空指針賦0
}
}

void CreateBiTree(BiTree &T)
{ // 演算法6.4:按先序次序輸入二叉樹中結點的值（可為字元型或整型，在主程中
// 定義），構造二叉鏈表表示的二叉樹T。變數Nil表示空（子）樹。有改動
TElemType ch;
#ifdef CHAR
scanf("%c",&ch);
#endif
#ifdef INT
scanf("%d",&ch);
#endif
if(ch==Nil) // 空
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
if(!T)
exit(OVERFLOW);
T->data=ch; // 生成根結點
CreateBiTree(T->lchild); // 構造左子樹
CreateBiTree(T->rchild); // 構造右子樹
}
}

Status BiTreeEmpty(BiTree T)
{ // 初始條件: 二叉樹T存在
// 操作結果: 若T為空二叉樹,則返回TRUE,否則FALSE
if(T)
return FALSE;
else
return TRUE;
}

#define ClearBiTree DestroyBiTree

int BiTreeDepth(BiTree T)
{ // 初始條件: 二叉樹T存在。操作結果: 返回T的深度
int i,j;
if(!T)
return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild);
else
i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild);
else
j=0;
return i>j?i+1:j+1;
}

TElemType Root(BiTree T)
{ // 初始條件: 二叉樹T存在。操作結果: 返回T的根
if(BiTreeEmpty(T))
return Nil;
else
return T->data;
}

TElemType Value(BiTree p)
{ // 初始條件: 二叉樹T存在，p指向T中某個結點
// 操作結果: 返回p所指結點的值
return p->data;
}

void Assign(BiTree p,TElemType value)
{ // 給p所指結點賦值為value
p->data=value;
}

typedef BiTree QElemType; // 設隊列元素為二叉樹的指針類型
#include"c3-2.h"
#include"bo3-2.cpp"
TElemType Parent(BiTree T,TElemType e)
{ // 初始條件: 二叉樹T存在,e是T中某個結點
// 操作結果: 若e是T的非根結點,則返回它的雙親,否則返回＂空＂
LinkQueue q;
QElemType a;
if(T) // 非空樹
{
InitQueue(q); // 初始化隊列
EnQueue(q,T); // 樹根入隊
while(!QueueEmpty(q)) // 隊不空
{
DeQueue(q,a); // 出隊,隊列元素賦給a
if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e) // 找到e(是其左或右孩子)
return a->data; // 返回e的雙親的值
else // 沒找到e,則入隊其左右孩子指針(如果非空)
{
if(a->lchild)
EnQueue(q,a->lchild);
if(a->rchild)
EnQueue(q,a->rchild);
}
}
}
return Nil; // 樹空或沒找到e
}

BiTree Point(BiTree T,TElemType s)
{ // 返回二叉樹T中指向元素值為s的結點的指針。另加
LinkQueue q;
QElemType a;
if(T) // 非空樹
{
InitQueue(q); // 初始化隊列
EnQueue(q,T); // 根結點入隊
while(!QueueEmpty(q)) // 隊不空
{
DeQueue(q,a); // 出隊,隊列元素賦給a
if(a->data==s)
return a;
if(a->lchild) // 有左孩子
EnQueue(q,a->lchild); // 入隊左孩子
if(a->rchild) // 有右孩子
EnQueue(q,a->rchild); // 入隊右孩子
}
}
return NULL;
}

TElemType LeftChild(BiTree T,TElemType e)
{ // 初始條件: 二叉樹T存在,e是T中某個結點
// 操作結果: 返回e的左孩子。若e無左孩子,則返回＂空＂
BiTree a;
if(T) // 非空樹
{
a=Point(T,e); // a是結點e的指針
if(a&&a->lchild) // T中存在結點e且e存在左孩子
return a->lchild->data; // 返回e的左孩子的值
}
return Nil; // 其餘情況返回空
}

TElemType RightChild(BiTree T,TElemType e)
{ // 初始條件: 二叉樹T存在,e是T中某個結點
// 操作結果: 返回e的右孩子。若e無右孩子,則返回＂空＂
BiTree a;
if(T) // 非空樹
{
a=Point(T,e); // a是結點e的指針
if(a&&a->rchild) // T中存在結點e且e存在右孩子
return a->rchild->data; // 返回e的右孩子的值
}
return Nil; // 其餘情況返回空
}

TElemType LeftSibling(BiTree T,TElemType e)
{ // 初始條件: 二叉樹T存在,e是T中某個結點
// 操作結果: 返回e的左兄弟。若e是T的左孩子或無左兄弟,則返回＂空＂
TElemType a;
BiTree p;
if(T) // 非空樹
{
a=Parent(T,e); // a為e的雙親
p=Point(T,a); // p為指向結點a的指針
if(p->lchild&&p->rchild&&p->rchild->data==e) // p存在左右孩子且右孩子是e
return p->lchild->data; // 返回p的左孩子(e的左兄弟)
}
return Nil; // 樹空或沒找到e的左兄弟
}

TElemType RightSibling(BiTree T,TElemType e)
{ // 初始條件: 二叉樹T存在,e是T中某個結點
// 操作結果: 返回e的右兄弟。若e是T的右孩子或無右兄弟,則返回＂空＂
TElemType a;
BiTree p;
if(T) // 非空樹
{
a=Parent(T,e); // a為e的雙親
p=Point(T,a); // p為指向結點a的指針
if(p->lchild&&p->rchild&&p->lchild->data==e) // p存在左右孩子且左孩子是e
return p->rchild->data; // 返回p的右孩子(e的右兄弟)
}
return Nil; // 樹空或沒找到e的右兄弟
}

Status InsertChild(BiTree p,int LR,BiTree c) // 形參T無用
{ // 初始條件: 二叉樹T存在,p指向T中某個結點,LR為0或1,非空二叉樹c與T
// 不相交且右子樹為空
// 操作結果: 根據LR為0或1,插入c為T中p所指結點的左或右子樹。p所指結點的
// 原有左或右子樹則成為c的右子樹
if(p) // p不空
{
if(LR==0)
{
c->rchild=p->lchild;
p->lchild=c;
}
else // LR==1
{
c->rchild=p->rchild;
p->rchild=c;
}
return OK;
}
return ERROR; // p空
}

Status DeleteChild(BiTree p,int LR) // 形參T無用
{ // 初始條件: 二叉樹T存在,p指向T中某個結點,LR為0或1
// 操作結果: 根據LR為0或1,刪除T中p所指結點的左或右子樹
if(p) // p不空
{
if(LR==0) // 刪除左子樹
ClearBiTree(p->lchild);
else // 刪除右子樹
ClearBiTree(p->rchild);
return OK;
}
return ERROR; // p空
}

void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ // 初始條件: 二叉樹T存在,Visit是對結點操作的應用函數。演算法6.1，有改動
// 操作結果: 先序遞歸遍歷T,對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{
Visit(T->data); // 先訪問根結點
PreOrderTraverse(T->lchild,Visit); // 再先序遍歷左子樹
PreOrderTraverse(T->rchild,Visit); // 最後先序遍歷右子樹
}
}

void InOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ // 初始條件: 二叉樹T存在,Visit是對結點操作的應用函數
// 操作結果: 中序遞歸遍歷T,對每個結點調用函數Visit一次且僅一次
if(T)
{
InOrderTraverse(T->lchild,Visit); // 先中序遍歷左子樹
Visit(T->data); // 再訪問根結點
InOrderTraverse(T->rchild,Visit); // 最後中序遍歷右子樹
}
}

typedef BiTree SElemType; // 設棧元素為二叉樹的指針類型
#include"c3-1.h"
#include"bo3-1.cpp"
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType))
{ // 採用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數。演算法6.3
// 中序遍歷二叉樹T的非遞歸演算法(利用棧)，對每個數據元素調用函數Visit
SqStack S;
InitStack(S);
while(T||!StackEmpty(S))
{
if(T)
{ // 根指針進棧,遍歷左子樹
Push(S,T);
T=T->lchild;
}
else
{ // 根指針退棧,訪問根結點,遍歷右子樹
Pop(S,T);
if(!Visit(T->data))
return ERROR;
T=T->rchild;
}
}
printf("\n");
return OK;
}

Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType))
{ // 採用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數。演算法6.2
// 中序遍歷二叉樹T的非遞歸演算法(利用棧)，對每個數據元素調用函數Visit
SqStack S;
BiTree p;
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);
if(!Visit(p->data))
return ERROR;
Push(S,p->rchild);
}
}
printf("\n");
return OK;
}

void PostOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ // 初始條件: 二叉樹T存在,Visit是對結點操作的應用函數
// 操作結果: 後序遞歸遍歷T,對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{
PostOrderTraverse(T->lchild,Visit); // 先後序遍歷左子樹
PostOrderTraverse(T->rchild,Visit); // 再後序遍歷右子樹
Visit(T->data); // 最後訪問根結點
}
}

void LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ // 初始條件：二叉樹T存在,Visit是對結點操作的應用函數
// 操作結果：層序遞歸遍歷T(利用隊列),對每個結點調用函數Visit一次且僅一次
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(q);
EnQueue(q,T);
while(!QueueEmpty(q))
{
DeQueue(q,a);
Visit(a->data);
if(a->lchild!=NULL)
EnQueue(q,a->lchild);
if(a->rchild!=NULL)
EnQueue(q,a->rchild);
}
printf("\n");
}
}

⑹ 二叉樹排序演算法實現（數據結構課程設計）

#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
}

⑺ 課程設計題二：二叉樹的基本操作 一、 設計目的 1．掌握二叉樹的概念和性質 2. 掌握任意二叉樹存儲結構。

自己寫啊。。這個東西很簡單的。上大學總要會點東西吧。。。

⑻ 數據結構課程設計 求二叉樹上結點的路徑

#include <stdio.h>
#include<malloc.h>
#define MAXSIZE 20
#define exit 0
typedef struct btnode
{
char cdata;
struct btnode *lchild,*rchild;
}BTNode;
BTNode *Create_BiTree()/*二叉樹的建立*/
{
/*用輔助數組建立二叉樹*/
int i,j;
char ch;
BTNode *s,*t,*p[MAXSIZE];
printf("\t=========數據結構=======RANBO========\n");
printf("\t=========二叉樹基本操作==============\n");
printf("輸入頂點編號及信息，輸入0和#結束:i,ch\n");
scanf("%d,%c",&i,&ch);
while (i!=0 &&ch!='#')/*建立二叉樹的存儲結構*/
{
s=(BTNode *)malloc(sizeof(BTNode));
s->cdata=ch;
s->lchild=s->rchild=NULL;
p[i]=s;
if (i==1) t=s;/*判斷輸入結點是根結點、左孩子還是右孩子*/
else
{
j=i/2;
if (i%2==0) p[j]->lchild=s;
else p[j]->rchild=s;
}
printf("輸入頂點編號及信息，輸入0和#結束:i,ch\n");
scanf("%d,%c",&i,&ch);
}
return t;
}/* Create_BiTree1*/
void Preorder(BTNode *bt)
{
/*前序遞歸遍歷*/
if (bt)
{
printf("%c",bt->cdata);
Preorder(bt->lchild);
Preorder(bt->rchild);
}
}/* Preorder*/
void Inorder(BTNode *bt)
{
/*中序遞歸遍歷*/
if (bt)
{
Inorder(bt->lchild);
printf("%c",bt->cdata);
Inorder(bt->rchild);
}
}/* Inorder*/
void Postorder(BTNode *bt)
{
/*後序遞歸遍歷*/
if (bt)
{
Postorder(bt->lchild);
Postorder(bt->rchild);
printf("%c",bt->cdata);
}
}/* Postorder*/
void LevelOrder(BTNode *bt) /*層次遍歷二叉樹bt*/
{
BTNode* queue[MAXSIZE];
int front,rear;
if (bt==NULL) return;
front=0; /*非循環隊列*/
rear=0;
queue[rear++]=bt;
while (front!=rear)
{
printf("%c",queue[front]->cdata); /*訪問隊首結點的數據域*/
if (queue[front]->lchild!=NULL) /*將隊首結點的左孩子指針入隊列*/
{
queue[rear]=queue[front]->lchild;
rear++;
}
if (queue[front]->rchild!=NULL) /*將隊首結點的右孩子指針入隊列*/
{
queue[rear]=queue[front]->rchild;
rear++;
}
front++;
} /* while */
}/* LevelOrder*/
int main()
{
int i,j=1;
BTNode *t;
t=Create_BiTree();
while (j)
{
printf("\n"); /*功能菜單*/
printf("請選擇操作:\n");
printf("1: 二叉樹的前序遍歷\n");
printf("2: 二叉樹的中序遍歷\n");
printf("3: 二叉樹的後序遍歷\n");
printf("4: 二叉樹的層次遍歷\n");
printf("0: 退出程序\n");
scanf("%d",&j);
switch (j)
{
case 0:
printf(" 程序退出!\n ");
exit(0);
case 1:
printf("前序遍歷結果:\n");
Preorder(t);
break;
case 2:
printf("中序遍歷結果:\n");
Inorder(t);
break;
case 3:
printf("後序遍歷結果:\n");
Postorder(t);
break;
case 4:
printf("按層遍歷結果:\n");
LevelOrder(t);
break;
default :
printf("\n輸入無效，請重新選擇操作!\n" );
break;
}
}
}

⑼ 排序二叉樹的遍歷課程設計（跪求參考）

我們剛做完的實驗。希望幫到您：
#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;
}

⑽ 《數據結構》的課程設計，題目是請設計一個演算法，把二叉樹的葉子結點按從左到右的順序連成。

下面是函數
//定義二叉樹鏈式結構
typedef struct BitNode
{
char data; //數據域
struct BitNode *lchild,*rchild;//左右指針域
}BitNode,*BiTree;

//葉子節點從左到右依次存入鏈表中
//bt-二叉樹,head-表頭,pre-前趨節點
void LeafLink(BiTree bt,BiTree &head,BiTree &pre)
{
if(bt!=NULL)
{
LeafLink(bt->lchild,head,pre);

if(bt->lchild==NULL&&bt->rchild==NULL)//葉子節點
{
BiTree s;

s=(BiTree)malloc(sizeof(BitNode));
if(s==NULL)
{
printf("建立單鏈表申請內存出錯\n");
exit(-1);
}
memcpy(s,bt,sizeof(BitNode));//內存拷貝,不破壞原二叉樹信息
if(pre==NULL)//第一個葉子節點
{
head=s;
pre=s;
}
else
{
pre->rchild=s;
pre=s;
}
}

LeafLink(bt->rchild,head,pre);

pre->rchild=NULL;//最後節點後續為空

}
}