假设二叉树以二叉链存储,设计一个算法,判断一棵二叉树是否为完全二叉树。
解:根据完全二叉树的定义,对完全二叉树按照从上到下、从左到右的次序遍历(层次遍历)应该满足:
(1)某结点没有左孩子,则一定无右孩子;
(2)若某结点缺左或右孩子,则其所有后继一定无孩子。
若不满足上述任何一条,均不为完全二叉树。对应的算法如下:
int CompBTNode(BTNode *b)
{ BTNode *Qu[MaxSize],*p; //定义一个队列,用于分层判断
int first=0,rear=0; //顺序队首尾指针
int cm=1; //cm=1表示二叉树为完全二叉树
int bj=1; //bj=1表示到目前为止所有结点均有左右孩子
if (b!=NULL)
{ rear++;
Qu[rear]=b;
while (first!=rear) //队列不空
{ first++; //出队
p=Qu[first];
if (p->lchild==NULL) //*p结点没有左孩子
{ bj=0;
if (p->rchild!=NULL)//没有左孩子但有右孩子, 违反(1),
cm=0;
}
else //*p结点有左孩子
{ if (bj==1) //迄今为止,所有结点均有左右孩子
{ rear++; //左孩子进队
Qu[rear]=p->lchild;
if (p->rchild==NULL)//*p有左孩子但没有右孩子,则 bj=0
bj=0;
else //*p有右孩子,则继续判断
{ rear++; //右孩子进队
Qu[rear]=p->rchild;
}
}
else //bj=0: 迄今为止,已有结点缺左或右孩子
cm=0 //此时*p结点有左孩子,违反(2)
}
} //while
return cm;
}
return 1; //空树当成特殊的完全二叉树
相关推荐
写一算法,判断一棵二叉树是否是一棵二叉排序树。
设一棵二叉树以二叉链表表示,试编写有关二叉树的递归算法
以二叉链表作存储结构,设计求二叉树高度的算法。
编写按层次顺序(同一层自左至右)遍历二叉树的算法。 (1)二叉树采用二叉链表作为存储结构。 (2)按题集p44面题6.69所指定的格式输出建立的二叉树。 (3)输出层次遍历结果。 (4)测试用例自己设计。
判别给定二叉树是否为二叉排序树
编写算法判别给定二叉树是否为完全二叉树,经过层次遍历依次搜索每一层
算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树 算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树 算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树 算法面试通关40讲完整课件 18-20 树、...
编写算法判别给定二叉树是否为完全二叉树。
二叉树按照二叉链表方式存储,编写算法,将二叉树左右子树进行交换。实现建立二叉树,输出未交换前的中序遍历序列、交换左右子树、输出交换后的中序序列功能。
在二叉树类binarytree中增加一个功能,判断是否为完全二叉树(使用自定义的队列类完成)
(1)输入字符序列,建立二叉链表。...(6)对于树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间。 (8)借助队列实现二叉树的层次遍历。 (9)在主函数中设计一个简单的菜单,分别调试上述算法。
二叉树采用二叉链表结构表示。设计并实现如下算法:输入某棵二叉树的广义表形式,建立该二叉树,并按层次遍历该二叉树
设二叉树采用二叉链表存储结构,结点数据域...实验目的:深入理解二叉树(二叉链表)存储结构,综合运用学过的程序语言和算法知识,通过选择适当的辅助存储结构完成算法设计、编码与调试,解决课堂和教材未讲过的问题。
建立二叉树,实现二叉树的先序、中序、后序的递归遍历算法,输出遍历结果。 实现二叉树的先序、中序、后序和层次遍历的非递归算法,输出遍历结果。
1、 定义链接存储的二叉树类。 2、 实验验证如下算法的正确性、各种功能及指标: 1) 创建一棵二叉树,并对其初始化; 2)先根、中根、后根遍历二叉树;...判别给定二叉树是否为完全二叉树。两个要求写了一份代码
里面是关于完全二叉树的判定方法,有两种方法,一种是用队列,另外一种是联想到堆排序算法,堆也是一种完全二叉树,也是一种简单算法,其实两者本质区别不大,只是实现方式略有区别。
二叉树的建立和遍历算法 数据结构课程设计用
拟定出合适的二叉树的输入形式; 构造出相应的求共同祖先的算法; 能够以直观的形式观察到所建立的二叉树; 采用Microsoft Visual C++ 6.0 编译环境进行调试运行。
(3)请设计一个算法,要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表,表头指针为head。 二叉树按二叉链表方式存储,链接时用叶子结点的右指针域来存放单链表指针。请遍历该链表输出所有叶子结点,...