//二叉樹(shù)結(jié)點(diǎn)類型為字符型的情況
目前創(chuàng)新互聯(lián)公司已為上1000+的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬空間、網(wǎng)站托管運(yùn)營(yíng)、企業(yè)網(wǎng)站設(shè)計(jì)、康馬網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。
#include stdio.h
#include stdlib.h
#include string.h
#define null 0
#define MaxSize 1024
typedef struct tree
{ /*聲明樹(shù)的結(jié)構(gòu)*/
struct tree *left; /*存放左子樹(shù)的指針*/
struct tree *right; /*存放右子樹(shù)的指針*/
char data; /*存放節(jié)點(diǎn)的內(nèi)容*/
} treenode, * b_tree; /*聲明二叉樹(shù)的鏈表*/
b_tree Q[MaxSize];
/*建立二叉樹(shù)，按完全二叉樹(shù)的層次遍歷序列輸入*/
b_tree createbtree()
{
char ch;
int front,rear;
b_tree root,s;
root=NULL;
front=1;rear=0;
ch=getchar();
getchar();
while(ch!='?')
{
s=NULL;
if(ch!='.')
{
s=(b_tree)malloc(sizeof(treenode));
s-data=ch;
s-left=NULL;
s-right=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else
{
if(sQ[front])
if(rear%2==0)
Q[front]-left=s;
else
Q[front]-right=s;
if(rear%2==1)
front++;
}
ch=getchar();
getchar();
}
return root;
}
/*先序遍歷打印二叉排序樹(shù)*/
void preorder_btree(b_tree root)
{
b_tree p=root;
if(p!=null)
{
printf("%3c",p-data);
preorder_btree(p-left);
preorder_btree(p-right);
}
}
/* 中序遍歷打印二叉排序樹(shù)*/
void inorder_btree(b_tree root)
{
b_tree p=root;
if(p!=null){
inorder_btree(p-left );
printf("%3c",p-data );
inorder_btree(p-right );
}
}
/*后序遍歷打印二叉排序樹(shù)*/
void postorder_btree(b_tree root)
{
b_tree p=root;
if(p!=null)
{
postorder_btree(p-left );
postorder_btree(p-right );
printf("%3c",p-data );
}
}
/*求樹(shù)的高度*/
int treedepth(b_tree bt)
{
int hl,hr,max;
if(bt!=null)
{
hl=treedepth(bt-left);
hr=treedepth(bt-right);
max=(hlhr)?hl:hr;
return (max+1);
}
else
return 0;
}
int count=0;
/*求葉子結(jié)點(diǎn)總數(shù)*/
int leafcount(b_tree bt)
{
if(bt!=null)
{
leafcount(bt-left);
leafcount(bt-right);
if(bt-left==nullbt-right==null)
count++;
}
return count;
}
void paintleaf(b_tree bt)
{
if(bt!=null)
{
if(bt-left==nullbt-right==null)
printf("%3c",bt-data);
paintleaf(bt-left);
paintleaf(bt-right);
}
}
typedef b_tree ElemType ;
int main()
{
char nodelist[MaxSize];
int len,flag;
char cmd;
b_tree root;
do
{
printf(" 輸入c......選擇創(chuàng)建一棵二叉排序樹(shù)\n");
printf(" 輸入a......將結(jié)束本程序\n\n");
flag=0;
do
{
if(flag!=0)
printf("選擇操作錯(cuò)誤！請(qǐng)重新選擇！\n");
fflush(stdin);
scanf("%c",cmd);
flag++;
}while(cmd!='c'cmd!='a');
if(cmd=='c')
{
printf("請(qǐng)輸入那你所要?jiǎng)?chuàng)建的二叉樹(shù)的結(jié)點(diǎn)的值,以'？'結(jié)束）：\n");
getchar();
root=createbtree();
do
{
flag=0;
printf("\n\n 請(qǐng)選擇你要對(duì)這棵二叉樹(shù)所做的操作:\n\n");
printf(" x......先序遍歷\n");
printf(" z......中序遍歷\n");
printf(" h......后序遍歷\n");
printf(" b......層次遍歷\n");
printf(" d......求二叉樹(shù)的深度\n");
printf(" y......求葉子總數(shù)并輸出各葉子結(jié)點(diǎn)\n");
printf(" q......結(jié)束操作\n\n");
do
{
if(flag!=0)
printf("選擇操作錯(cuò)誤！請(qǐng)重新選擇！\n");
fflush(stdin);
scanf("%c",cmd);
flag++;
}while(cmd!='x'cmd!='z'cmd!='h'cmd!='b'cmd!='d'cmd!='y'cmd!='j'cmd!='q');
switch(cmd)
{
case 'x':
printf("\n先序遍歷開(kāi)始:\n");
preorder_btree(root);
printf("\n先序遍歷結(jié)束\n\n");
break;
case 'z':
printf("\n中序遍歷開(kāi)始:\n");
inorder_btree(root);
printf("\n中序遍歷結(jié)束\n\n");
break;
case 'h':
printf("\n后序遍歷開(kāi)始:\n");
postorder_btree(root);
printf("\n后序遍歷結(jié)束\n\n");
break;
case 'd':
printf("\n這棵二叉樹(shù)的高度：\n%d\n\n",treedepth(root));
break;
case 'y':
printf("\n這棵二叉樹(shù)的葉子結(jié)點(diǎn)為：\n");
paintleaf(root);
printf("\n");
count=0;
count=leafcount(root);
printf("\n這棵二叉樹(shù)的葉子總數(shù)為:\n%d\n\n",count);
count=0;
break;
}
}while(cmd!='q'cmd!='Q');
}
}while(cmd!='a'cmd!='A');
printf("****謝謝使用！歡迎指正！****\n\n");
return 0;
}
//?創(chuàng)建二叉樹(shù),請(qǐng)輸入節(jié)點(diǎn)的總數(shù)量:?7
//?請(qǐng)連續(xù)輸入7個(gè)節(jié)點(diǎn)的數(shù)據(jù):?4?2?6?1?3?5?7
//?前序遍歷序列:?4?2?1?3?6?5?7
//?中序遍歷序列:?1?2?3?4?5?6?7
//?后序遍歷序列:?1?3?2?5?7?6?4
//?二叉樹(shù)的節(jié)點(diǎn)一共有7個(gè),度為1的節(jié)點(diǎn)有0個(gè),度為2的節(jié)點(diǎn)有3個(gè),
//?葉子節(jié)點(diǎn)有4個(gè),數(shù)據(jù)值的最大值是7,最小值是1
//
//?對(duì)應(yīng)的二叉樹(shù):
//
//???????4
//????/??????\
//???2????????6
//??/??\?????/??\
//?1????3???5????7
#include?"stdio.h"
#include?"stdlib.h"
struct?Tree
{
int?data;
struct?Tree?*left;
struct?Tree?*right;
};
typedef?struct?Tree?TreeNode;
typedef?TreeNode?*Bitree;
typedef?struct?stack_node?//棧的結(jié)構(gòu)體
{
Bitree?bt;
struct?stack_node?*next;
}?stack_list,?*stack_link;
Bitree?insertNode(Bitree?root,int?data)?//插入結(jié)點(diǎn)
{
Bitree?newnode;
Bitree?current;
Bitree?back;
newnode=(Bitree)malloc(sizeof(TreeNode));
if(newnode==NULL)
{
printf("\n動(dòng)態(tài)分配內(nèi)存出錯(cuò).\n");
exit(1);
}
newnode-data=data;
newnode-left=NULL;
newnode-right=NULL;
if(root==NULL)
{
return?newnode;
}
else
{
current=root;
while(current!=NULL)
{
back=current;
if(current-data??data)
current=current-left;
else
current=current-right;
}
if(back-data??data)
back-left=newnode;
else
back-right=newnode;
}
return?root;
}
Bitree?createTree()?//創(chuàng)建二叉樹(shù)(非遞歸)
{
Bitree?root=NULL;
int?len;
int?data;
int?i;
printf("創(chuàng)建二叉樹(shù),請(qǐng)輸入節(jié)點(diǎn)的總數(shù)量:?");
scanf("%d",len);
printf("請(qǐng)連續(xù)輸入%d個(gè)節(jié)點(diǎn)的數(shù)據(jù):?",len);
for(i=0;ilen;i++)
{
scanf("%d",data);
root=insertNode(root,data);
}
return?root;
}
void?preOrder(Bitree?ptr)?//先序遍歷(遞歸法)
{
if(ptr!=NULL)
{
printf("%d?",ptr-data);
preOrder(ptr-left);
preOrder(ptr-right);
}
}
void?inOrder(Bitree?ptr)?//中序遍歷(遞歸法)
{
if(ptr!=NULL)
{
inOrder(ptr-left);
printf("%d?",ptr-data);
inOrder(ptr-right);
}
}
void?postOrder(Bitree?ptr)?//后序遍歷(遞歸法)
{
if(ptr!=NULL)
{
postOrder(ptr-left);
postOrder(ptr-right);
printf("%d?",ptr-data);
}
}
//檢查[棧]是否是空
int?isEmpty(stack_link?stack)
{
if(stack?==?NULL)
{
return?1;
}
else
{
return?0;
}
}
//入棧
stack_link?push(stack_link?stack,Bitree?bt)
{
stack_link?new_node;
new_node=(stack_link)malloc(sizeof(stack_list));
if(!new_node)
{
return?NULL;
}
new_node-bt=bt;
new_node-next=stack;
stack=new_node;
return?stack;
}
//出棧
stack_link?pop(stack_link?stack,Bitree?*bt)
{
stack_link?top;
if(isEmpty(stack))
{
*bt?=?NULL;
return?NULL;
}
top=stack;
*bt=top-bt;
stack=top-next;
free(top);
return?stack;
}
//統(tǒng)計(jì)節(jié)點(diǎn)(非遞歸)
void?reportByStack(Bitree?bt,int?*pTotal,int?*pCount0,int?*pCount1,
int?*pCount2,int?*pMaxValue,int?*pMinValue)
{
Bitree?p=NULL;
stack_link?oneStack=NULL;
int?total=0;
int?count0=0,count1=0,count2=0;
int?maxValue=0,minValue=0;
if(bt?==?NULL)
{
return;
}
p=bt;??????????//當(dāng)前二叉樹(shù)的節(jié)點(diǎn)
minValue=p-data;
maxValue=minValue;
while(p?!=?NULL)
{
if(minValue??p-data)
{
minValue?=?p-data;
}
if(maxValue??p-data)
{
maxValue?=?p-data;
}
total++;?//total=count0+count1+count2
if(p-right?==?NULL??p-left?==?NULL)?//葉子
{
count0++;
}
else?if(p-right?!=?NULL??p-left?!=?NULL)?//度2
{
count2++;
}
else?//度1
{
count1++;
}
if(p-right?!=?NULL)??//如果有右子樹(shù),馬上入棧
{
oneStack=push(oneStack,p-right);
}
if(p-left?!=?NULL)?//如果有左子樹(shù),設(shè)為當(dāng)前節(jié)點(diǎn)
{
p=p-left;
}
else
{
oneStack=pop(oneStack,p);
if(p?==?NULL)
{
break;
}
}
}
*pTotal=total;
*pCount0=count0;
*pCount1=count1;
*pCount2=count2;
*pMaxValue=maxValue;
*pMinValue=minValue;
}
int?main()
{
Bitree?root=NULL;
int?total=0;
int?count0=0,count1=0,count2=0;
int?maxValue=0,minValue=0;
root=createTree();?//創(chuàng)建二叉樹(shù)
printf("\n前序遍歷序列:?");
preOrder(root);
printf("\n中序遍歷序列:?");
inOrder(root);
printf("\n后序遍歷序列:?");
postOrder(root);
//統(tǒng)計(jì)節(jié)點(diǎn)(非遞歸)
reportByStack(root,total,count0,count1,count2,maxValue,minValue);
printf("\n二叉樹(shù)的節(jié)點(diǎn)一共有%d個(gè),度為1的節(jié)點(diǎn)有%d個(gè),度為2的節(jié)點(diǎn)有%d個(gè),\n",
total,count1,count2);
printf("葉子節(jié)點(diǎn)有%d個(gè),數(shù)據(jù)值的最大值是%d,最小值是%d",
count0,maxValue,minValue);
printf("\n");
return?0;
}
樓主你好
具體代碼如下：
#includestdio.h
#includestdlib.h
#define MAX 40
typedef struct node//二叉樹(shù)結(jié)點(diǎn)定義
{
char data;
struct node *lChild;//左孩子
struct node *rChild;//右孩子
}BTNode;
//*************************************二叉樹(shù)操作***************************************
void Initial_BT(BTNode * b)
{
b=NULL;
}
void Creat_BT(BTNode * b)//創(chuàng)建二叉樹(shù)
{
BTNode *St[MAX];//用棧輔助實(shí)現(xiàn)二叉樹(shù)的建立
BTNode *p=NULL;
b=NULL;
int top=-1;//棧指針
int k;//k為左右孩子標(biāo)示(1為左孩子、2為右孩子)
char ch;
printf("Enter the binary tree:\n");
ch=getchar();
while(ch!='\n')
{
switch(ch)
{
case '('://左孩子
top++;
St[top]=p;
k=1;
break;
case ')':
top--;
break;
case ','://右孩子
k=2;
break;
default:
p=(BTNode *)malloc(sizeof(BTNode));
p-data=ch;
p-lChild=p-rChild=NULL;
if(!b)//如果為根節(jié)點(diǎn)
b=p;
else
{
switch(k)
{
case 1:
St[top]-lChild=p;
break;
case 2:
St[top]-rChild=p;
break;
}
}
}
ch=getchar();//繼續(xù)讀入數(shù)據(jù)
}
}
void InOrder(BTNode *b)//中序遍歷
{
if(b)
{
InOrder(b-lChild);
printf("%c",b-data);
InOrder(b-rChild);
}
}
void PostOrder(BTNode *b)//后序遍歷
{
if(b)
{
PostOrder(b-lChild);
PostOrder(b-rChild);
printf("%c",b-data);
}
}
int Leaf_Sum(BTNode *b)
{
if(!b)
return 0;
else if(b-lChild == NULL b-rChild == NULL)
return 1;
else
return Leaf_Sum(b-lChild)+Leaf_Sum(b-rChild);
}
void Start()
{
BTNode *b;//二叉樹(shù)
char choice;
b=(BTNode *)malloc(sizeof(BTNode));
Initial_BT(b);
GOTO:system("cls");
printf("\t\t1.創(chuàng)建二叉樹(shù).\n"
"\t\t2.中序遍歷.\n"
"\t\t3.后序遍歷.\n"
"\t\t4.葉子結(jié)點(diǎn)個(gè)數(shù).\n"
"\t\t5.退出.\n");
printf("輸入你的選擇:");
GOTO1:choice=getchar();
switch(choice)
{
case '1':
getchar();
Creat_BT(b);
system("pause");
goto GOTO;
case '2':
InOrder(b);
printf("\n");
system("pause");
getchar();
goto GOTO;
case '3':
PostOrder(b);
printf("\n");
system("pause");
getchar();
goto GOTO;
case '4':
printf("共有%d個(gè)葉子結(jié)點(diǎn)\n",Leaf_Sum(b));
system("pause");
getchar();
goto GOTO;
case '5':
system("pause");
break;
default:
printf("輸入錯(cuò)誤!\n"
"重新輸入:");
goto GOTO1;
}
}
int main()
{
Start();
return 0;
}
希望能幫助你哈
//這個(gè)題目挺有意思的，很喜歡，你看看我這個(gè)咋樣??？
#includestdio.h
#includemalloc.h
typedef
char
elemtype
;
typedef
struct
node
{
elemtype
data
;
struct
node
*lchild
;
struct
node
*rchild
;
}btree,*pbtree
;
//先序創(chuàng)建樹(shù)
void
createbtree(pbtree
*t)
//此處參數(shù)應(yīng)該用指針的指針，應(yīng)給它要改變指向二叉樹(shù)根的那個(gè)指針
{
char
ch
;
ch=getchar();
getchar();
//得到回車按那個(gè)字符
if(ch
=='
')
//輸入空字符時(shí)要打空格
{
(*t)
=
null
;
return
;
}
else
{
if(
!(
(*t)
=
(pbtree)
malloc(sizeof(btree))
)
)
return
;
(*t)-data
=
ch
;
createbtree(
(*t)-lchild
);
createbtree(
(*t)-rchild
);
}
}
void
btreeprint(btree
*tr,int
n)
//逆時(shí)針旋轉(zhuǎn)90°打印二叉樹(shù)，n為縮進(jìn)層數(shù)，初始值為0
{
int
i;
if(tr
==
null)
return;
btreeprint(tr-rchild,n+1);
for(i
=
0;in;i++)
printf("
");
if(n
=
0)
{
printf("--");
printf("%c\n",tr-data);
}
btreeprint(tr-lchild,n+1);
}
void
main()
{
pbtree
btree
;
createbtree(btree);
btreeprint(btree,0);
}
輸入舉例：建立以a為根b、c分別為左右子樹(shù)的二叉樹(shù)！輸入格式為：
a
回車！
b
回車！
空格
回車！
空格
回車！
c
回車！
空格
回車！
空格
回車！
在二叉樹(shù)中有一種平衡二叉樹(shù)，通過(guò)平衡算法可以讓二叉樹(shù)兩邊的節(jié)點(diǎn)平均分布，這樣就能讓所有的索引查找都在一個(gè)近似的時(shí)間內(nèi)完成。而MySQL這類數(shù)據(jù)庫(kù)采用了二叉樹(shù)的升級(jí)版B+Tree的形式，每個(gè)節(jié)點(diǎn)有三個(gè)支葉，不過(guò)其算法原理仍然是平衡樹(shù)的原理。
#includestdio.h
#includestdio.h
#includemalloc.h
#include"c6_2.h"
#includestdlib.h#define TRUE 1
#define NULL 0
#define FALSE 0
#define ERROR 0
#define WRONG 0
#define OK 1
#define OVERFLOW 0typedef int TElemType;
typedef int Status;//二叉樹(shù)結(jié)構(gòu)體
typedef struct BiTNode
{ TElemType data;//結(jié)點(diǎn)的值
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//隊(duì)列結(jié)構(gòu)體
typedef BiTree QElemType;
typedef struct QNode
{ QElemType data;
QNode *next;
}*QueuePtr;struct LinkQueue
{ QueuePtr front,rear;//隊(duì)頭，隊(duì)尾指針
};#define ClearBiTree DestoryBiTree//清空二叉樹(shù)的操作和銷毀二叉樹(shù)的操作一樣
void InitBiTree(BiTree T)
{ T=NULL;
}
void DestroyBiTree(BiTree T)
{ //銷毀二叉樹(shù)
if(T)
{ DestroyBiTree(T-lchild);//銷毀左子樹(shù)
DestroyBiTree(T-rchild);//銷毀右子樹(shù)
free(T);
T=NULL;
}
}
void PreOrderTraverse(BiTree T,void(*visit)(TElemType))
{//先序遍歷二叉樹(shù)
if(T)
{ visit(T-data);
PreOrderTraverse(T-lchild,visit);
PreOrderTraverse(T-rchild,visit);
}
}
void InOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //中序遍歷二叉樹(shù)
if(T)
{ InOrderTraverse(T-lchild,visit);
visit(T-data);
InOrderTraverse(T-rchild,visit);
}
}
void PostOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //后序遍歷二叉樹(shù)
if(T)
{ PostOrderTraverse(T-lchild,visit);
PostOrderTraverse(T-rchild,visit);
visit(T-data);
}
}
Status BiTreeEmpty(BiTree T)
{ //判斷二叉樹(shù)是否為空
if(T)
return FALSE;
else
return TRUE;
}
int BiTreeDepth(BiTree T)//返回T的深度
{ int i,j;
if(!T)
return 0;
i=BiTreeDepth(T-lchild);//i為左孩子的深度
j=BiTreeDepth(T-rchild);//j為右孩子的深度
return ij?i+1:j+1;
}
TElemType Root(BiTree T)
{ //返回二叉樹(shù)的根結(jié)點(diǎn)
if(BiTreeEmpty(T))
return NULL;
else
return T-data;
}
TElemType Value(BiTree p)
{//返回P所指結(jié)點(diǎn)的值
return p-data;
}
void Assign(BiTree p,TElemType value)
{ //給P的結(jié)點(diǎn)賦新值
p-data=value;
}BiTree Point(BiTree T,TElemType s)//返回二叉樹(shù)T中指向元素值為S的結(jié)點(diǎn)指針
{ LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);//初始化隊(duì)列
EnQueue(q,T);//根指針入隊(duì)
while(!QueueEmpty(q))//隊(duì)不空
{ DeQueue(q,a);//出隊(duì)，隊(duì)列元素賦給e
if(a-data==s)//a所指結(jié)點(diǎn)為的值為s
return a;
if(a-lchild)//有左孩子
EnQueue(q,a-lchild);//入隊(duì)左孩子
if(a-rchild)//有右孩子
EnQueue(q,a-rchild);//入隊(duì)右孩子
}
}
return NULL;
}
TElemType LeftChild(BiTree T,TElemType e)
{//返回e的左孩子
BiTree a;
if(T)
{ a=Point(T,e);//a是指向結(jié)點(diǎn)e的指針
if(aa-lchild)
return a-lchild-data;
}
return NULL;
}
TElemType RightChild(BiTree T,TElemType e)
{ BiTree a;
if(T)
{ a=Point(T,e);//a是指向結(jié)點(diǎn)e的指針
if(aa-rchild)//T中存在結(jié)點(diǎn)e并且e存在右孩子
return a-rchild-data;
}
return NULL;
}
Status DeleteChild(BiTree p,int LR)
{ if(p)
{ if(LR==0)
DestroyBiTree(p-lchild);
else
DestroyBiTree(p-rchild);
return OK;
}
return ERROR;
}void visit(TElemType e)
{ printf("%d",e);
}
void LevelOrderTraverse(BiTree T,void(*visit)(TElemType))
{//層序遍歷
LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);//初始化隊(duì)列
EnQueue(q,T);//根指針入隊(duì)
while(!QueueEmpty(q))
{ DeQueue(q,a);//出隊(duì)元素，賦給a
visit(a-data);//訪問(wèn)a所指結(jié)點(diǎn)
if(a-lchild!=NULL)
EnQueue(q,a-lchild);
if(a-rchild!=NULL)
EnQueue(q,a-rchild);
}
}
}
void CreateBiTree(BiTree T)
{ TElemType ch;scanf("%d",ch);//輸入結(jié)點(diǎn)的值
if(ch==0)//結(jié)點(diǎn)為空
T=NULL;
else
{T=(BiTree)malloc(sizeof(BiTNode));br//生成根結(jié)點(diǎn)brif(!T)brexit(OVERFLOW);brT-data=ch;//將值賦給T所指結(jié)點(diǎn)/ppCreateBiTree(T-lchild);//遞歸構(gòu)造左子樹(shù)brCreateBiTree(T-rchild);br} } TElemType Parent(BiTree T,TElemType e)
{//返回雙親
LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);
EnQueue(q,T);//樹(shù)根入隊(duì)列
while(!QueueEmpty(q))//隊(duì)不空
{DeQueue(q,a);//出隊(duì)，隊(duì)列元素賦給abr if(a-lchilda-lchild-data==e||a-rchilda-rchild-data==e)//找到ebr return a-data;br elsebr { if(a-lchild)br EnQueue(q,a-lchild);//入隊(duì)列左孩子br if(a-rchild)br EnQueue(q,a-rchild);//入隊(duì)列右孩子br }
}
}
return NULL;
}
TElemType LeftSibling(BiTree T,TElemType e)
{ //返回左兄弟
TElemType a;
BiTree p;
if(T)
{ a=Parent(T,e);//a為e的雙親
if(a!=NULL)
{ p=Point(T,a);//p指向結(jié)點(diǎn)a的指針
if(p-lchildp-rchildp-rchild-data==e)//p存在左右孩子而且右孩子是e
return p-lchild-data;
}
}
return NULL;
}
TElemType RightSibling(BiTree T,TElemType e)
{ //返回右孩子
TElemType a;
BiTree p;
if(T)
{ a=Parent(T,e);//a為e的雙親
if(a!=NULL)
{ p=Point(T,a);//p為指向結(jié)點(diǎn)的a的指針
if(p-lchildp-rchildp-lchild-data==e)
return p-lchild-data;
}
}
return NULL;
}
Status InsertChild(BiTree p,int LR,BiTree c)
{ //根據(jù)LR為0或1，插入C為T(mén)中P所指結(jié)點(diǎn)的左或右子樹(shù)，P所結(jié)點(diǎn)的原有左或右子樹(shù)則成為C的右子樹(shù)
if(p)
{ if(LR==0)//把二叉樹(shù)C插入P所指結(jié)點(diǎn)的子樹(shù)
{ c-rchild=p-lchild;//p所結(jié)點(diǎn)的原有左子樹(shù)成為C的右子樹(shù)
p-lchild=c;//二叉樹(shù)成為P的左子樹(shù)
}
else{ c-rchild=p-rchild;//p指結(jié)點(diǎn)的原有右子樹(shù)成為C的右子樹(shù)
p-rchild=c;
}
return OK;
}
return ERROR;
}
//隊(duì)列操作
void InitQueue(LinkQueue Q)
{//初始化一個(gè)隊(duì)列
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)//生成頭結(jié)點(diǎn)失敗
exit(OVERFLOW);
Q.front-next=NULL;
}
Status QueueEmpty(LinkQueue Q)
{ //判斷隊(duì)列是否為空
if(Q.front-next==NULL)
return TRUE;
else return FALSE;
}void EnQueue(LinkQueue Q,QElemType e)
{ //插入元素e為隊(duì)列Q的新的隊(duì)尾元素
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
//動(dòng)態(tài)生成新結(jié)點(diǎn)
if(!p)
exit(OVERFLOW);
p-data=e;//將e的值賦給新結(jié)點(diǎn)
p-next=NULL;//新結(jié)點(diǎn)的指針為空
Q.rear-next=p;//原隊(duì)尾結(jié)點(diǎn)的指針域?yàn)橹赶蛐陆Y(jié)點(diǎn)
Q.rear=p;//尾指針指向新結(jié)點(diǎn)
}
Status DeQueue(LinkQueue Q,QElemType e)
{ //若隊(duì)列不為空，刪除Q的隊(duì)頭元素，用e返回其值
QueuePtr p;
if(Q.front==Q.rear)//隊(duì)列為空
return ERROR;
p=Q.front-next;//p指向隊(duì)頭結(jié)點(diǎn)
e=p-data;//隊(duì)頭元素賦給e
Q.front-next=p-next;//頭結(jié)點(diǎn)指向下一個(gè)結(jié)點(diǎn)
if(Q.rear==p)//如果刪除的隊(duì)尾結(jié)點(diǎn)
Q.rear=Q.front;//修改隊(duì)尾指針指向頭結(jié)點(diǎn)
free(p);
return OK;
}
//主函數(shù)文件
#includestdio.h
#include"c6_2.h"main()
{ int i,j;
BiTree T,p,c;
TElemType e0,e1,e2,e3,e4;
InitBiTree(T);//初始化二叉樹(shù)
printf("構(gòu)造二叉樹(shù)后，樹(shù)空否?%d(1,是,0否).樹(shù)的深度=%d.\n",BiTreeEmpty(T),BiTreeDepth(T));CreateBiTree(T);//建立二叉樹(shù)T
printf("構(gòu)造二叉樹(shù)后，樹(shù)空否?%d(1,是,0否).樹(shù)的深度=%d.\n",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);//e1為二叉樹(shù)T的根結(jié)點(diǎn)的值
if(e1!=NULL)
printf("二叉樹(shù)的根為%d",e1);
else
printf("樹(shù)空，無(wú)根");e2=LeftChild(T,e1);
printf("左孩子:%d",e2);
e3=RightChild(T,e1);
printf("右孩子:%d",e3);
printf("\n");printf("先序遞歸遍歷:\n");
PreOrderTraverse(T,visit);
printf("\n");printf("后序遞歸遍歷:\n");
PostOrderTraverse(T,visit);
printf("\n");printf("中序遞歸遍歷:\n");
InOrderTraverse(T,visit);
printf("\n");printf("輸入一個(gè)結(jié)點(diǎn)的值:");
scanf("%d",e1);
p=Point(T,e1);//p指向?yàn)閑的指針
printf("結(jié)點(diǎn)的值為%d\n",Value(p));
e0=Parent(T,e1);//返回e1的雙親
printf("結(jié)點(diǎn)%d的雙親為%d",e1,e0);
printf("\n");e0=LeftChild(T,e1);//返回e1的左孩子
if(e0==NULL)
printf("沒(méi)有孩子");
else
printf("左孩子為%d",e0);
printf("\n");e0=RightChild(T,e1);//返回e1的右孩子
if(e0==NULL)
printf("沒(méi)有右孩子");
else
printf("右孩子為%d",e0);
printf("\n");
e0=RightSibling(T,e1);//返回e1的右兄弟
if(e0!=NULL)
printf("右兄弟為%d",e0);
else
printf("沒(méi)有右兄弟");
printf("\n");e0=LeftSibling(T,e1);//返回e1的左兄弟
if(e0!=NULL)
printf("左兄弟為%d",e0);
else
printf("沒(méi)有左兄弟");
printf("\n");
printf("要改變結(jié)點(diǎn)%d的值，請(qǐng)輸入新值:",e1);
scanf("%d",e2);
Assign(p,e2);//將e2的值賦給p所指結(jié)點(diǎn)，代替e1
printf("層序遍歷二叉樹(shù):\n");
LevelOrderTraverse(T,visit);
printf("\n");
printf("創(chuàng)建一棵根結(jié)點(diǎn)右子樹(shù)為空的新樹(shù):");
CreateBiTree(c);//創(chuàng)建二叉樹(shù)
printf("先序遞歸遍歷二叉樹(shù)c:\n");
PreOrderTraverse(c,visit);
printf("將樹(shù)C插入樹(shù)T中，請(qǐng)輸入樹(shù)T中樹(shù)C的雙親結(jié)點(diǎn)C為左（0）或右（1）子樹(shù):");
scanf("%d,%d",e1,i);
p=Point(T,e1);//p指向二叉樹(shù)T中將T中作為二叉樹(shù)C的雙親結(jié)點(diǎn)的e1
InsertChild(p,i,c);//將樹(shù)C插入到二叉樹(shù)T中作為結(jié)點(diǎn)的左或右子樹(shù)
printf("構(gòu)造二叉樹(shù)后，樹(shù)空否?%d(1,是,0否).樹(shù)的深度=%d.\n",BiTreeEmpty(T),BiTreeDepth(T));
printf("先序遞歸遍歷二叉樹(shù):\n");
PreOrderTraverse(T,visit);
}
重慶分公司
重慶分公司
