数据结构实验——exp4--二叉树实验

一、 实验任务

1. 设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。

实验测试数据基本要求：

第一组数据： bt151.btr

第二组数据： bt21.btr

     2.求二叉树的叶子结点数和1度结点数。

       实验测试数据基本要求：

第一组数据： bt261.btr

第二组数据： bt21.btr

3.键盘输入一个元素x，求其父节点、兄弟结点、子结点的值，不存在时给出相应提示信息。对兄弟结点和孩子结点，存在时要明确指出是左兄弟、左孩子、右兄弟或右孩子。

       实验测试数据基本要求：

第一组数据： bt31.btr

第二组数据： bt21.btr

4.键盘输入一个元素x，求其在树中的层次。不存在时给出相应提示信息。

       实验测试数据基本要求：

第一组数据： bt262.btr

第二组数据： bt21.btr

5.将按顺序方式存储在数组中的二叉树转换为二叉链表形式。（数组中要扩展为完全二叉树）。

       实验测试数据基本要求：

第一组数据： bt8.btr

第二组数据： bt14.btr

6.输出二叉树从每个叶子结点到根结点的路径（经历的结点）。

       实验测试数据基本要求：

第一组数据： bt261.btr

第二组数据： bt21.btr

7.对二叉链表表示的二叉树，按从上到下，从左到右打印结点值，即按层次遍历序打印。（提示：需要使用队列）

       实验测试数据基本要求：

第一组数据： bt261.btr

第二组数据： bt21.btr

二、 二叉树扩展实验

非必做内容，有兴趣的同学选做，

1. 复制一棵二叉树T到T1。

       实验测试数据基本要求：

第一组数据： bt151.btr

第二组数据： bt21.btr

2.交换二叉树中每个结点的左右孩子指针的值。（即：左子树变为右子树，右子树变为左子树）。

       实验测试数据基本要求：

第一组数据： bt151.btr

第二组数据： bt21.btr

3.对二叉链表表示的二叉树，求2个结点最近的共同祖先。

       实验测试数据基本要求：

第一组数据： bt261.btr

第二组数据： bt21.btr

三、算法设计

（除书上给出的基本运算（这部分不必给出设计思想），其它实验内容要给出算法设计思想）

    从文件中读数据到二叉树中：

结点数据读入数组函数：因为是按先序次序递归创建二叉树，在创建过程中又要记录读取数据的行数，所以直接从文件中读取数据创建时处理不方便，因此可以先把文件中的数据读取到一个二维数组中，再从数组中读取数据来创建二叉树。考虑到文件内容有点不一样。文件扩展名没有限制，程序只根据标识“BinaryTree”判定是否二叉树数据文件。文件中可以有空行。文件可以有注释行，注释行必须以“//”开始，且注释行必须是单独的行，不能混杂在标识行、数据行中。因此读文件的时候需要自定义一个去除空格的函数，然后再一个循环中，判断，去掉空格的第一个和第二个数据是’/n’和’//’的时候跳过此次循环，当不为空格或者注释的时候，说明空格注释已经遍历过了，到了标识的时候。此时再进行判断是否含有BinaryTree，若有则正确，否则文件格式错误。之后再一个字符的判断，是否第一个是’/’若是则说明是注释，跳到下一行。若不是则把一行的三个数据读入。最后关闭文件。在将数组读入二叉树中，结束。

(1) 改造先序遍历算法，增加一个结点层次参数，当递归遍历 T->lChild

子树时，结点层次为 T 的层次加 1；之后递归遍历 T-> rChild子树时，结点层次为T + 1。输出形式：(结点值，层次)。初始调用 outMidOrder(T,1)。

(2)采用中序遍历，命名两个整型变量储存叶子节点数和1度节点数，首先递归调用左子树，当T->lChild == NULL && T->rChild == NULL 时ye++;当(T->lChild != NULL && T->rChild == NULL) || (T->lChild == NULL && T->rChild != NULL)时Du++，然后再递归调用右子树。

(3)采用先序遍历，三个形参，数结点，输入的变量，一个bool类型的数据用来标志是否查找到。首先是T->lChild != NULL && T->lChild->data == x，说明最多只有右兄弟，一种情况，再仔细判断是否有双亲结点，左孩子右孩子，最后把f标志为true。之后当T->rChild != NULL && T->rChild->data == x时说明最多只有左兄弟，一种情况，再仔细判断是否有双亲结点，左孩子右孩子，最后把f标志为true。做后是T->data == x，这说明是根节点，没有双亲结点和兄弟节点，只需判断是否有孩子节点即可。之后再分别递归调用左子树右子树。

(4) 采用先序遍历，四个形参，数结点，高度， 输入的变量，一个bool类型的数据用来标志是否查找到。首先当树不空的时候，每次递归调用左子树或者右子树，都需要对高度进行加一，之后再每次递归调用之前判断是否查找到输入的元素，若查找到，进行输出当前传入形参的高度，再将标志标为true。最后递归调用左子树右子树。

(5) 造先序遍历实现。算法包括两个整型参数 i 和 num。i 为结点在完全二叉树上的编号，从 1 开始；num 为二叉树上最后有效结点编号。对每次i <= num && A[i] != '0'时，进行new 一个树节点，把数组数据传进去，再把该树的左子树右子树，全部赋值为NULL。最后在递归调用左右子树。注意，在顺序储存中，左子树和父节点的关系为2倍，右子树为父节点的二倍加1，当数组0下标为空时刚好下标与之对应。所以当调用左子树的时候，记得为2 * i，调用右子树时为2 * i + 1。

(6) 从根结点开始遍历，用栈存储路径上每个结点的数值，有左子树往左走，没有左子树再往右子树走，如果都没有左右子树说明到了叶子结点了，那么路径就完整了，就可以打印栈的内容了，

1.当遍历到了叶子结点d，此时这条路径便已经完整了，而结点b还有另一个右孩子结点e，那么遍历到d的路径和遍历到e的路径只差了最后一个结点，那么只需要把结点d出栈，再把结点e入栈，遍历到e的路径就完整了吗，所以每次遍历到叶子结点将栈打印完后，只需将该叶子结点出栈。

2.当此时已经遍历完结点e并出栈了，此时b的左右孩子结点已经都遍历完了，不再被需要了，此时若想若遍历到c结点，只需要将结点b出栈，那么a的左子树已经遍历完，此时再往右子树走，也就是c点走，这样就能获取遍历到c结点的路径。

此算法实际操作时，为了操作方便，用数组来模拟栈。

(7)二叉树的层次遍历，我们定义一个队列，先将根结点入队；当前结点是队头结点，将其出队并访问；若当前结点的左结点不为空将左结点入队；若当前结点的右结点不为空将其入队即可。

此算法实际操作时，为了操作方便，用数组来模拟队列。

(8)声明两个形参，一个传指针，一个传指针的引用，因为要操作树节点的里面内容们需要指针的引用，或者用指针的指针。当树不为空时，new 一个树节点，把当前树的值赋值给新的树，之后把新树的左右孩子赋值为空。最后在递归调用左右孩子进行遍历即可。

(9)将左右子树交换。此时对先序遍历改编。当树节点不为空时，临时声明一个树节点的空指针。把左右子树进行交换，再进行递归调用即可。

(10)采用递归方式。命名两个指针为左右树，进行递归调用查找左右子树。递归结束的标志就是,  在某个节点的左字数发现一个节点, 右子树发现一个节点, 那就是此节点了;返回T

如果左子树发现了, 右子树没有发现, 那就继续往左子树寻找;返回left.

如果右子树发现了, 左子树没有发现, 那就继续往右子树寻找;返回right。

#include 
#include
using namespace std;

typedef struct lBNode{
	char data;
	struct lBNode *lChild, *rChild;
}BiNode;

void TrimLeft(char str[]){
	int j, i = 0;
	while(str[i] == ' '){
		i++;
	}
	strncpy(str,str + i, 1000 - i);
	return;
}
bool ReadFileToArray(char fileName[], char strLine[100][3], int nArrLen)
{   // fileName[]存放文件名
    // strLine[][3]存放结点的二维数组，数组的3列对应数据文件的3列
	// nArrLen返回二叉树结点的个数
	FILE* pFile;  //定义二叉树的文件指针
	char str[1000];  //存放读出一行文本的字符串
	char strTmp[10] = "";
	pFile = fopen(fileName, "r");
	if(!pFile){
		printf("二叉树数据文件打开失败！n");
		return false;
	}
	
	while (fgets(str,1000,pFile) != NULL )
    {
        TrimLeft(str);//这个函数是为了去掉左面的空格，须自定义
        if ( str[0] == 'n' ){
            continue;           //空行跳过
        }
        strncpy(strTmp,str,2);
        if ( strcmp (strTmp,"//") == 0 ){
            continue;
        }
        else{
            break;
        }
    }
    if(strcmp(str,"BinaryTreen") != 0){
		printf("打开的文件格式错误！n");
		fclose(pFile);     //关闭文件
		return false;
	}
	nArrLen = 0;
	char s[10];
    while(fgets(s, 10, pFile) != NULL ){
    	if(s[0] != 'n' && s[0] != '/'){
    		strLine[nArrLen][0] = s[0];
			strLine[nArrLen][1] = s[3];
			strLine[nArrLen][2] = s[6];
			nArrLen++;
		}
	}
//	while(fscanf(pFile,"%c  %c  %cn",
//		  &strLine[nArrLen][0], &strLine[nArrLen][1], &strLine[nArrLen][2]) != EOF)	
//	{             //循环读取结点行数据，存入数组，结点总数加1
//		nArrLen++;
//	}
	fclose(pFile); //关闭文件
	return true;
}
//从数组数据按先序次序创建二叉树
bool CreateBiTreeFromFile(BiNode*& pBT, char strLine[100][3],int nLen, int & nRow)
{
	    //strLine[100][3]--保存结点数据的二维数组
	    //nLen--结点个数
	    //nRow--数组当前行号
	if((nRow >= nLen) || (nLen == 0))
		return false;   //数据已经处理完毕，或者没有数据，退出
	    //根据数组数据递归创建二叉树
	pBT = new BiNode;  //建立根结点
	pBT->data = strLine[nRow][0];
	pBT->lChild = NULL;
	pBT->rChild = NULL;
	int nRowNext = nRow;         //保留本次递归的行号	
	if(strLine[nRowNext][1] == '1')  
	{               //当前结点有左子树，读下一行数据，递归调用创建左子树。
		nRow++;     //行号加1
		CreateBiTreeFromFile(pBT->lChild, strLine, nLen, nRow);
	}
	if(strLine[nRowNext][2] == '1')  
	{               //当前结点有右子树，读下一行数数，递归调用创建右子树。
		nRow++;    //行号加1
		CreateBiTreeFromFile(pBT->rChild, strLine,nLen,nRow);		
	}
	return true;
}

void DestroyBiTree(BiNode* pBT)
{
	if(pBT)
	{
		DestroyBiTree(pBT->lChild);   //递归销毁左子树
		DestroyBiTree(pBT->rChild);   //递归销毁右子树
		delete pBT;                  //释放当前根结点
	}
}
void B(BiNode* T){
	if(T){
		cout << T->data;
		B(T->lChild);
		B(T->rChild);
	}
}

void outMidOrder(BiNode *T, int level)
{
	if(T){
		outMidOrder(T->lChild,level + 1); //T 的孩子层次为 T 的层次加 1
		cout<<"("<data<<","<rChild,level + 1); //T 的兄弟层次与 T 相同
	}
}
//2
void yeAnd1Du(BiNode *T, int &ye, int &Du){
	if(T){
		yeAnd1Du(T->lChild, ye, Du);
		if(T->lChild == NULL && T->rChild == NULL){
			ye++;
		}
		if((T->lChild != NULL && T->rChild == NULL) || (T->lChild == NULL && T->rChild != NULL)){
			Du++;
		}
		yeAnd1Du(T->rChild, ye, Du);
	}
}
//3
void find(BiNode *T, char x, bool &f){
	if(T){
		if(T->lChild != NULL && T->lChild->data == x){
			cout << "x的双亲结点的值为：" << T->data << endl;
			if(T->rChild != NULL){
				cout << "x的兄弟结点为右兄弟，其值为：" << T->rChild->data << endl;
			}
			if(T->lChild->lChild != NULL){
				cout << "x的左孩子结点的值为：" << T->lChild->lChild->data << endl;
			} else{
				cout << "没有左孩子" << endl; 
			} 
			if(T->lChild->rChild != NULL){
				cout << "x的右孩子结点的值为：" << T->lChild->rChild->data << endl;
			} else{
				cout << "没有右孩子" << endl; 
			} 
			f = true;
			return;
		}else if(T->rChild != NULL && T->rChild->data == x){
			cout << "x的双亲结点的值为：" << T->data << endl;
			if(T->lChild != NULL){
				cout << "x的兄弟结点为左兄弟，其值为：" << T->lChild->data << endl;
			}
			if(T->rChild->lChild != NULL){
				cout << "x的左孩子结点的值为：" << T->rChild->lChild->data << endl;
			} else{
				cout << "没有左孩子" << endl; 
			} 
			if(T->rChild->rChild != NULL){
				cout << "x的右孩子结点的值为：" << T->rChild->rChild->data << endl;
			} else{
				cout << "没有右孩子" << endl; 
			} 
			f = true;
			return;
		}else if(T->data == x){
			cout << "x没有双亲结点" << endl;
			cout << "x没有兄弟结点" << endl;
			if(T->lChild != NULL){
				cout << "x的左孩子结点的值为：" << T->lChild->data << endl;
			} else{
				cout << "没有左孩子" << endl; 
			} 
			if(T->rChild != NULL){
				cout << "x的右孩子结点的值为：" << T->rChild->data << endl;
			} else{
				cout << "没有右孩子" << endl; 
			} 
			f = true;
			return;
		}
		find(T->lChild, x, f);
		find(T->rChild, x, f);
	}
} 
//4
void findH(BiNode *T, int level, char x, bool &f)
{
	if(T){
		if(T->data == x){
			cout<< T->data << "的高度为：" << level << endl; //访问根结点
			f = true;
		}	
		findH(T->lChild,level + 1, x, f); //T 的孩子层次为 T 的层次加 1
		findH(T->rChild,level + 1, x, f); 
	}
}
//5
void ArrayToBiTree(BiNode *&T, char A[], int i, int num)
{
	//i 为当前结点编号，从 1 开始
	//num 为最后有效结点编号
    if(i <= num && A[i] != '0'){
        T = new BiNode;
        T->data = A[i];
        T->lChild = NULL;
        T->rChild = NULL;
        ArrayToBiTree(T->lChild, A, 2 * i, num);
        ArrayToBiTree(T->rChild, A, 2 * i + 1, num);
    }
}
//6
void Route(BiNode *T, char *path, int pathlen){  //输出二叉树中从每个叶子结点到根结点的路径
	if(T){
		if(T->lChild == NULL && T->rChild == NULL){
			cout<< "叶子结点 " << T->data << " 的路径为：";
			for(int i = pathlen - 1; i >= 0; i--){
				cout<< path[i] << " ";
			}	
			cout << endl;
		}else{
			path[pathlen++] = T->data;
			Route(T->lChild, path, pathlen);
			Route(T->rChild, path, pathlen);
		}
	}
}
//7 
void LevelOrder(BiNode *T)   // 二叉树的层序遍历
{
    BiNode *Q[100];   // 数组模拟队列
    int front = 0;
    int rear = 0;
    BiNode *p;

    Q[++rear] = T;  // 根结点入队
    while (front != rear) {   // 若队列不为空
        // 队头结点出队，并访问出队结点
        p = Q[++front];
        cout << p->data << " ";
        // 出队结点的非空左右孩子依次入队
        if(p->lChild != NULL) {
            Q[++rear] = p->lChild;
        }
        if (p->rChild != NULL) {
            Q[++rear] = p->rChild;
        }
    }
}
//8
void fuZhi(BiNode *T, BiNode *&T1){
	if(T){
		T1 = new BiNode;
		T1->data = T->data;
		T1->lChild = NULL;
		T1->rChild = NULL;
		fuZhi(T->lChild, T1->lChild);
		fuZhi(T->rChild, T1->rChild);
	}
}

//9
//交换二叉树中每个结点的左右孩子指针的值
void ExchangeTree(BiNode *&T)
{
    BiNode * temp;
    if(T)
    {
        temp = T-> lChild;
        T->lChild = T->rChild;
        T->rChild = temp;
        ExchangeTree(T->lChild);
        ExchangeTree(T->rChild);
    }
}
//10
void findHave(BiNode *T,char x, bool &f)
{
	if(T){
		if(T->data == x){ 
			f = true;
		}	
		findHave(T->lChild, x, f);
		findHave(T->rChild, x, f);
	}
}
BiNode * Find(BiNode *T, char p, char q) {
	
	if (T == NULL || T->data == p || T->data == q)return T;
	BiNode *left = Find(T->lChild, p, q);
	BiNode *right = Find(T->rChild, p, q);
	// 左边找到一个值, 右边找到一个值, 说明就是结果了
	if (left && right)return T;
	// 左边找到了,右边没找到, 继续在左边寻找
	if (left)return left;
	// 右边找到了,左边没找到, 继续在右边寻找
	if (right)return right;
}