【数据结构周周练】007顺序结构实现完全二叉树操作- 求编号i与j最近公共祖先结点

港控/mmm° 2021-06-11 15:13 266阅读 0赞

树型结构是数据结构中学到的第一个一对多的结构，是非常重要的非线性结构，也是比较难的一个结构，由于一叉树是顺序表，三叉树比较复杂，最常用的是二叉树。从这次开始就带领大家走进树的世界。

**目录**

一、题目

二、代码实现

三、运行结果

--------------------

**注意：**

**1、树的相关术语也比较多，操作也比较多，在这里，我只写了该次练习所用到的操作及相近操作。后续的树的练习还会不断完善。**

**2、本次实现的树的代码与书上讲的代码差距比较大，完全根据自己对树的理论理解写的代码。**以树的顺序结构实现的定义为例，严蔚敏老师的书上的定义是：

#define MAX_TREE_SIZE 100
    
    int SqBiTree[MAX_TREE_SIZE]; //数据结构书中二叉树的定义

而我自己的定义是：

typedef struct {
    	int *treeBase;
    	int elemNum;
    	int treeSize;
    }SqBiTree;

如果大家有其他定义方式，希望大家能够积极评论。

# 一、题目 #

已知一棵顺序二叉树有20个数据，求编号分别为 i、j 的两个结点最近的公共祖先结点的编号及当前结点的值（结点赋值为编号值，但要通过结点获取）。

# 二、代码实现 #

#define MAX_TREE_SIZE 20
    
    #include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    //int SqBiTree[MAX_TREE_SIZE];//数据结构书中二叉树的定义
    
    typedef struct {
    	int *treeBase;
    	int elemNum;
    	int treeSize;
    }SqBiTree;
    
    int InitBiTree(SqBiTree &T) {
    	T.treeBase = (int *)malloc(MAX_TREE_SIZE * sizeof(SqBiTree));
    	if (!T.treeBase)
    	{
    		cout << "空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	T.elemNum = 0;
    	T.treeSize = MAX_TREE_SIZE;
    	return 1;
    }
    
    int CreatBiTree(SqBiTree &T,int e) {
    	if (T.elemNum == T.treeSize)
    	{
    		cout << "树已满" << endl;
    		exit(OVERFLOW);
    	}
    	T.treeBase[T.elemNum] = e;
    	T.elemNum++;
    	return 1;
    }
    
    int ParentNum(SqBiTree &T, int childNum) {
    	return (childNum -1) / 2;
    }
    
    int LChildNum(SqBiTree &T, int parentNum) {
    	return parentNum * 2 + 1;
    }
    
    int RChildNum(SqBiTree &T, int parentNum) {
    	return (parentNum + 1) * 2;
    }
    
    int ElemLayer(SqBiTree &T, int num) {
    	int layar = 0;
    	while (num)
    	{
    		num = (num - 1) / 2;
    		layar++;
    	}
    	return layar;
    }
    void main() {
    	int i = 7;
    	int j = 18;
    
    	SqBiTree T;
    	InitBiTree(T);
    	for (int k = 0; k < 20; k++)
    	{
    		CreatBiTree(T, k);
    	}
    
    	while (i != j)
    	{
    		if (ElemLayer(T, i)>ElemLayer(T, j))
    			i = ParentNum(T, i);
    		else if (ElemLayer(T, i)<ElemLayer(T, j))
    			j = ParentNum(T, j);
    		else
    		{
    			i = ParentNum(T, i);
    			j = ParentNum(T, j);
    		}
    	}
    	cout << "距离i 与 j 最近的公共祖先的编号是：" << i << endl;
            cout << "该编号对应的值为：" << T.treeBase[i] << endl;
    }

# 三、运行结果 #

![70][]

[70]: /images/20210516/d31796a7ff5a446182482e27667a2d78.png