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

====实习报告二“二叉树的二叉链表表示”演示程序 ==== 、程序的功能和特点 1. 程序功能：利用链表对非线性二叉树进行存储表示和访问。能够创建二叉树，并且能够按前序遍历显示输出所创建的二叉树。 2. 程序特点：采用java面向对象语言，对二叉树用二叉链表用类进行封装。能够创建二叉树，并且能够按前序遍历显示输出所创建的二叉树。 、程序的算法设计 算法一：“按前序遍历方式建立二叉树”算法： 【逻辑结构与存储结构设计】 逻辑结构：非线性结构。 存储结构：链式存储结构。 头指针bt 头结点指针bt AA A A C∧BC∧B C ∧ B C ∧ B ∧F∧∧E∧D∧∧F∧∧E∧D∧ ∧ F ∧ ∧ E ∧ D ∧ ∧ F ∧ ∧ E ∧ D ∧ ∧G∧∧G∧ ∧ G ∧ ∧ G ∧ (a) 带头指针的二叉链表 (b) 带头结点的二叉链表 链式 二叉树的二叉链表表示示意图 开始创建【基本操作设计】 开始创建 键盘输入二叉树的二叉链的数据 键盘输入二叉树的二叉链的数据 if if ( item != RefValue ) Y N 封闭叶子结点创建二叉链表结点 封闭叶子结点 创建二叉链表结点 递归生成左右子树 递归生成左右子树 创建成功返回二叉树的头指针 创建成功返回二叉树的头指针 创建结束 创建结束 【算法设计】 创建二叉链表文字说明： （1）.首先按前序输入二叉树。 （2）.判断是否是封闭结点的标识，如果不是则创建二叉链表，递归生成其左右子树。 （3）.如果是封闭结点标识则结束; （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 } } 算法二：“按前序遍历方式输出二叉树”算法： 【逻辑结构与存储结构设计】 逻辑结构：非线性结构。 存储结构：链式存储结构。 leftChild data rightChild 结构如图所示： 开始输出 开始输出 【基本操作设计】 判断链表是否为空？ 判断链表是否为空？ Y N 输出该节点的数据 输出该节点的数据 输出该节点的数据 输出该节点的数据 递归输出其左，右子树 递归输出其左，右子树 输出结束 输出结束 3.【算法设计】 文字说明： （1）.首先取链表元素判断链表是否为空。 （2）.链表非空先输出该结点的值，在递归调用该方法输出其左右子树。 （3）.链表为空则结束，结束退出。 4.【高级语言代码】 //按前序遍历方式输出二叉树 public void preOrderTraverse (BinTreeNode p) { if ( p != null ) { //输出根结点数据域 System.out.print( +p.GetData()); //递归输出p的左子树 preOrderTraverse ( p.lef