?? 1.cpp
字號(hào):
//*****************************
#include<stdio.h> //
#include<string.h> //
#include<malloc.h> //
#include<stdlib.h> //
#define NULL 0 //
#define OK 1 //
#define ERROR 0 //
#define OVERFLOW 0 //
#define TElemType int //
#define QElemType BiTree //
//*****************************
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild; //左右孩子指針
}BiTNode,*BiTree;
InitBiTree(BiTree &T){
//創(chuàng)建空樹(shù)
T=NULL;
return OK;
}//InitBiTree
DestroyBiTree(BiTree &T){
//銷(xiāo)毀二叉樹(shù)
if(T)
delete(T); //銷(xiāo)毀根節(jié)點(diǎn)
DestroyBiTree(T->lchild); //銷(xiāo)毀左子樹(shù)
DestroyBiTree(T->rchild); //銷(xiāo)毀右子樹(shù)
return OK;
}//DestroyBiTree
CreatBiTree(BiTree &T,int definition){
//按先序次序輸入二叉樹(shù)中節(jié)點(diǎn)的值,空格字符表示空樹(shù)
//構(gòu)造二叉鏈表表示的二叉樹(shù)T
if(definition=1){
TElemType nodedata;
printf("Enter the data of the tree node:");
scanf("%d",&nodedata);
if(nodedata==99)T=NULL;
else{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data=nodedata; //生成根節(jié)點(diǎn)
CreatBiTree(T->lchild,1); //構(gòu)造左子樹(shù)
CreatBiTree(T->rchild,1); //構(gòu)造右子樹(shù)
}
}
return OK;
}//CreatBiTree
void ClearBiTree(BiTree &T){
//清空二叉樹(shù)
if(T){
ClearBiTree(T->lchild); //清空左子樹(shù)
ClearBiTree(T->rchild); //清空右子樹(shù)
free(T);
T=NULL;
}
}//ClearBiTree
BiTreeDepth(BiTree &T){
//求二叉樹(shù)深度
int LeftBiTreedepth,RightBiTreedepth; //設(shè)左右兩個(gè)深度/層次計(jì)數(shù)器
if(T==NULL)
return (0); //當(dāng)前結(jié)點(diǎn)指針為空則立即返回
else{
LeftBiTreedepth=BiTreeDepth(T->lchild); //遍歷當(dāng)前結(jié)點(diǎn)左子樹(shù)
RightBiTreedepth=BiTreeDepth(T->rchild);//遍歷當(dāng)前結(jié)點(diǎn)右子樹(shù)
if(LeftBiTreedepth<=RightBiTreedepth) //從葉子起計(jì)數(shù)
return (RightBiTreedepth+1);
else
return (LeftBiTreedepth+1);
}
}//BiTreeDepth
BiTree Root(BiTree &T){
//返回根結(jié)點(diǎn)
if(T!=NULL){
return (T);
}
else
return 0;
}//Root
int EQ(BiTree &T,int e){
//判斷結(jié)點(diǎn)是否在樹(shù)中
return (T->data)==e?OK:ERROR;
}
int Value(BiTree &T,TElemType e){
//e是樹(shù)中的結(jié)點(diǎn)，返回節(jié)點(diǎn)值
if(T!=NULL){
if(!EQ(T,e)){
Value(T->lchild,e);
if(!EQ(T->lchild,e))
Value(T->rchild,e);
}
return (T->data);
}else return (0);
}//Value
int Assign(BiTree &T,TElemType e,TElemType value){
//e是樹(shù)中的結(jié)點(diǎn)，將e賦值為value
if(T!=NULL){
if(!EQ(T,e)){
EQ(T->lchild,e);
EQ(T->rchild,e);
}else T->data=value;
return (T->data);
}else return (0);
}//Assign
int PrintfElement(TElemType e){
//輸出e的值
printf("%d",e);
printf("->");
return OK;
}
PreOrderTraverse(BiTree &T,int Visit(TElemType e)){
//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)應(yīng)數(shù)據(jù)元素操作的函數(shù)
//先序遍歷二叉樹(shù)T的遞規(guī)算法，對(duì)數(shù)據(jù)的每個(gè)元素都調(diào)用函數(shù)visit
if(T!=NULL){
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit))
return OK;
return ERROR;
}else return OK;
}//PreOrderTraverse
InOrderTraverse(BiTree &T,int Visit(TElemType e)){
//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)應(yīng)數(shù)據(jù)元素操作的函數(shù)
//中序遍歷二叉樹(shù)T的遞規(guī)算法，對(duì)數(shù)據(jù)的每個(gè)元素都調(diào)用函數(shù)visit
if(T!=NULL){
if(InOrderTraverse(T->lchild,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Visit))
return OK;
return ERROR;
}else return OK;
}//InOrderTraverse
PostOrderTraverse(BiTree &T,int Visit(TElemType e)){
//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)應(yīng)數(shù)據(jù)元素操作的函數(shù)
//后序遍歷二叉樹(shù)T的遞規(guī)算法，對(duì)數(shù)據(jù)的每個(gè)元素都調(diào)用函數(shù)visit
if(T!=NULL){
if(PostOrderTraverse(T->lchild,Visit))
if(PostOrderTraverse(T->rchild,Visit))
if(Visit(T->data))
return OK;
return ERROR;
}else return OK;
}//PostOrderTraverse
//------------------------------------------------------------------
//創(chuàng)建隊(duì)列
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front; //隊(duì)頭指針
QueuePtr rear; //對(duì)尾指針
}LinkQueue;
InitQueue(LinkQueue&Q){
//構(gòu)造一個(gè)空隊(duì)列Q
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); //存儲(chǔ)內(nèi)存分配失敗
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
DestroyQueue (LinkQueue&Q){
//銷(xiāo)毀隊(duì)列Q
while(Q.front){
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
EnQueue(LinkQueue&Q,QElemType e){
//插入元素e為Q的新的隊(duì)尾元素
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode)); //存儲(chǔ)內(nèi)存分配失敗
if(!p) exit(OVERFLOW);
p->data=e; p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
QueueEmpty(LinkQueue &Q){
//判斷隊(duì)列是否為空
return Q.front==Q.rear?OK:ERROR;
}
DeQueue(LinkQueue &Q,QElemType &e){
//若隊(duì)列不為空，則刪除Q的隊(duì)頭元素，用e返回其值，并返回OK
//否則返回ERROR
if(Q.front==Q.rear) return ERROR;
QueuePtr p;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return OK;
}
LevelOrderTraverse(BiTree &T, int Visit(TElemType e)){
//層序遍歷二叉樹(shù)
if(T!=NULL){
LinkQueue Q;
InitQueue(Q); //建一個(gè)空隊(duì)（初始化隊(duì)列）
QElemType p;
EnQueue(Q,T); //將一個(gè)結(jié)點(diǎn)插入隊(duì)尾的函數(shù)
while(!QueueEmpty(Q)) {
DeQueue(Q, p); //隊(duì)首結(jié)點(diǎn)出隊(duì)(送入p)
Visit(p->data);
if(p->lchild) EnQueue(Q,T->lchild); //p的左孩子入隊(duì)
if(p->rchild) EnQueue(Q,T->rchild); //p的右孩子入隊(duì)
}
}
return OK;
}//LevelOrderTraverse
IsOrNotInTree(BiTree &T,BiTree &c){
//判斷兩個(gè)樹(shù)是否相交
if(T!=NULL&&c!=NULL){
if(!EQ(T,c->data)){
EQ(T->lchild,c->data);
EQ(T->rchild,c->data);
}else return 1;
}else return 0;
}
BiTree EQQ(BiTree &T,int e){
//返回指向結(jié)點(diǎn)的指針
if(T!=NULL){
if(!EQ(T,e)){
EQQ(T->lchild,e);
if(!EQ(T->lchild,e))
EQQ(T->rchild,e);
}
return (T);
}
}
InsertChild(BiTree &T,BiTree &p,int LR,BiTree &c){
//插入c為T(mén)的子樹(shù)..
BiTree pchild;
if(T!=NULL&&c!=NULL&&c->rchild==NULL&&!IsOrNotInTree(T,c)){
if(LR){
pchild=p->rchild;
p->rchild=c;
c->rchild=pchild;
}
else{
pchild=p->lchild;
p->lchild=c;
c->rchild=pchild;
}
}
return 0;
}//InsertChild
DeleteChild(BiTree &T,BiTree &p, int LR){
//刪除T的子樹(shù)..
if(LR){
ClearBiTree(p->rchild);
p->rchild=NULL;
}
else if(LR==0){
ClearBiTree(p->lchild);
p->lchild=NULL;}
else
return ERROR;
}//DeleteChild
main()
{
printf("\n");
printf("********************二叉樹(shù)*******************");
printf("\n");
printf("Build the tree:\n");
printf("The num(99) is NULL:\n");
BiTree T=NULL;
CreatBiTree(T,1);
printf("T tree has been built:\n");
printf("***************************\n");
printf("The traverse of the tree:\n");
printf("***************************\n");
printf("PreOrderTraverse The BiTree:\n");
PreOrderTraverse(T,PrintfElement);
printf("\n");
printf("InOrderTraverse The BiTree:\n");
InOrderTraverse(T,PrintfElement);
printf("\n");
printf("PostOrderTraverse The BiTree:\n");
PostOrderTraverse(T,PrintfElement);
printf("\n");
printf("LevelOrderTraverse The BiTree:\n");
LevelOrderTraverse(T,PrintfElement);
printf("\n");
printf("*************************\n");
printf("The depth of the tree is:\n");
printf("**************************\n");
int BiTreedepth;
BiTreedepth=BiTreeDepth(T);
printf("%d\n",BiTreedepth);
printf("\n");
printf("***************************\n");
printf("the data of the tree root:\n");
printf("***************************\n");
BiTree root=Root(T);
printf("%d\n",root->data);
printf("\n");
printf("enter the data of the node:\n");
int e,f;
scanf("%d",&e);
f=Value(T,e);
printf("***************************\n");
printf("the data of the node is:\n");
printf("***************************\n");
printf("%d\n",f);
int m,n,g;
printf("enter the data of the node:\n");
scanf("%d",&m);
printf("enter the data you want to change:\n");
scanf("%d",&n);
g=Assign(T,m,n);
printf("***************************\n");
printf("change the data of the node:\n");
printf("***************************\n");
printf("%d",g);
printf("\n");
printf("build another tree:\n");
BiTree c;
CreatBiTree(c,1);
printf("T tree has been built:\n");
/* int t;
printf("Enter the t:\n");
scanf("%d",&t);
BiTree p;
p=EQQ(T,t);*/
InsertChild(T,T->lchild,1,c);
printf("***************************\n");
printf("insert the child:\n");
printf("the T tree changed:\n");
printf("***************************\n");
PreOrderTraverse(T,PrintfElement);
printf("\n");
DeleteChild(T,T->lchild,1);
printf("***************************\n");
printf("delete the child:\n");
printf("the T tree changed:\n");
printf("***************************\n");
PreOrderTraverse(T,PrintfElement);
return 0;
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -