《数据结构》上机实验(第七章) —树与二叉树Ⅱ

9. 设一棵二叉树中各结点的值互不相同，其先序遍历序列和中序遍历序列分别存于两个一维数组A[1…n]和B[1…n]中，建立该二叉树的二叉链表。算法思想：在这里插入代码片运行结果10. 二叉树按二叉链表形式存储，写一个判别给定二叉树是否是完全二叉树的算法。算法思想：在这里插入代码片运行结果...

—Miss. Z—

1857人浏览 · 2021-08-30 07:44:16

—Miss. Z— · 2021-08-30 07:44:16 发布

1. 设一棵二叉树中各结点的值互不相同，其先序遍历序列和中序遍历序列分别存于两个一维数组A[1…n]和B[1…n]中，建立该二叉树的二叉链表。

BiTNode* PreInCreate(ElemType A[], ElemType B[], int l1, int r1, int l2, int r2)
//l1,h1为先序的第一个和最后一个结点下标，l2,h2为中序的第一个和最后一个结点下标
{
	BiTNode* root = (BiTNode*)malloc(sizeof(BiTNode)); //建根结点
	if (root == NULL) return NULL; //分配内存失败
	root->data = A[l1]; //根结点
	// printf("%d\n",root->data);
	for (int i = l2; B[i] != A[l1]; i++); //在中序遍历序列中查找根结点位置
	int llen = i - l2; //左子树长度
	int rlen = r2 - i; //右子树长度
	if (llen > 0) root->lchild = PreInCreate(A, B, l1 + 1, l1 + llen, l2, llen + l2 - 1); //递归建立左子树
	else root->lchild = NULL; //左子树为空
	if (rlen > 0) root->rchild = PreInCreate(A, B, r1 - rlen + 1, r1, r2 - rlen + 1, r2); //递归建立右子树
	else root->rchild = NULL; //右子树为空
	return root;
}

2. 设一棵二叉树中各结点的值互不相同，其后序遍历序列和中序遍历序列分别存于两个一维数组A[1…n]和B[1…n]中，建立该二叉树的二叉链表。

BiTNode* PostInCreate(ElemType A[], ElemType B[], int l1, int r1, int l2, int r2)
//l1,h1为先序的第一和最后一个结点下标，l2,h2为中序的第一和最后一个结点下标
{
	BiTNode* root = (BiTNode*)malloc(sizeof(BiTNode)); //建根结点
	if (root == NULL) return NULL; //分配内存失败
	root->data = A[r1]; //根结点
	// printf("%d\n",root->data);
	int i = l2, llen, rlen;
	for (i = l2; B[i] != root->data; i++);  //在中序遍历序列中查找根结点位置
	llen = i - l2;  //左子树长度
	rlen = r2 - i; //右子树长度
	if (llen > 0) root->lchild = PostInCreate(A, B, l1, l1 + llen - 1, l2, l2 + llen - 1); //递归建立左子树
	else root->lchild = NULL; //左子树为空
	if (rlen > 0) root->rchild = PostInCreate(A, B, r1 - rlen, r1 - 1, r2 - rlen + 1, r2); //递归建立右子树
	else root->rchild = NULL; //右子树为空
	return root;
}

运行结果

3. 二叉树按二叉链表形式存储，写一个判别给定二叉树是否是完全二叉树的算法。

算法思想：采用层次遍历算法，将所有结点加入队列(包括空结点)。遇到空结点时，检查其后是否有非空结点。若有，则二叉树不是完全二叉树。

bool IsComplete(BiTNode* b) //层次遍历
{
    if (b == NULL) return true; //空树为满二叉树
    BiTNode* p;
    SqQueue* qu;
    InitQueue(qu);
    enQueue(qu, b);
    while (!EmptyQueue(qu))
    {
        deQueue(qu, p);
        if (p != NULL) //结点非空，将其左、右子树入队列
        {
            enQueue(qu, p->lchild);
            enQueue(qu, p->rchild);
        }
        else //结点为空，检查其后是否有非空结点
            while (!EmptyQueue(qu))
            {
                deQueue(qu, p);
                if (p != NULL) return false; //结点非空，则二叉树为非完全二叉树
            }
    }
    return true;
    DestroyQueue(qu);
}

4. 设二叉树采用二叉链表存储结构存储，计算一棵给定二叉树的所有叶子结点/单分支结点/双分支结点个数。

求叶子结点个数

int count = 0; //用于计数的全局变量
void visit(BiTNode* b)
{
	if (b->lchild == NULL && b->rchild == NULL)  
		count++; //如果结点的左、右孩子都NULL，则它为叶子结点
}

int PreLeafNodes(BiTNode* b) //先序遍历求叶子结点个数
{
	if (b != NULL)
	{
		visit(b);
		PreLeafNodes(b->lchild);
		PreLeafNodes(b->rchild);
	}
	return count;
}

int InLeafNodes(BiTNode*& b) //中序遍历求叶子结点个数
{
	if (b != NULL)
	{
		InLeafNodes(b->lchild);
		visit(b);
		InLeafNodes(b->rchild);
	}
	return count;
}


int PostLeafNodes(BiTNode*& b) //后序遍历求叶子结点个数
{
	if (b != NULL)
	{
		PostLeafNodes(b->lchild);
		PostLeafNodes(b->rchild);
		visit(b);
	}
	return count;
}

求单分支结点个数

void visit(BiTNode* b)
{
	if (b->lchild == NULL && b->rchild != NULL || b->lchild != NULL && b->rchild == NULL)  
		count++; //如果结点的左、右孩子有一个是NULL，则它为单分支结点
}

求双分支结点个数

void visit(BiTNode* b)
{
	if (b->lchild != NULL && b->rchild != NULL) count++; //如果结点的左、右孩子都不是NULL，则它为双分支结点
}

运行结果

5. 设树B是一棵采用链式结构存储的二叉树，把树B中所有结点的左、右子树进行交换。

void visit(BiTNode* b)
{
	BiTNode* temp;
	temp = b->lchild;
	b->lchild = b->rchild;
	b->rchild = temp;
	
}

void PreSwap(BiTNode* &b) //先序遍历进行交换(根 左 右)
{
	if (b != NULL)
	{
		visit(b); //交换b结点的左、右孩子
		PreSwap(b->lchild); //再交换b结点的左子树的左、右子树
		PreSwap(b->rchild); //最后交换b结点的右孩子的左、右子树
	}
}

void InSwap(BiTNode* &b) //中序遍历进行交换(左 根 右)
{
	if (b != NULL)
	{
		InSwap(b->lchild); //先交换b结点的左子树的左、右子树
		visit(b); //再交换b结点的左、右孩子
		InSwap(b->rchild); //最后交换b结点的右孩子的左、右子树
	}
}


void PostSwap(BiTNode* &b) //后序遍历进行交换(左 右 根)
{
	if (b != NULL)
	{
		PostSwap(b->lchild); //先交换b结点的左子树的左、右子树
		PostSwap(b->rchild); //再交换b结点的右孩子的左、右子树
		visit(b); /最后交换b结点的左、右孩子
	}
}

运行结果

6. 假设二叉树采用二叉链存储结构存储，求先序/中序/后序遍历序列中第k(1≤k≤二叉树中结点个数)个结点的值。

int count = 1; //定义全局变量用于计数
void PreNode(BiTNode* b,int k) //先序遍历求第k个结点的值
{
	if (b != NULL)
	{
		if (count++ == k)
		{
			printf("%c\n", b->data);
			return;
		}
		PreNode(b->lchild, k);
		PreNode(b->rchild, k);
	}
}

void InNode(BiTNode* b, int k) //中序遍历求第k个结点的值
{
	if (b != NULL)
	{
		InNode(b->lchild, k);
		if (count++ == k)
		{
			printf("%c\n", b->data);
			return;
		}
		InNode(b->rchild, k);
	}
}

void PostNode(BiTNode* b, int k) //后序遍历求第k个结点的值
{
	if (b != NULL)
	{
		PostNode(b->lchild, k);
		PostNode(b->rchild, k);
		if (count++ == k) printf("%c\n", b->data);
		return;
	}
}

运行结果

7. 已知二叉树以二叉链表存储，对于树中每个元素值为x的结点，删去以它为根的子树，并释放相应的空间。

算法思想：删除值为x的结点，意味着应将其父结点的左(右)子女指针置空，用层次遍历易于找到某结点的父结点。本题要求删除树中每个元素值为x的结点的子树，因此要遍历一棵完整二叉树。

void DeleteXTree(BiTNode* &bt) //删除以bt为根的子树
{
	if (bt != NULL)
	{
		DeleteXTree(bt->lchild); //删除bt的左子树
		DeleteXTree(bt->rchild); //删除bt的右子树
		free(bt); //释放被删除结点所占的存储空间
	}
}

void Search(BiTNode* bt, ElemType x) //在二叉树中查找所有以x为元素值的结点，并删除以其为根的子树
{
	if (bt !=NULL)
	{
		if (bt->data == x) //若根结点为x，则删除整棵树
		{
			DeleteXTree(bt);
			exit(0);
		}
	}
	SqQueue* qu;
	InitQueue(qu);
	BiTNode* p;
	enQueue(qu, bt);
	while (!EmptyQueue(qu)) 
	{
		deQueue(qu, p);
		if (p->lchild != NULL) //若左子女非空
		{
			if (p->lchild->data == x) //左子女符合，则删除左子树
			{
				DeleteXTree(p->lchild);
				p->lchild = NULL; //父节点的左子女置空
			}
			else enQueue(qu, p->lchild); //左子女入队列
		}
		if (p->rchild != NULL) //若右子女非空
		{
			if (p->rchild->data == x) //右子女符合，则删除左子树
			{
				DeleteXTree(p->rchild);
				p->rchild = NULL; //父节点的右子女置空
			}
			else enQueue(qu, p->rchild); //右子女入队列
		}
	}
}

删除以元素值x为根的子树，只要能删除其左、右子树，就可以释放值为x的根结点，因此宜采用后序遍历。

8. 设一棵二叉树的结点结构为( LLINK，INFO，RLINK)，ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写算法ANCESTOR(ROOT,p,q,r)，找到p和q的最近公共祖先结点r。

后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。本题要找p和q的最近公共祖先结点r，不失一般性，设p在q的左边。

算法思想：采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。先将栈复制到另一辅助栈中，继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配(即相等)的元素就是结点p和q的最近公共祖先算法实现如下：

typedef struct
{
	BiTNode t;
	int tag; //tag=0表示左子女已被访问，tag=1表示右子女已被访问
}stack;
stack s[], s1[]; //栈，容量足够大
BiTNode* Ancestor(BiTNode* ROOT, BiTNode* p, BiTNode* q, BiTNode* &r) //求二叉树中p和q指向结点的最近公共祖先结点r
{
	top = 0;
	bt = ROOT;
	while(bt!=NULL||top>0)
		while (bt != NULL)
		{
			s[++top].t = bt;
			s[top].tag = 0;
			bt = bt.lchild;
		} //沿左分支向下
	while (top != 0 && s[top].tag == 1)
	{ //假定p在q的左侧，遇到p时，栈中元素均为p的祖先
		if (s[top].t == p)
		{
			for (i = 1; i <= top; i++)
			{
				s1[i] = s[i];
				top1 = top;
			} //将栈s的元素转入辅助栈s1保存
			if(s[top].t==q) //找到q结点
				for (i = top; i > 0; i--) //将栈中元素的树结点到s1中去匹配
				{
					for (j = top1; j > 0; j--)
						if (s1[j].t == s[i].t) r = s[i].t;
					return true; //p和q的最近公共祖先已找到
				}
			top--; //退栈
		}
		if (top != 0)
		{
			s[top].tag = 1;
			bt = s[top].t->lchild;
		} //沿右分支向下遍历
	}
	return false; //p和q无公共祖先
}

9. 设有一棵满二叉树(所有结点值均不同)，已知其先序序列为pre，求其后序序列post。

算法思想：对一般二叉树，仅根据先序或后序序列，不能确定另一个遍历序列。但对满二叉树，任意一个结点的左、右子树均含有相等的结点数，同时，先序序列的第一个结点作为后序序列的最后一个结点，由此得到将先序序列pre[f1…r1]转换为后序序列post[f2…r2]的递归模型如下：
$f(pre,f1,r1,post,f2,r2)≡\begin{cases} 不做任何事情\;\;\;\;r1<f1时 \\ post[r2]=pre[f1]\;\;\;\;其他情况 \\ \end{cases}$

void PretoPost(ElemType pre[], int f1, int r1, ElemType post[], int f2, int r2)
//f1是先序序列中的第一个元素，r1是先序序列中的最后一个元素;
//f2是中序序列中的第一个元素，r2是中序序列中的最后一个元素
{
	int mid;
	if (r1 >= f1)
	{
		post[r2] = pre[f1];
		mid = (r1 - f1) / 2;
		PretoPost(pre, f1 + 1, f1 + mid, post, f2, f2 + mid - 1); //转换左子树
		PretoPost(pre, f1 + mid + 1, r1, post, f2 + mid, r2 - 1); //转换右子树
	}
}

运行结果

10. 将二叉树的叶结点按从左到右的顺序连成一个单链表，表头指针为head，二叉树按二叉链表方式存储，链接时用叶结点的右指针域来存放单链表指针。

方法一

算法思想：设置前驱结点指针pre，初始为空。第一个叶结点由指针head指向，遍历到叶结点时，就将它前驱的rchild指针指向它，最后一个叶结点的rchild为空。

LinkedList head,  pre=NULL; //全局变量
void visit(BiTree b)
{
	if (b->lchild == NULL && b->rchild == NULL) //叶结点
		if (pre == NULL)
		{
			head = b;
			pre = b;
		}
		else //处理第一个叶结点
		{
			pre->rchild = b;
			pre = b;
		} //将叶结点链入表尾
}

LinkedList Preorder(BiTree b) //使用先序遍历
{
	if (b != NULL)
	{
		visit(b);
		Preorder(b->lchild); //中序遍历左子树
		Preorder(b->rchild); //中序遍历右子树
		pre->rchild = NULL; //设置链表尾
	}
	return head;
}

LinkedList Inorder(BiTree b) //使用中序遍历
{
	if (b != NULL)
	{
		Inorder(b->lchild); //中序遍历左子树
		visit(b);
		Inorder(b->rchild); //中序遍历右子树
		pre->rchild = NULL; //设置链表尾
	}
	return head;
}

LinkedList Postorder(BiTree b) //使用后序遍历
{
	if (b != NULL)
	{
		Postorder(b->lchild); //中序遍历左子树
		Postorder(b->rchild); //中序遍历右子树
		visit(b);
		pre->rchild = NULL; //设置链表尾
	}
	return head;
}

方法二

算法思想：设置一个队列，遇到叶结点时将它的指针入队，等遍历结束后，所有的叶结点指针都存放于队列中，依次出队列，head和pre指向第一个叶结点，此后pre.rchild指向队列中的下一个。当队列为空时，最后使链表的表尾变为NULL。

LinkedList head, pre = NULL; //全局变量

LinkedList Preorder(BiTree b)
{
	Node* p;
	SqQueue* qu;
	InitQueue(qu);
	if (b != NULL)
	{
		if (b->lchild == NULL && b->rchild == NULL) enQueue(qu, b); //叶结点
		Preorder(b->lchild); //中序遍历左子树
		Preorder(b->rchild); //中序遍历右子树
		while (!EmptyQueue(qu))
		{
			if (pre == NULL)
			{
				deQueue(qu, p);
				head = p;
				pre = p;
			}
			else //处理第一个叶结点
			{
				deQueue(qu, p);
				pre->rchild = p;
				pre = p;
			} //将叶结点链入表尾
		}
		pre->rchild = NULL; //设置链表尾
	}
	return head;
}

运行结果

11. 判断两棵二叉树是否相似的算法。所谓二叉树T₁和T₂相似，指的是T₁和T₂都是空的二叉树或都只有一个根结点；或T₁的左子树和T₂的左子树是相似的，且T₁的右子树和T₂的右子树是相似的。

算法思想：采用递归的思想求解，若T₁和T₂都是空树，则相似；若有一个为空另一个不空，则必然不相似；否则递归地比较它们的左、右子树是否相似。递归函数的定义如下:
$f(T₁,T_2)≡\begin{cases} 1\;\;\;\;若T₁==T₂==NULL \\ 0\;\;\;\;若T₁和T₂之一为NULL，另一个不为NULL \\ f(T₁->lchild，T₂->lchild)\&\&f(T₁->rchild，T₂->rchild)\;\;\;\;T₁和T₂均不为NULL \\ \end{cases}$

bool Similar(BiTNode* T1, BiTNode* T2)
{
	bool leftS, rightS;
	if (T1 == NULL && T2 == NULL) return true; //两树皆空
	else if (T1 == NULL || T2 == NULL) return false; //只有一树为空
	else //递归判断
	{
		leftS = Similar(T1->lchild, T2->lchild);
		rightS = Similar(T1->rchild, T2->rchild);
		return leftS && rightS;
	}
}

12. 写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法。

算法思想：在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点p左、右子女均无，设其中序左线索指向某祖先结点f(p是f右子树中按中序遍历的第一个结点)，若f有左子女，则其左子女是结点p在后序下的前驱；若f无左子女，则顺其前驱找双亲的双亲，一直找到双亲有左子女(这时左子女是p的前驱)。还有一种情况，若p是中序遍历的第一个结点，则结点p在中序和后序下均无前驱。

ThreadNode* InPostPre(ThreadNode* t, ThreadNode* p)
{
	ThreadNode* q;
	if (p->rtag == 0) q = p->rchild; //若p有右子女，则右子女是其后序前驱
	else if (p->ltag == 0) q = p->lchild; //若p只有左子女，则左子女是其后序前驱
	else if (p->lchild == NULL) q = NULL; //p是中序序列第一个结点，无后序前驱
	else
	{
		while (p->ltag == 1 && p->lchild != NULL) p = p->lchild; //顺左线索向上找p的祖先，若存在，再找祖先的左子女
		if (p->ltag == 0) q = p->lchild; //p结点的祖先的左子女是其后序前驱
		else q = NULL; //仅有单支树(p是叶子)，已到根结点，p无后序前驱
	}
	return q;
}