判定其是否为完全二叉树

2024-06-04

判定其是否为完全二叉树（共3篇）

判定其是否为完全二叉树篇1

数据结构与算法课程设计报告

课程设计题目：二叉树平衡的判定

专业班级：信息与计算科学1001班姓名：谢炜学号：100701114 设计室号：理学院机房设计时间： 2011-12-26 批阅时间：指导教师：杜洪波成绩：

一、摘要：

基于我们对C语言和数据结构的学习我们有能力编写处理一些比较基本而又简单的问题。在我们此题我们的目标就是任意给出一个二叉树我们判断是否为平衡的二叉树。

我们在学习计算机语言类的知识时当然要注重理论知识的学习，但是我们要明确我们学习的是计算机语言，由于课程的性质就决定了我们必须将我们在课本中学到的知识在计算机上运行并且自己能编写一些比较简单的程序，这才是我们学习计算机语言的最终目的而不是满足于理解一个理论会算一个题。因而我们将要抓住这样一个锻炼的机会

所谓平衡二叉树，它或者是一颗空树或者是具有下列性质的二叉树：它的左右子树都是平衡二叉树，且左右子树的深度之差得绝对值不超过1。

在我们这个判定任意给定的二叉树的题中。我们处理这道题的主要的思路是：首先按先序和中序或者按中序和后序的方式将我们所要判断的二叉树输入进入，目的是要得到一个明确的二叉树的结构准确的判断二叉树是否平衡。在我们判断二叉树的平衡中我们将分别考虑二叉树左右子树的是不是为平衡二叉树，依次得到左右子树的深度，判断左右子树的平衡性。

在我们的设计思路中我们将用到不同的树的遍历方式。

二、问题重叙：

平衡二叉树的判断，设计要求给定一个先序或者后序的遍历结果，判断其是否为二叉树。问题分析：

在处理二叉树平衡的判断的问题中。我们需要将分别考虑二叉树的左右子树的平衡问题只要左右子树确定为平衡二叉树，而且左右子树的深度的绝对值之差不大于1，那么我们得到的就是一颗平衡的二叉树。

我们将先通过前序和中序或者中序和后序将所要判断的二叉树输入。建立一个明确的二叉树在此基础上判断二叉树是否为平衡二叉树。

我们先建立一个二叉树并用前序和中序或者中序和后序遍历的方式将我们输入的树的元素输入得到一个明确的树的结构。

三、流程图如下：

四、模块分析：

1、定义一个结构体存储各节点的信息，并且用递归的方法存储左右子树的信息

typedef struct BINTREE { char

chData;struct BINTREE * pbLChild;struct BINTREE * pbRChild;} BinTree, * pBinTree;

2、分别得到树的深度以及左右子树的深度

int BT_GetTreeDepth(pBinTree pbTree){ //存储树总的深度

int iDepthTotal = 0;//存储左子树的深度

int iDepthLeft = 0;//存储右子树的深度

int iDepthRight = 0;

if(pbTree == NULL){

iDepthTotal = 0;} else {

// 左孩子的深度

iDepthLeft = BT_GetTreeDepth(pbTree->pbLChild);

// 右孩子的深度

iDepthRight = BT_GetTreeDepth(pbTree->pbRChild);

// 去左右孩子深度的最大值，1代表着根节点

iDepthTotal = 1 +(iDepthLeft > iDepthRight ? iDepthLeft : iDepthRight);} return iDepthTotal;}

3、判断左右子树是不是为平衡二叉树

bool BT_IsBalanceTree(pBinTree pbTree){ //如果树不是空的if(pbTree!= NULL){

//存储左孩子的深度

int iLeftDepth = 0;

//存储右孩子的深度

int iRightDepth = 0;

//得到左孩子的深度

iLeftDepth = BT_GetTreeDepth(pbTree->pbLChild);

//得到右孩子的深度

iRightDepth = BT_GetTreeDepth(pbTree->pbRChild);

//判断树是不是平衡二叉树

平衡二叉树的左右孩子的深度绝对值只差不大于

if((iLeftDepthiRightDepth <= 1))

{

// 判断左子树是不是平衡的

BT_IsBalanceTree(pbTree->pbLChild);

//判断右子树是不是平衡的

BT_IsBalanceTree(pbTree->pbRChild);

}

else

{

return false;

} } else {

return false;}

return true;}

4、输入各节点元素

bool BT_PreInToTree(pBinTree & pbTree, char * szInOrder, char * szPreOrder, int iInLeft, int iInRight, int iPreLeft, int iPreRight)

BT_PreInToTree(pbTree->pbLChild, szInOrder, szPreOrder, iInLeft, iCurPosiRightDepth >=-1)&&(iLeftDepthiInLeft;// If current position is greater than left, generate left child if(iCurPos > iInLeft){ BT_PreInToTree(pbTree->pbLChild, szInOrder, szPreOrder, iInLeft, iCurPosiInLeft;// If the current position is greater than the left border, generate the left child if(iCurPos > iInLeft){

BT_InPostToTree(pbTree->pbLChild, szInOrder, szPostOrder, iInLeft, iCurPos1);}

// If the current position is less than the right border, generate the right child if(iCurPos < iInRight){

BT_InPostToTree(pbTree->pbRChild, szInOrder, szPostOrder, iCurPos + 1, iInRight, iPostLeft + iLengthLeft, iPostRight-1);} return true;} void BT_PreOrder(pBinTree pbTree){ if(pbTree!= NULL){

// The preorder traversal is, root, left child, right child

printf(“%c ”, pbTree->chData);

BT_PreOrder(pbTree->pbLChild);

BT_PreOrder(pbTree->pbRChild);} } void BT_PostOrder(pBinTree pbTree){

if(pbTree!= NULL){

// The postorder traversal is, left child, right child, root

BT_PostOrder(pbTree->pbLChild);

BT_PostOrder(pbTree->pbRChild);

printf(“%c ”, pbTree->chData);} } void main(){ char szPre [100] = “";char szMid [100] = ”“;char szPost [100] = ”“;pBinTree pbPreInTree;pBinTree pbPostInTree;int

iMode = 0;printf(”请选择生成二叉树规则：前序和中序(0)，后序和中序(1)n“);scanf(”%d“,&iMode);switch(iMode){ case 0:

{

printf(”请输入前序序列:n“);

scanf(”%s“,&szPre);printf(”请输入中序序列:n“);

scanf(”%s“,&szMid);bool bCorrect = BT_PreInToTree(pbPreInTree, szMid, szPre, 0, strlen(szMid)-1, 0, strlen(szPre)-1);

if(bCorrect)

{printf(”该树的后序序列为：n“);

BT_PostOrder(pbPreInTree);

if(BT_IsBalanceTree(pbPreInTree))

{printf(”该树是平衡二叉树“);

}

else

{printf(”这个不是平衡二叉树“);

}

else

{printf(”不要乱输，前序与中序不匹配“);} }

break;case 1:

{printf(”请输入中序序列:n“);scanf(”%s“,&szMid);printf(”请输入后序序列:n“);scanf(”%s“,&szPost);bool bCorrect = BT_InPostToTree(pbPostInTree, szMid, szPost, 0, strlen(szMid)-1, 0, strlen(szPost)-1);

if(bCorrect)

{printf(”该树的前序序列为：n“);BT_PreOrder(pbPostInTree);

if(BT_IsBalanceTree(pbPostInTree))

{printf(”该树是平衡二叉树“);

}

else

{printf(”这个不是平衡二叉树“);

}

else

{printf(”不要乱输，中序与后序不匹配“);

} }

break;default:

{printf(”不要乱选，不支持其他模式");

} } }

实验8 二叉树的基本操作篇2

班级: 学号:

一、题目

由数字序列生成二叉树假设我们有这样的二叉树：

节点的元素(key)是正整数，且互不相同。可能给出这样一个虚拟的树更有利于理解输入。是的，我们的输入是上图的先序遍历；

即,要求根据1 3 0 2 0 0 4 5 0 0 0这样的输入，构造出一棵只含有正整数节点的二叉树。

【输入】

扩展的二叉树的先序遍历【输出】

构造的简单树的节点个数【样例输入】 3 0 2 0 0 4 5 0 0 0 【样例输出】

二、程序清单

三、程序调试过程中所出现的错误

四、运行结果（界面）：

计算机数据结构核心考点之二叉树篇3

遍历的过程就是把非线性结构的二叉树中的结点排成一个线性序列的过程。

二叉树遍历方法可分为两大类，一类是“宽度优先”法，即从根结点开始，由上到下，从左往右一层一层的遍历;另一类是“深度优先法”，即一棵子树一棵子树的遍历。

从二叉树结构的整体看，二叉树可以分为根结点，左子树和右子树三部分，只要遍历了这三部分，就算遍历了二叉树。设D表示根结点，L表示左子树，R表示右子树，则DLR的组合共有6种，即DLR，DRL，LDR，LRD，RDL，RLD。若限定先左后右，则只有DLR，LDR，LRD三种，分别称为先(前)序法(先根次序法)，中序法(中根次序法，对称法)，后序法(后根次序法)。三种遍历的递归算法如下：

1.先序法(DLR)

若二叉树为空，则空操作，否则：访问根结点，先序遍历左子树，先序遍历右子树。

2.中序法(LDR)

若二叉树为空，则空操作，否则：中序遍历左子树，访问根结点，中序遍历右子树.

3.后序法(LRD)

若二叉树为空，则空操作，否则：后序遍历左子树，后序遍历右子树，访问根结点。

▶完全二叉树中有关结点个数计算

完全二叉树的定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。

完全二叉树的叶子数为(n + 1) / 2取下整。

▶森林与二叉树之间的转换以及转换过程中结点之间的关系

将一棵树转换为二叉树的方法是：

1.树中所有相邻兄弟之间加一条连线。