// c6-1.h 二叉树的顺序存储结构(见图6.1)#define MAX_TREE_SIZE 100 // 二叉树的最大结点数typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 0号单元存储根结点struct position{	int level,order; // 结点的层,本层序号(按满二叉树计算)};

在顺序存储结构中，如图62 所示，第i 层结点的序号从2i1 -1～2i-2；序号为i 的结

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

奇数的结点是其双亲的左孩子，它的右兄弟的序号是它的序号+1；序号为偶数的结点是其

双亲的右孩子，它的左兄弟的序号是它的序号-1；i 层的满二叉树，其结点总数为2i-1。

显然，在顺序存储结构中，按层序输入二叉树是最方便的。当最后一个结点的值输入

后，输入给定符号表示结束。二叉树的顺序存储结构适合存完全二叉树或近似完全二

叉树。

bo6-1.cpp 是采用顺序存储结构的基本操作程序，main6-1.cpp 是检验这些基本操作的

主程序。为了使这两个程序在结点类型为整型和字符型时都能使用，采用了编译预处理的

“#define”、“#if”等命令。这样，只要将main6-1.cpp 的第2 行或第3 行改为注释行

即可。

// bo6-1.cpp 二叉树的顺序存储(存储结构由c6-1.h定义)的基本操作(23个)#define ClearBiTree InitBiTree // 在顺序存储结构中，两函数完全一样#define DestroyBiTree InitBiTree // 在顺序存储结构中，两函数完全一样void InitBiTree(SqBiTree T){ // 构造空二叉树T。因为T是数组名，故不需要&	int i;	for(i=0;i
    
     >T[i];		if(T[i]==999)		{			T[i]=Nil;			break;		}		i++;	}#endif	for(i=1;i
     
      =0;i--) // 找到最后一个结点		if(T[i]!=Nil)			break;		i++; // 为了便于计算		do		j++;		while(i>=pow(2,j));		return j;}Status Root(SqBiTree T,TElemType &e){ // 初始条件：二叉树T存在。操作结果：当T不空，用e返回T的根，返回OK；否则返回ERROR，e无定义	if(BiTreeEmpty(T)) // T空		return ERROR;	else	{		e=T[0];		return OK;	}}TElemType Value(SqBiTree T,position e){ // 初始条件：二叉树T存在，e是T中某个结点(的位置)	// 操作结果：返回处于位置e(层,本层序号)的结点的值	return T[int(pow(2,e.level-1)+e.order-2)];}Status Assign(SqBiTree T,position e,TElemType value){ // 初始条件：二叉树T存在，e是T中某个结点(的位置)	// 操作结果：给处于位置e(层,本层序号)的结点赋新值value	int i=int(pow(2,e.level-1)+e.order-2); // 将层、本层序号转为矩阵的序号	if(value!=Nil&&T[(i+1)/2-1]==Nil) // 给叶子赋非空值但双亲为空		return ERROR;	else if(value==Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) // 给双亲赋空值但有叶子(不空)		return ERROR;	T[i]=value;	return OK;}TElemType Parent(SqBiTree T,TElemType e){ // 初始条件：二叉树T存在，e是T中某个结点	// 操作结果：若e是T的非根结点，则返回它的双亲；否则返回“空”	int i;	if(T[0]==Nil) // 空树		return Nil;	for(i=1;i<=MAX_TREE_SIZE-1;i++)		if(T[i]==e) // 找到e			return T[(i+1)/2-1];		return Nil; // 没找到e}TElemType LeftChild(SqBiTree T,TElemType e){ // 初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子,则返回“空”	int i;	if(T[0]==Nil) // 空树		return Nil;	for(i=0;i<=MAX_TREE_SIZE-1;i++)		if(T[i]==e) // 找到e			return T[i*2+1];		return Nil; // 没找到e}TElemType RightChild(SqBiTree T,TElemType e){ // 初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子,则返回“空”	int i;	if(T[0]==Nil) // 空树		return Nil;	for(i=0;i<=MAX_TREE_SIZE-1;i++)		if(T[i]==e) // 找到e			return T[i*2+2];		return Nil; // 没找到e}TElemType LeftSibling(SqBiTree T,TElemType e){ // 初始条件：二叉树T存在，e是T中某个结点	// 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”	int i;	if(T[0]==Nil) // 空树		return Nil;	for(i=1;i<=MAX_TREE_SIZE-1;i++)		if(T[i]==e&&i%2==0) // 找到e且其序号为偶数(是右孩子)			return T[i-1];		return Nil; // 没找到e}TElemType RightSibling(SqBiTree T,TElemType e){ // 初始条件：二叉树T存在，e是T中某个结点	// 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”	int i;	if(T[0]==Nil) // 空树		return Nil;	for(i=1;i<=MAX_TREE_SIZE-1;i++)		if(T[i]==e&&i%2) // 找到e且其序号为奇数(是左孩子)			return T[i+1];		return Nil; // 没找到e}void Move(SqBiTree q,int j,SqBiTree T,int i) // InsertChild()用到。加{ // 把从q的j结点开始的子树移为从T的i结点开始的子树	if(q[2*j+1]!=Nil) // q的左子树不空		Move(q,(2*j+1),T,(2*i+1)); // 把q的j结点的左子树移为T的i结点的左子树	if(q[2*j+2]!=Nil) // q的右子树不空		Move(q,(2*j+2),T,(2*i+2)); // 把q的j结点的右子树移为T的i结点的右子树	T[i]=q[j]; // 把q的j结点移为T的i结点	q[j]=Nil; // 把q的j结点置空}void InsertChild(SqBiTree T,TElemType p,int LR,SqBiTree c){ //初始条件：二叉树T存在，p是T中某个结点的值，LR为0或1，非空二叉树c与T不相交且右子树为空	//操作结果:根据LR为0或1,插入c为T中p结点的左或右子树。p结点的原有左或右子树则成为c的右子树	int j,k,i=0;	for(j=0;j
     
    

// main6-1.cpp 检验bo6-1.cpp的主程序，利用条件编译选择数据类型为char或int//#define CHAR 1 // 字符型#define CHAR 0 // 整型(二者选一)#include"c1.h"#if CHARtypedef char TElemType;TElemType Nil=''; // 设字符型以空格符为空#elsetypedef int TElemType;TElemType Nil=0; // 设整型以0为空#endif#include"c6-1.h"#include"bo6-1.cpp"void visit(TElemType e){	cout<
    
     <<"";}void main(){	Status i;	int j;	position p;	TElemType e;	SqBiTree T,s;	InitBiTree(T);	CreateBiTree(T);	cout<<"建立二叉树后,树空否？"<
     
      <<"(1:是0:否) 树的深度="<
      
       <
       
        >p.level>>p.order;	e=Value(T,p);	cout<<"待修改结点的原值为"<
        
         <<"请输入新值: ";	cin>>e;	Assign(T,p,e);	cout<<"先序遍历二叉树:"<
         
          >e>>j; InsertChild(T,e,j,s); Print(T); cout<<"删除子树,请输入待删除子树根结点的层号本层序号左(0)或右(1)子树: "; cin>>p.level>>p.order>>j; DeleteChild(T,p,j); Print(T); ClearBiTree(T); cout<<"清除二叉树后,树空否？"<
          
           <<"(1:是0:否) 树的深度="<
           
            <
           
          
         
        
       
      
     
    

代码的运行结果：

请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤100:

1 2 3 4 5 0 6 7 999(见图63)

建立二叉树后,树空否？0(1:是0:否) 树的深度=4

二叉树的根为1

层序遍历二叉树:

1 2 3 4 5 6 7

中序遍历二叉树:

7 4 2 5 1 3 6

后序遍历二叉树:

7 4 5 2 6 3 1

请输入待修改结点的层号本层序号: 2 2

待修改结点的原值为3请输入新值: 8

先序遍历二叉树:

1 2 4 7 5 8 6

结点8的双亲为1,左右孩子分别为0,6,左右兄弟分别为2,0

建立右子树为空的树s:

请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤100:

10 11 0 13 14 0 0 17 999(见图64)

树s插到树T中,请输入树T中树s的双亲结点s为左(0)或右(1)子树: 2 1(见图65)

第1层: 1:1

第2层: 1:2 2:8

第3层: 1:4 2:10 4:6

第4层: 1:7 3:11 4:5

第5层: 5:13 6:14

第6层: 9:17

删除子树,请输入待删除子树根结点的层号本层序号左(0)或右(1)子树: 3 2 0(见图66)

第1层: 1:1

第2层: 1:2 2:8

第3层: 1:4 2:10 4:6

第4层: 1:7 4:5

清除二叉树后,树空否？1(1:是0:否) 树的深度=0

树空，无根