一,实验题目。
试写一算法判别给定的二叉树是否为二叉排序树,设此二叉树以二叉链表存储,且树中结点的关键字均不相同。
二,问题分析。
本程序要求判别一个以二叉链表存储且树中结点的关键字均不相同的给定的二叉树是否为二叉排序树,完成这些操作需要解决的关键问题是:以二叉链表的存储形式输入一个二叉树。用一个函数实现判断是否为二叉排序树的功能。
1, 数据的输入形式和输入值的范围:输入的二叉树元素为字符型,注意不能输入空格键和回车键,会出现错误,因为它们也是一个字符。
2, 结果的输出形式:输出的是中序遍历后的二叉树元素。
3, 测试数据:(1)输入的队列元素为:6 4 8 9 @ 2 #
2)输入的队列元素为:5 4 7 1 @ 6 9 #
三,概要设计。
1)为了实现上述程序的功能,需要:
a,建立一颗二叉树。
b,中序遍历输出该二叉树。
c,判断该二叉树是否为二叉排序树。
2)本程序包含4个函数:
a,主函数main()
b,建立二叉树函数creatree()
c,中序遍历输出二叉树函数inorder()
d,判断二叉树是否为二叉排序树函数:panduan()
各函数间关系如右图所示:
四,详细设计。
1)结点类型定义:
typedef struct node
rear++;q[rear]=s;
if(rear==1) t=s
elsescanf("%c",&ch);}return t;}
3)中序遍历输出二叉树函数伪**:
void inorder(bitree *t)}
4)判断二叉树是否为二叉排序树函数伪**:
int panduan(bitree *p)
return x
五,源**。
#include ""
#include ""
#define maxsize 100
#define null 0
typedef struct node
rear++;
q[rear]=s; /将虚结点指针null或新节点地址入队。
if(rear==1)
t=s输入的第一个结点为新结点。
elsescanf("%c",&ch);
return t;
int panduan(bitree *p) /判断二叉树是否为二叉排序树函数。
int x=0; /定义并初始化x
if(p)return x; /返回x值。
void inorder(bitree *t) /中序遍历输出二叉树。
if(t)void main()
else if(x==0)
printf("");
六,调试分析。
递归判断左孩子并将结果与x进行或运算:x=x||panduan(p->lchild) 和递归判断右孩子并将结果与x进行或运算:x=x||panduan(p->rchild)时出错。
判断是否为排序二叉树的条件弄错。
七,使用手册。
用户在使用时,根据界面提示,首先输入一系列字符型二叉树元素,当输入‘#’时,二叉树元素输入结束。此时,则会输出中序遍历二叉树的结果和该二叉树是否为二叉排序树。注意,在输入时,@表示空结点,当输入空格键或回车键时,也是一个二叉树元素,用户需特别注意。
八,测试结果。
数据结构实验二叉树
下列程序中的统计二叉树结点的函数,是对二叉树遍历方法的应用,请认真理解然后模仿练习。二叉树的建立与遍历 include include typedef int etype typedef struct bitnode 树结点结构体 bitnode 函数原形声明 bitnode creat bt1 b...
数据结构练习4 二叉树
一 选择题。1 按照二叉树定义,具有3个结点的二叉树共有 c 种形态。a 3 b 4 c 5d 6 2 具有五层结点的完全二叉树至少有 d 个结点。a 9 b 15 c 31 d 16 3 以下有关二叉树的说法正确的是 b a 二叉树的度为2b 一棵二叉树的度可以小于2 c 至少有一个结点的度为2 ...
数据结构实验八内部排序
1 掌握内部排序的基本算法 2 分析比较内部排序算法的效率。1.运行下面程序 include include define max 50 int slist max 待排序序列 void insertsort int list,int n void createlist int list,int n...