二叉树的二叉链表表示.doc

=实习报告二“二叉树的二叉链表表示”演示程序 =（1） 、程序的功能和特点1. 程序功能：利用链表对非线性二叉树进行存储表示和访问。能够创建二叉树，并且能够按前序遍历显示输出所创建的二叉树。2. 程序特点：采用java面向对象语言，对二叉树用二叉链表用类进行封装。能够创建二叉树，并且能够按前序遍历显示输出所创建的二叉树。（2） 、程序的算法设计算法一：“按前序遍历方式建立二叉树”算法：1. 【逻辑结构与存储结构设计】 逻辑结构：非线性结构。 存储结构：链式存储结构。头指针bt 头结点指针btaacbcbfedfedgg (a) 带头指针的二叉链表 (b) 带头结点的二叉链表 链式 二叉树的二叉链表表示示意图开始创建2. 【基本操作设计】键盘输入二叉树的二叉链的数据if ( item != refvalue ) y n封闭叶子结点创建二叉链表结点 递归生成左右子树创建成功返回二叉树的头指针创建结束3. 【算法设计】 创建二叉链表文字说明： （1）.首先按前序输入二叉树。 （2）.判断是否是封闭结点的标识，如果不是则创建二叉链表，递归生成其左右子树。 （3）.如果是封闭结点标识则结束; （4）.插入成功返回二叉链表的头指针。4. 【高级语言代码】/按前序遍历方式建立二叉树public bintreenode preordercreate ( bintreenode p ) double item=0.0;system.out.println(按照前序遍历次序每次输入一个结点值。);try /* 键盘接受一个double数 */ bufferedreader br=new bufferedreader( new inputstreamreader(system.in) ); item=double.parsedouble(br.readline(); catch(ioexception e) if ( item != refvalue ) /读入的不是参照值p=new bintreenode(item);p.leftchild=preordercreate(p.leftchild); /递归生成左子树p.rightchild=preordercreate(p.rightchild); /递归生成右子树/实参是空二叉树,得到返回的子二叉树else /读入的是参照数p=null; /封闭叶子结点return p; /返回二叉树p 算法二：“按前序遍历方式输出二叉树”算法：1. 【逻辑结构与存储结构设计】 逻辑结构：非线性结构。 存储结构：链式存储结构。leftchilddatarightchild结构如图所示：开始输出2. 【基本操作设计】判断链表是否为空？ y n输出该节点的数据输出该节点的数据递归输出其左，右子树输出结束3.【算法设计】 文字说明： （1）.首先取链表元素判断链表是否为空。 （2）.链表非空先输出该结点的值，在递归调用该方法输出其左右子树。 （3）.链表为空则结束，结束退出。4.【高级语言代码】/按前序遍历方式输出二叉树public void preordertraverse (bintreenode p) if ( p != null ) /输出根结点数据域 system.out.print( +p.getdata();/递归输出p的左子树 preordertraverse ( p.leftchild );/递归输出p的右子树 preordertraverse (p.rightchild );（三）、程序中类的设计 “bintreenode”类：1. 【逻辑结构与存储结构】 逻辑结构：非线性结构。 存储结构：链式存储结构。二叉链表也可以带头结点的方式存放，如图(b)所示。头指针bt 头结点指针btaacbcbfedfedgg (a) 带头指针的二叉链表 (b) 带头结点的二叉链表 链式 二叉树的二叉链表表示示意图2. 【主要成员变量说明】 主要成员变量有：data：为结点的数据域，为double类型变量。用于存放节点的数据。leftchild，rightchild：为节点的指针域，为bintreenode类型变量，存放结点的指向下一个节点的指针。结构如图所示：leftchilddatarightchild3. 【主要成员方法说明】 public bintreenode ( double item)： 为bintreenode的构造函数：一个叶子结点 。参数为该结点的数据。 public bintreenode ( double item, bintreenode left,bintreenode right)：构造函数：非一个叶子结点。含有三个参数，分别为该结点的数据，左子树和右子树。public double getdata()：返回数据域的值。4.【高级语言代码】 / /定义“二叉链表结点”类class bintreenode private double data; /结点数据域bintreenode leftchild; /结点左右指针域bintreenode rightchild;/构造函数：一个叶子结点public bintreenode ( double item) data=item; /左右指针域自动为null/构造函数：一个非叶子结点public bintreenode ( double item, bintreenode left,bintreenode right) data=item;leftchild=left;rightchild=right;/返回结点数据域的值public double getdata() return data; /定义“二叉链表结点”类完毕 “cbinarytree”类：1. 【逻辑结构与存储结构】 逻辑结构：非线性结构。 存储结构：链式存储结构。二叉链表可以有不带头结点（a）和带都结点（b）。头指针bt 头结点指针btaacbcbfedfedgg (a) 带头指针的二叉链表 (b) 带头结点的二叉链表 2. 【主要成员变量说明】 主要成员变量为：root：表示根节点，为bintreenode类型。refvalue：参照值为double类型。3. 【主要成员方法说明】 public cbinarytree ( double v)：构造函数：建立一棵空树，并设定参照值。 public void createbintree() ：以root为根建立二叉树。 public bintreenode preordercreate ( bintreenode p,string s) ：按前序遍历方式建立二叉树。public bintreenode getroot()：得到二叉树的根。public void preordertraverse (bintreenode p)：前序遍历方式输出二叉树。public static void main(string args) ：主函数。 4.【高级语言代码】 /*定义“二叉链表”类*public class cbinarytree private bintreenode root; /根节点private double refvalue; /参照值：在建立二叉树之前，/给定一个结点数据域中不可能出现的数，/用来标记二叉树的一条分支到此封闭。/构造函数：建立一棵空树，并设定参照值public cbinarytree ( double v) refvalue=v;root=null;/以root为根建立二叉树public void createbintree()root=preordercreate(root); /实参是空二叉树/根root得到返回的二叉树根节点/按前序遍历方式建立二叉树public bintreenode preordercreate ( bintreenode p ) double item=0.0;system.out.println(按照前序遍历次序每次输入一个结点值。);try /* 键盘接受一个double数 */ bufferedreader br=new bufferedreader( new inputstreamreader(system.in) ); item=double.parsedouble(br.readline(); catch(ioexception e) if ( item != refvalue ) /读入的不是参照值p=new bintreenode(item);p.leftchild=preordercreate(p.leftchild); /递归生成左子树p.rightchild=preordercreate(p.rightchild); /递归生成右子树/实参是空二叉树,得到返回的子二叉树else /读入的是参照数p=null; /封闭叶子结点return p; /返回二叉树p/输出以root为根的二叉树public void outputbintree()preordertraverse(root);/按前序遍历方式输出二叉树public void preordertraverse (bintreenode p) if ( p != null ) /输出根结点数据域 system.out.print( +p.getdata();/递归输出p的左子树 preordertraverse ( p.leftchild );/递归输