二叉树的二叉链表表示

=实习报告二“二叉树的二叉链表表示”演示程序（一）、程序的功能和特点1. 程序功能：利用链表对非线性二叉树进行存储表示和访问。能够创建二叉树， 并且能够按前序遍历显示输出所创建的二叉树。2. 程序特点：采用java面向对象语言，对二叉树用二叉链表用类进行封装。能够创建二叉树，并且能够按前序遍历显示输出所创建的二叉树。（二）、程序的算法设计算法一：“按前序遍历方式建立二叉树”算法：1. 【逻辑结构与存储结构设计】逻辑结构：非线性结构。 存储结构：链式存储结构。链式二叉树的二叉链表表示示意图2. 【基本操作设计】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. 【逻辑结构与存储结构设计】逻辑结构：非线性结构。 存储结构：链式存储结构。2.【基本操作设结构如图所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)所示。链式二叉树的二叉链表表示示意图2. 【主要成员变量说明】主要成员变量有：data：为结点的数据域，为double类型变量。用于存放节点的数据。leftChild, rightChild：为节点的指针域，为BinTreeNode类型变量, 存放结点的指向下一个节点的指针。结构如图所示：leftChilddatarightChild3. 【主要成员方法说明】public BinTreeNode ( double item): 为 BinTreeNode 的构造函数：一个 叶子结点。参数为该结点的数据。public BinTreeNode ( double item, BinTreeNode left,BinTreeNode right): 构造函数：非一个叶子结点。含有三个参数，分别为该结点的数据，左子树和右 子树。public double Get Da ta():返回数据域的值。4. 【高级语言代码】/ /定义“二叉链表结点”类class BinTreeNode privatedouble 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;/返回结点数据域的值publicdouble GetData() returndata; /定义“二叉链表结点”类完毕“cBinaryTree ”类：1.【逻辑结构与存储结构】 逻辑结构：非线性结构。 存储结构：链式存储结构。二叉链表可以有不带头结点(a)和带都结点(b)。(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 Ge tRoo t()：得到二叉树的根。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;/以roo t为根建立二叉树public void CreateBinTree()root=preOrderCreate(root); /实参是空二叉树/根roo t得到返回的二叉树根节点 /按前序遍历方式建立二叉树 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/输出以roo t为根的二叉树public void OutputBinTree()preOrderTraverse(root);/按前序遍历方式输出二叉树public void preOrderTraverse (BinTreeNode p) if ( p != null ) /输出根结点数据域System.out.print(" "+p.GetData();/递归输出p的左子树 preOrderTraverse ( p.leftChild );/递归输出p的右子树preOrderTraverse (p.rightChild );/主函数public static void main(String args) /定义一棵二叉树，参照值为-1cBinaryTree s=new cBinaryTree(T.O);s.Crea teBinTree();s.O utput BinTreeO;/定义“二叉链表”类完毕(四) 程序的输入输出和运行结果截屏程序运行结果截屏：曰 Consol* 妄 I.'C<erminaced> cBirairyTre Java Application C:Program Filcsava'jre7binjavaw.tKe l'2019-4-19 卜午7;27;02按灵前序遍历次序每扶输入一个结启舉扌曰闘“序遍历氏存毎汝输入一7琵尸徨。2捋駁ti序诵円次韦m戈输入Y结孑直。3按照前序遍 历枕序每衣输入一个结点值.拎吳甸序m HfA韦至犧输入一个结口佰。3按瑕TT序遍丿力成子茅次输人一个茫戸按耐 序遍历咬序每衣输入一个结点值a9披灵前疗遍历次序每初输八-个结启So拽預利序遍历肚存零汝締人一i琵F徨.按按前序遍历谀序每衣输入一个结点值。詰照前序遍 历挨序每衣输入一个结点值匚拎用甸序诵E松年输川该二沪卅:1. D 2.0 3.0 8. 0 9.0