C

二叉树的定义：

二叉树是一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

相关术语：

节点的度：一个节点含有的子树的个数称为该节点的度； 叶节点或终端节点：度为0的节点称为叶节点； 非终端节点或分支节点：度不为0的节点； 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 兄弟节点：具有相同父节点的节点互称为兄弟节点； 树的度：一棵树中，最大的节点的度称为树的度； 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推； 树的高度或深度：树中节点的最大层次； 堂兄弟节点：双亲在同一层的节点互为堂兄弟； 节点的祖先：从根到该节点所经分支上的所有节点； 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。 森林：由m（m>=0）棵互不相交的树的集合称为森林；

(相关术语来自百度百科)

二叉树的顺序存储结构

struct position{ int level; //结点的层 int order; //本层序号 }; 二叉树基本操作函数定义

/*构造空的二叉树T。*/ void InitBiTree(SqBiTree T) /*按层序次序输入二叉树中结点的值，构造顺序存储的二叉树T。*/ void CreateBiTree(SqBiTree T) /*初始条件：二叉树T存在。*/ /*操作结果：若二叉树T为空二叉树，则返回TRUE；否则返回FALSE。*/ Status BiTreeEmpty(SqBiTree T) /*初始条件：二叉树T存在。*/ /*操作结果：返回树T的深度。*/ int BiTreeDepth(SqBiTree T) /*初始条件：二叉树存在。*/ /*操作结果：当T不为空，用e返回T的根，返回OK；否则返回ERROR，e无定义。*/ Status Root(SqBiTree T,TElemType &e) /*初始条件：二叉树存在，e是T中某个结点的位置。*/ /*操作结果：返回处于位置e层，本层序号的结点的值。*/ TElemType Value(SqBiTree T,position e) /*初始条件：二叉树存在，e是T中某个结点的位置。*/ /*操作结果：给处于位置e层，本层序号的结点赋新值value。*/ Status Assign(SqBiTree T,position e,TElemType value) /*初始条件：二叉树T存在，e是T中某个结点。*/ /*操作结果：若e是T的非根结点，则返回它的双亲；否则返回空。*/ TElemType Parent(SqBiTree T,TElemType e) /*初始条件：二叉树T存在,e是树T中的某个结点。*/ /*操作结果：返回e的左孩子。若e无左孩子，则返回"空"。*/ TElemType LeftChild(SqBiTree T,TElemType e) /*初始条件：二叉树T存在,e是树T中的某个结点。*/ /*操作结果：返回e的右孩子。若e无右孩子，则返回"空"。*/ TElemType RightChild(SqBiTree T,TElemType e) /*初始条件：二叉树T存在，e是T中某个结点。*/ /*操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回"空"。*/ TElemType LeftSibling(SqBiTree T,TElemType e) /*初始条件：二叉树T存在，e是T中某个结点。*/ /*操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回"空"。*/ TElemType RightSibling(SqBiTree T,TElemType e) /*初始条件：二叉树T存在。*/ /*把从q的j结点开始的子树移为从T的i结点开始的子树。*/ void Move(SqBiTree q,int j,SqBiTree T,int i) /*初始条件：二叉树存在，p是T中某个结点的值，LR为0或1，非空二叉树c与T不相交且右子树为空。*/ /*操作结果：根据LR为0或1，插入c为T中p结点的左或右子树,p结点的原有左或右子树则为c的右子树。*/ void InserChild(SqBiTree T,TElemType p,int LR,SqBiTree c) /*初始条件：二叉树T存在，Visit是对结点操作的应用函数。*/ /*操作结果：层序遍历二叉树*/ void LevelOrderTraverse(SqBiTree T,void(*Visit)(TElemType)) 二叉树函数定义基本实现:

·在i层结点的序号从pow(2,i-1)-1到pow(2,i)-2；

·序号为i的结点，其双亲序号为(i+1)/2-1,其左右孩子序号分别为2i+1和2i+2；

·除了根节点，序号为奇数的结点是其双亲的左孩子，它的右兄弟的序号是它的序号+1；

·除了根节点，序号为偶数的结点是其双亲的右孩子，它的左兄弟的序号是它的序号-1；

·i层的满二叉树，其结点总数为pow(2,i)-1

(1)构造空的二叉树T

/*构造空的二叉树T。*/ void InitBiTree(SqBiTree T) { int i; for(i=0;i<MAX_TREE_SIZE;i++) T[i]=0; }在顺序存储结构中，二叉树的清空与销毁和构造空二叉树函数完全一样。

(2)输入二叉树中结点的值，构造顺序存储的二叉树T

/*按层序次序输入二叉树中结点的值，构造顺序存储的二叉树T。*/ void CreateBiTree(SqBiTree T) { int i=0; InitBiTree(T); //构造空二叉树T printf("请按层序输入结点的值，0表示空结点，输入999表示结束：\n"); while(1) { scanf("%d",&T[i]); if(T[i]==999) { T[i]=0; break; } i++; } for(i=1;i<MAX_TREE_SIZE;i++) if(i!=0&&T[(i+1)/2-1]==0&&T[i]!=0) //此结点无双亲且不是根节点 { printf("出现无双亲的非根结点，程序退出!\n"); exit(0); } }

(3)判断二叉树是否为空树

/*初始条件：二叉树T存在。*/ /*操作结果：若二叉树T为空二叉树，则返回TRUE；否则返回FALSE。*/ Status BiTreeEmpty(SqBiTree T) { if(T[0]==0) //根结点为空则为空 return TRUE; else return FALSE; }

(4)返回二叉树深度

/*初始条件：二叉树T存在。*/ /*操作结果：返回树T的深度。*/ int BiTreeDepth(SqBiTree T) { int i; int j=-1; for(i=MAX_TREE_SIZE-1;i>=0;i--) //找到最后一个结点 if(T[i]!=0) break; i++; //为了便于计算 do j++; while(i>=pow(2,j)); return j; }

(5)返回二叉树的根

/*初始条件：二叉树存在。*/ /*操作结果：当T不为空，用e返回T的根，返回OK；否则返回ERROR，e无定义。*/ Status Root(SqBiTree T,TElemType &e) { if(BiTreeEmpty(T)) //二叉树为空树 { return ERROR; }else{ e=T[0]; return OK; } }

(6)返回二叉树中某个结点位置

/*初始条件：二叉树存在，e是T中某个结点的位置。*/ /*操作结果：返回处于位置e层，本层序号的结点的值。*/ TElemType Value(SqBiTree T,position e) { return T[int(pow(2,e.level-1)+e.order-2)]; }

(7)二叉树中某个结点赋新值

/*初始条件：二叉树存在，e是T中某个结点的位置。*/ /*操作结果：给处于位置e层，本层序号的结点赋新值value。*/ Status Assign(SqBiTree T,position e,TElemType value) { int i=pow(2,e.level-1)+e.order-2; //将层、本层序号转为矩阵的序号 if(value!=0&&(T[(i+1)/2-1]==0)) //给叶子赋非空值但双亲为空 return ERROR; else if(value==0&&(T[i*2+1]!=0||T[i*2+2]!=0)) //给双亲赋空值但有叶子(不空) return ERROR; T[i]=value; return OK; }

(8)返回结点双亲

/*初始条件：二叉树T存在，e是T中某个结点。*/ /*操作结果：若e是T的非根结点，则返回它的双亲；否则返回空。*/ TElemType Parent(SqBiTree T,TElemType e) { int i; if(T[0]==0) //空树 return 0; for(i=1;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e) //找到e return T[(i+1)/2-1]; return 0; //没有找到e }

(9)返回结点孩子

返回左孩子

/*初始条件：二叉树T存在,e是树T中的某个结点。*/ /*操作结果：返回e的左孩子。若e无左孩子，则返回"空"。*/ TElemType LeftChild(SqBiTree T,TElemType e) { int i; if(T[0]==0) //空树 return 0; for(i=0;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e) //找到e return T[i*2+1]; return 0; } 返回右孩子

/*初始条件：二叉树T存在,e是树T中的某个结点。*/ /*操作结果：返回e的右孩子。若e无右孩子，则返回"空"。*/ TElemType RightChild(SqBiTree T,TElemType e) { int i; if(T[0]==0) //空树 return 0; for(i=0;i<=MAX_TREE_SIZE;i++) if(T[i]==e) //找到e return T[i*2+2]; return 0; //没有找到 }

(10)返回结点兄弟

返回左兄弟

/*初始条件：二叉树T存在，e是T中某个结点。*/ /*操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回"空"。*/ TElemType LeftSibling(SqBiTree T,TElemType e) { int i; if(T[0]==0) //空树 return 0; for(i=1;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e&&i%2==0) //找到e且其序号为偶数是右孩子 return T[i-1]; return 0; //没找到e } 返回右兄弟

/*初始条件：二叉树T存在，e是T中某个结点。*/ /*操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回"空"。*/ TElemType RightSibling(SqBiTree T,TElemType e) { int i; if(T[0]==0) //空树 return 0; for(i=1;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e&&i%2) //找到e且其序号为奇数做孩子 return T[i+1]; return 0; //没找到e }

(11)对子树的操作

/*初始条件：二叉树T存在。*/ /*把从q的j结点开始的子树移为从T的i结点开始的子树。*/ void Move(SqBiTree q,int j,SqBiTree T,int i) { if(q[2*j+1]!=0) //q的左子树不空 Move(q,(2*j+1),T,(2*i+1)); //把q的j结点的左子树移为T的i结点的左子树 if(q[2*j+2]!=0) //q的右子树不空 Move(q,(2*j+2),T,(2*i+2)); //把q的j结点右子树移为T的i结点的右子树 T[i]=q[j]; //把q的j结点移为T的i结点 q[j]=0; }

(12)插入原有左右子树

/*初始条件：二叉树存在，p是T中某个结点的值，LR为0或1，非空二叉树c与T不相交且右子树为空。*/ /*操作结果：根据LR为0或1，插入c为T中p结点的左或右子树,p结点的原有左或右子树则为c的右子树。*/ void InserChild(SqBiTree T,TElemType p,int LR,SqBiTree c) { int j,k,i=0; for(j=0;j<int(pow(2,BiTreeDepth(T)))-1;j++) //查找p的序号 if(T[j]==p) //j为p的序号 break; k=2*j+1+LR; //k为p的左或右孩子的序号 if(T[k]!=0) Move(T,k,T,2*k+2); //把从T的k结点开始的子树移为从k结点的右子树开始的子树 Move(c,i,T,k); }

(13)层次遍历二叉树

/*初始条件：二叉树T存在，Visit是对结点操作的应用函数。*/ /*操作结果：层序遍历二叉树*/ void LevelOrderTraverse(SqBiTree T,void(*Visit)(TElemType)) { int j; int i=MAX_TREE_SIZE-1; while(T[i]==0) i--; for(j=0;j<=i;j++) //从根结点起，按层序遍历二叉树 if(T[j]!=0) Visit(T[j]); //只遍历非空的结点 printf("\n"); }

嗯下面就是在VC中测试

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAX_TREE_SIZE 100 #define ClearBiTree InitBiTree //顺序存储结构中，两函数完全一样 #define DestroyBiTree InitBiTree //顺序存储结构中，两函数完全一样 typedef int TElemType; typedef int Status; typedef TElemType SqBiTree[MAX_TREE_SIZE]; struct position{ int level; //结点的层 int order; //本层序号 }; void visit(TElemType e) { printf("%d \n",e); } /*构造空的二叉树T。*/ void InitBiTree(SqBiTree T) { int i; for(i=0;i<MAX_TREE_SIZE;i++) T[i]=0; } /*按层序次序输入二叉树中结点的值，构造顺序存储的二叉树T。*/ void CreateBiTree(SqBiTree T) { int i=0; InitBiTree(T); //构造空二叉树T printf("请按层序输入结点的值，0表示空结点，输入999表示结束：\n"); while(1) { scanf("%d",&T[i]); if(T[i]==999) { T[i]=0; break; } i++; } for(i=1;i<MAX_TREE_SIZE;i++) if(i!=0&&T[(i+1)/2-1]==0&&T[i]!=0) //此结点无双亲且不是根节点 { printf("出现无双亲的非根结点，程序退出!\n"); exit(0); } } /*初始条件：二叉树T存在。*/ /*操作结果：若二叉树T为空二叉树，则返回TRUE；否则返回FALSE。*/ Status BiTreeEmpty(SqBiTree T) { if(T[0]==0) //根结点为空则为空 return TRUE; else return FALSE; } /*初始条件：二叉树T存在。*/ /*操作结果：返回树T的深度。*/ int BiTreeDepth(SqBiTree T) { int i; int j=-1; for(i=MAX_TREE_SIZE-1;i>=0;i--) //找到最后一个结点 if(T[i]!=0) break; i++; //为了便于计算 do j++; while(i>=pow(2,j)); return j; } /*初始条件：二叉树存在。*/ /*操作结果：当T不为空，用e返回T的根，返回OK；否则返回ERROR，e无定义。*/ Status Root(SqBiTree T,TElemType &e) { if(BiTreeEmpty(T)) //二叉树为空树 { return ERROR; }else{ e=T[0]; return OK; } } /*初始条件：二叉树存在，e是T中某个结点的位置。*/ /*操作结果：返回处于位置e层，本层序号的结点的值。*/ TElemType Value(SqBiTree T,position e) { return T[int(pow(2,e.level-1)+e.order-2)]; } /*初始条件：二叉树存在，e是T中某个结点的位置。*/ /*操作结果：给处于位置e层，本层序号的结点赋新值value。*/ Status Assign(SqBiTree T,position e,TElemType value) { int i=pow(2,e.level-1)+e.order-2; //将层、本层序号转为矩阵的序号 if(value!=0&&(T[(i+1)/2-1]==0)) //给叶子赋非空值但双亲为空 return ERROR; else if(value==0&&(T[i*2+1]!=0||T[i*2+2]!=0)) //给双亲赋空值但有叶子(不空) return ERROR; T[i]=value; return OK; } /*初始条件：二叉树T存在，e是T中某个结点。*/ /*操作结果：若e是T的非根结点，则返回它的双亲；否则返回空。*/ TElemType Parent(SqBiTree T,TElemType e) { int i; if(T[0]==0) //空树 return 0; for(i=1;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e) //找到e return T[(i+1)/2-1]; return 0; //没有找到e } /*初始条件：二叉树T存在,e是树T中的某个结点。*/ /*操作结果：返回e的左孩子。若e无左孩子，则返回"空"。*/ TElemType LeftChild(SqBiTree T,TElemType e) { int i; if(T[0]==0) //空树 return 0; for(i=0;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e) //找到e return T[i*2+1]; return 0; } /*初始条件：二叉树T存在,e是树T中的某个结点。*/ /*操作结果：返回e的右孩子。若e无右孩子，则返回"空"。*/ TElemType RightChild(SqBiTree T,TElemType e) { int i; if(T[0]==0) //空树 return 0; for(i=0;i<=MAX_TREE_SIZE;i++) if(T[i]==e) //找到e return T[i*2+2]; return 0; //没有找到 } /*初始条件：二叉树T存在，e是T中某个结点。*/ /*操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回"空"。*/ TElemType LeftSibling(SqBiTree T,TElemType e) { int i; if(T[0]==0) //空树 return 0; for(i=1;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e&&i%2==0) //找到e且其序号为偶数是右孩子 return T[i-1]; return 0; //没找到e } /*初始条件：二叉树T存在，e是T中某个结点。*/ /*操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回"空"。*/ TElemType RightSibling(SqBiTree T,TElemType e) { int i; if(T[0]==0) //空树 return 0; for(i=1;i<=MAX_TREE_SIZE-1;i++) if(T[i]==e&&i%2) //找到e且其序号为奇数做孩子 return T[i+1]; return 0; //没找到e } /*初始条件：二叉树T存在。*/ /*把从q的j结点开始的子树移为从T的i结点开始的子树。*/ void Move(SqBiTree q,int j,SqBiTree T,int i) { if(q[2*j+1]!=0) //q的左子树不空 Move(q,(2*j+1),T,(2*i+1)); //把q的j结点的左子树移为T的i结点的左子树 if(q[2*j+2]!=0) //q的右子树不空 Move(q,(2*j+2),T,(2*i+2)); //把q的j结点右子树移为T的i结点的右子树 T[i]=q[j]; //把q的j结点移为T的i结点 q[j]=0; } /*初始条件：二叉树存在，p是T中某个结点的值，LR为0或1，非空二叉树c与T不相交且右子树为空。*/ /*操作结果：根据LR为0或1，插入c为T中p结点的左或右子树,p结点的原有左或右子树则为c的右子树。*/ void InserChild(SqBiTree T,TElemType p,int LR,SqBiTree c) { int j,k,i=0; for(j=0;j<int(pow(2,BiTreeDepth(T)))-1;j++) //查找p的序号 if(T[j]==p) //j为p的序号 break; k=2*j+1+LR; //k为p的左或右孩子的序号 if(T[k]!=0) Move(T,k,T,2*k+2); //把从T的k结点开始的子树移为从k结点的右子树开始的子树 Move(c,i,T,k); } /*初始条件：二叉树T存在，Visit是对结点操作的应用函数。*/ /*操作结果：层序遍历二叉树*/ void LevelOrderTraverse(SqBiTree T,void(*Visit)(TElemType)) { int j; int i=MAX_TREE_SIZE-1; while(T[i]==0) i--; for(j=0;j<=i;j++) //从根结点起，按层序遍历二叉树 if(T[j]!=0) Visit(T[j]); //只遍历非空的结点 printf("\n"); } int main() { int i; int ch; position p; TElemType e; SqBiTree T,s; InitBiTree(T); printf("成功构造空二叉树\n"); CreateBiTree(T); printf("********************************\n"); printf("1、结点双亲\n2、结点孩子\n3、左右兄弟\n"); printf("4、对树判空\n5、返回树深\n6、修改结点\n"); printf("7、逐层遍历\n0、退出操作\n"); printf("********************************\n"); printf("请选择接下来的操作："); while(scanf("%d",&ch)&&ch!=0) { if(ch==1){ printf("请输入要寻找双亲的结点："); scanf("%d",&e); if(Parent(T,e)){ printf("%d结点的双亲是%d\n",e,Parent(T,e)); }else{ printf("输入错误!\n"); } } if(ch==2){ printf("请输入要查询孩子的根节点："); scanf("%d",&e); if(LeftChild(T,e)){ printf("%d的左孩子是%d ",e,LeftChild(T,e)); } if(RightChild(T,e)){ printf("%d的右孩子是%d ",e,LeftChild(T,e)); } printf("\n"); } if(ch==3){ printf("请输入要查询左右兄弟的结点："); scanf("%d",&e); if(LeftSibling(T,e)){ printf("%d结点的左兄弟是%d ",e,LeftSibling(T,e)); } if(RightSibling(T,e)){ printf("%d结点的右兄弟是%d ",e,RightSibling(T,e)); } printf("\n"); } if(ch==4){ if(BiTreeEmpty(T)){ printf("这是一个空树!\n"); }else{ printf("这是一个非空树!\n"); } } if(ch==5){ printf("树的深度为%d\n",BiTreeDepth(T)); } if(ch==6){ printf("请输入要修改结点的层号和本层序号："); scanf("%d%d",&p.level,&p.order); printf("请输入修改以后的值："); scanf("%d",&e); if(Assign(T,p,e)) printf("操作成功!\n"); else printf("输入错误!\n"); } if(ch==7){ LevelOrderTraverse(T,visit); } printf("请选择接下来的操作："); } printf("成功退出操作!\n"); return 0; }