1、学习情境5 树和二叉树学习情境学习情境5 5 树和二叉树树和二叉树5.1 任务一任务一 认识树认识树5.2 任务二任务二 二叉树二叉树5.3 任务三任务三 二叉树操作的程序实现二叉树操作的程序实现5.4 任务四任务四 哈夫曼哈夫曼(Huffman)树树学习情境5 树和二叉树现实生活中和软件设计中的许多关系表现为树的形式，如家族成员关系、一个单位的组成结构等。这些结构形势的共同特点是具有明显的层次特点，并且其中的每个数据最多只有一个前驱和若干个后继，因而可抽象表示为本学习情境的树状结构。与线性表不同，树结构是一种非线性结构。树结构中的各子结构与整个结构具有相似的特性，因而其算法可以采用递归形式或
2、非递归形式。本情境学习树结构的基本概念和术语，二叉树的基本概念、性质和存储结构，重点介绍二叉树的遍历这一基本算法及其图形界面操作实现，最后学习哈夫曼树编码及其程序实现。本学习情境是数据结构课程的重点之一，主要研究非线性的树结构及其应用，重点是二叉树的定义、性质、遍历方式、存储结构、非递归及递归算法实现。学习情境5 树和二叉树5.1 任务一任务一 认识树认识树5.1.1 子任务子任务1 树的基础知识树的基础知识1什么是树什么是树树是数据节点之间具有层次关系的非线性结构。在树结构中，除根以外的节点只有一个直接前驱节点，可以有零至多个直接后继节点。树结构从自然界中的树抽象而来，有树根、从根发源的类似
3、枝杈的分支关系和作为分支终点的叶子等。Windows操作系统的磁盘文件系统结构、生活中所见的家谱等，虽然表现形式各异，但都可以使用树结构处理，如图5-1及图5-2所示。学习情境5 树和二叉树图5-1 Windows磁盘文件结构 学习情境5 树和二叉树 图5-2 家族树结构 学习情境5 树和二叉树2定义树定义树(tree)树是由n(n0)个节点组成的有限集合，记为T，树中的数据通常称为节点。n=0的树称为空树；n0的树T：(1)有一个特殊的节点称为根(root)节点，它只有后继节点，没有前驱节点。(2)除根节点外的其他节点分为m(m0)个相互相交的集合T0,T1,Tm-1，其中每个集合Ti(0i
4、m)本身又是一棵树，称为根的子树(subtree)。如图5-3所示，树T有7个节点，A为树根，B为A的一棵子树，C为A的另一棵子树。学习情境5 树和二叉树图5-3 树T 学习情境5 树和二叉树上面树的定义是递归的。节点是树的基本单位，若干个节点组成一棵树，若干棵互不相交的子树组成一棵树。树中每个节点都是该树中某一棵树的根。因此，树是由节点组成的、节点之间具有层次关系的非线性结构。5.1.2 子任务子任务2 学习树的术语学习树的术语1空树空树没有任何节点的树称为空树，即T=null；只有1个节点的树，该节点就是树的根；一般情况下树具有n个节点。学习情境5 树和二叉树2父节点父节点(双亲双亲)、孩
5、子与兄弟节点、孩子与兄弟节点节点的前驱节点称为父节点或双亲节点(parent)，一棵树中，根节点没有双亲节点，其他节点有且仅有一个父节点(双亲节点)。节点的后继节点称为该节点的孩子节点(child)。如图5-3所示，根节点A没有双亲节点，A是B、C的双亲节点，B、C是A的孩子节点。拥有同一个双亲节点的多个节点之间称为兄弟(sibling)节点。如图5-3所示，B、C是兄弟，D、E是兄弟，F、G也是兄弟，但是E和F不是兄弟。学习情境5 树和二叉树节点的祖先(ancestor)是指从根节点到双亲节点所经过的所有节点。节点的后代(descendant)是指该节点的所有孩子节点，以及孩子的孩子等。如图
6、5-3所示，E的祖先是B和A，E是A和B的后代。3树的度树的度节点的度(degree)是节点所拥有子树的棵数。如图5-3所示，A的度是2，D和E的度是0。度为0的节点称为叶子节点(leaf)，又叫终端节点；树中除叶子节点之外的其他节点称为分支节点，又叫非叶节点或非终端节点。如图5-3所示，D、E、F和G是叶子节点，B、C是分支节点。树的度是指树中各节点度的最大值。学习情境5 树和二叉树4节点层次和树的高度节点层次和树的高度节点的层次(level)反映节点处于树中的层次位置。约定根节点的层次为1，其他节点的层次为其父母节点的层次加1。显然，兄弟的节点层次相同。如图5-3所示，A的层次为1，B的层
7、次为2，E的层次为3。E与F不是兄弟，称为同一层上的节点。树的高度(height)或深度(depth)是树中节点的最大层次数。如图5-3所示，树的高度为3。学习情境5 树和二叉树5边和路径边和路径设树中A节点是B节点的父节点，有序对(A，B)称为连接这两个节点的分支，也称为边(edge)。如图5-3所示，A、B节点之间的边是(A，B)。设(X0，X1，Xk-1)是由树中节点组成的一个序列，且(Xi,Xi+1)(0i0时，二叉树由一个根节点和两棵互不相交、分别称为左子树和右子树的子二叉树构成。二叉树定义也是递归的。在树中定义的度、层次等术语，同样适用于二叉树。二叉树的节点最多只有两棵树，所以二叉
8、树的度最多为2。二叉树的子树有左、右之分，即使只有一个子树也要区分是左子树还是右子树。学习情境5 树和二叉树2二叉树的基本形态二叉树的基本形态二叉树有五种基本形态(如图5-8所示)：(1)空二叉树，见图5-8(a)。(2)只有一个根节点的二叉树，见图5-8(b)。(3)由根节点、非空的左子树和空的右子树组成的二叉树，见图5-8(c)。(4)由根节点、空的左子树和非空的右子树组成的二叉树，见图5-8(d)。(5)由根节点、非空的左子树和非空的右子树组成的二叉树，见图5-8(e)。学习情境5 树和二叉树图5-8 二叉树五种基本形态 学习情境5 树和二叉树5.2.2 子任务子任务2 二叉树的基本性质
9、二叉树的基本性质二叉树的性质是二叉树的重要内容，理解二叉树的性质有助于相关内容的学习。下面介绍二叉树的5个性质，并给出证明。性质1：若根节点的层次为1，则二叉树第i层最多有2i-1(i1)个节点。证明：采用归纳法。(1)第一层是根，i=1，该层有唯一的节点(根)，故2i-1=20=1，命题成立；(2)设第i-1层最多有2i-1-1个节点，由于二叉树中每个节点的度最多为2，因此第i层最多有22i-2=2i-1个节点。性质2：在高度为k的二叉树中，最多有2k-1个节点(k0)。证明：由性质1可知，在高度为k的二叉树中，节点树最多为20+21+2k-1=2k-1。学习情境5 树和二叉树性质3：设一棵
10、二叉树的叶子节点数为n0，度为2的节点数为n2，则n0=n2+1。证明：设二叉树节点数为n，度为1的节点数为n1，则有n=n0+n1+n2因度为1的节点有1个孩子，度为2的节点有2个孩子，叶子节点没有孩子，根节点不是任何节点的子女，所以二叉树的节点总数又可表示为n=0n0+1n1+2n2+1综合上述两式，可得n0=n2+1。一棵高度为k的满二叉树(full binary tree)是具有2k-1(k0)个节点的二叉树。从定义可知，满二叉树中每一层的节点数目都达到最大值。对满二叉树的节点进行编号，如图5-9(a)所示。学习情境5 树和二叉树一棵具有n个节点、高度为k的二叉树，如果它的每个节点都与
11、高度为k的满二叉树中序号为0至n-1的节点一一对应，则称这棵二叉树为完全二叉树(complete binary tree)，如图5-9(b)所示。满二叉树是完全二叉树，而完全二叉树不一定是满二叉树。完全二叉树在第1至k-1层是满二叉树，第k层不满，并且该层所有节点都必须集中在该层左边的若干位置上。图5-9(c)则不是一棵完全二叉树。学习情境5 树和二叉树图5-9 满二叉树与完全二叉树学习情境5 树和二叉树性质4：一棵具有n个节点的完全二叉树，其高度k=int(lbn)+1。证明：由性质2和完全二叉树的定义可知，一棵有n个节点、高度为k的完全二叉树有2k-1-1n2k-1对不等式移项并求对数，有
12、k-1lb(n+1)k由于二叉树的高度k只能是整数，所以取k=int(lbn)+1。学习情境5 树和二叉树性质5：一棵具有n个节点的完全二叉树，对序号为i(01，则i的父母节点序号为int(i-1)/2)；(3)若2in，则i的左孩子节点序号为2i，否则i无左孩子；(4)若2i+1n，则i的右孩子节点序号为2i+1，否则i无右孩子。证明：在图5-9(b)中，i=1时为根节点1，其左孩子节点2的序号为2i-1=2，右孩子节点的序号为2i+1=3，其他类推。学习情境5 树和二叉树5.2.3 子任务子任务3 二叉树的存储结构二叉树的存储结构与线性结构类似，二叉数的存储结构也可采用顺序存储结构和链式存
13、储结构两种存储方式，下面讨论这两种存储方式。1顺序存储结构顺序存储结构在采用顺序结构存储二叉树时，不仅要能将节点的值存储起来，同时还要能体现节点间的关系，即父子关系及兄弟关系，否则便没有意义。如果简单地将所有节点的值“挤”在数组的前n个数据中，则不能体现出相互的关系。采用的存储方式是按完全二叉树的编号次序进行的，即编号为i的节点存储在数组中下标为i的数据中。这样，由性质5可知，其左孩子节点在数组中的数据的下标为2i，右孩子节点的下标为2i+1，其父节点的下标为int(i/2)。图5-3的树可以用图5-10所示的二叉数的顺序存储结构进行存储。学习情境5 树和二叉树图5-10 二叉数的顺序存储结构
14、 学习情境5 树和二叉树然而，这种方法存在一个问题：若二叉树不是完全二叉树形式，则为了保持节点之间的关系，不得不空出许多数据来，这就造成了空间的浪费。极端情况下，仅有n个节点的二叉树，却需要2n-1个数据存储空间，这显然是不能接受的。为此，要求存储结构还要能合理地利用空间，即依据实际节点数来分配存储空间。这就需要链式存储结构。2二叉树链式存储结构二叉树链式存储结构在二叉树链式存储结构中，每个节点应包括存储点值的数据部分及指向两个孩子的指针，可以设为data、lchild和rchild，其结构如图5-11(a)所示。学习情境5 树和二叉树图5-11 二叉数的链式存储结构 学习情境5 树和二叉树在
15、用这样的节点所构造的链表中，每个节点有两个指针，分别指向其左右孩子节点，因而称这样的链表为二叉链表。图5-11(b)为一棵二叉树及对应的二叉链表。对于一个二叉链表，如果给出其根指针，即可由此出发搜索到其余各节点，因此，常用根指针作为二叉链表的名称。二叉树(链表)的根指针为T，因而可称为二叉树T或二叉链表T。本学习情境的二叉树程序实现采用链式存储结构。学习情境5 树和二叉树3二叉树的遍历二叉树的遍历二叉树的遍历(traverse)是按照一定规则和次序访问二叉树中的所有节点，并且每个节点仅被访问一次。虽然二叉树是非线性结构，但对二叉树的一次遍历仍然是线性次序。(1)如图5-12(a)所示的3个数据
16、LDR，共有种排列DLR、LDR、LRD、RLD、RDL、DRL。观察上述序列可知，前三个序列与后三个序列的次序正好相反。前三个序列的共同特点是，L在R之前，即先遍历左子树，后遍历右子树。学习情境5 树和二叉树(2)二叉树的三种次序遍历规则。由于先遍历左子树还是右子树在算法设计上没有本质区别，因此一般都约定遍历子树的次序是先左后右，则二叉树的遍历有三种次序，分别称为先序遍历、中序遍历和后序遍历，也称为先根次序、中根次序和后根次序三种遍历。这三种遍历的顺序如下：先根次序：访问根节点，遍历左子树，遍历右子树。中根次序：遍历左子树，访问根节点，遍历右子树。后根次序：遍历左子树，遍历右子树，访问根节点
17、。学习情境5 树和二叉树图5-12 基本二叉树遍历 学习情境5 树和二叉树(3)图5-13是一个普通二叉树及其三种遍历结果。二叉树遍历运算是二叉树各种运算的基础。真正理解这一运算的实现及其含义有助于许多二叉树运算的实现及算法设计。其程序实现将在任务三中学习。学习情境5 树和二叉树图5-13 二叉树遍历结果 学习情境5 树和二叉树5.3 任务三任务三 二叉树操作的程序实现二叉树操作的程序实现二叉树存储有顺序存储结构和链式存储结构两种方式，程序实现也有多种。为了更直观地学习和领会二叉树，也进一步提升Java编程技能，本任务采用图形界面展示二叉树的实现结果。程序内容包括构建二叉树，递归算法和非递归算
18、法实现先序遍历、中序遍历和后序遍历三种遍历算法。Java程序实现的界面如图5-14所示。学习情境5 树和二叉树图5-14 二叉树操作程序实现界面 学习情境5 树和二叉树5.3.1 子任务子任务1 构造二叉树的程序实现框架构造二叉树的程序实现框架首先创建包，包名为ch5Tree。1构造二叉树节点的结构类构造二叉树节点的结构类因为采用链式存储结构来实现，所以二叉树的节点要包含存储数据data、左子树的指针lchild和右子树指针rchild。在包ch5Tree中创建类BiTreeNode.java，完整的程序代码如下：学习情境5 树和二叉树package ch5Tree;public class
19、BiTreeNode /二叉树节点 public String data;/二叉树节点的值 public BiTreeNode lchild;/二叉树的左孩子 public BiTreeNode rchild;/二叉树的右孩子学习情境5 树和二叉树2构造二叉树节点的图形类构造二叉树节点的图形类在包ch5Tree中创建类BiTreeNodeMap.java，完整的程序代码如下：package ch5Tree;public class BiTreeNodeMap /节点圆圈图 int x;/节点直角坐标x int y;/节点直角坐标y String data;/节点的数据学习情境5 树和二叉树3构
20、造二叉树实现代码框架构造二叉树实现代码框架在包ch5Tree中创建类BiTreeFrame.java，初步程序代码如下(注意：详细的程序实现将在“子任务2 二叉树算法的程序实现”中讲解)：package ch5Tree;import javax.swing.JFrame;public class BiTreeFrame extends JFrame/二叉树操作窗体类，继承JFrameclass BiTree_Panel extends JPanel /画二叉树的面板类，继承JPanel学习情境5 树和二叉树4构造主程序构造主程序在包ch5Tree中创建主程序类BiTreeMain.java，完
21、整的程序代码如下：package ch5Tree;import javax.swing.JFrame;public class BiTreeMain public static void main(String args)BiTreeFrame tree=new BiTreeFrame();/调用tree类 /退出应用程序，关闭窗口 tree.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);tree.setVisible(true);/启动可视化界面 学习情境5 树和二叉树至此可以编译运行主程序，如果没有错误，会出现一个空的界面窗口，只能点击关闭按
22、钮退出，因为还没有编写具体的组件和操作实现代码。接下来进入下一个子任务，即“子任务2 二叉树算法的程序实现”。5.3.2 子任务子任务2 二叉树算法的程序实现二叉树算法的程序实现二叉树的节点系列输入，二叉树的构造，二叉树的图形显示，二叉先序遍历、中序遍历和后序遍历的算法，以及结果显示，都是在BiTreeFrame.java中实现的，代码共有543行，对已经完成前几个学习情境的学习者而言，代码量属中等。为了帮助学习和理解，基本每行代码都进行注释，如果能参照代码自己完成，则学习数据结构的二叉树和Java程序编写技能必将有极大的提高。学习情境5 树和二叉树1二叉树程序画图实现的方法和操作步骤二叉树程
23、序画图实现的方法和操作步骤根据二叉树窗口中显示的内容，按照从上到下、从左到右的顺序实现各组件：(1)在创建过程中遇到需要导入318行代码时，可由系统自动导入，不必手工键入。(2)在类BiTree_Panel之中完成“画二叉树的面板”类的代码，详见472543行。(3)回到BiTreeFrame类中，后续所有操作都在BiTreeFrame类中编写代码。声明二叉树、创建二叉树节点，详见2223行。按操作界面从上到下的顺序声明各组件，详见2542行。学习情境5 树和二叉树(4)设置画二叉树面板的方法bitree_panel()，详见111119行。(5)设置输入文本框，详见121130行。(6)检查
24、输入二叉树节点系列的合法性check(String str)，详见297311行。(7)构建二叉树createBiTree(BiTreeNode tree,String str_tree)，详见313339行。(8)计算二叉树的深度，详见460469行。(9)设置“创建二叉树”按钮，详见177214行。(10)面板生成方法，装载各标签、文本框和按钮等，详见61109行。注意此时，三个遍历结果的文本框和三个遍历按钮还没构造，所以8388行要先注释或不要输入。学习情境5 树和二叉树(11)编写初始化界面方法initialize()和BiTreeFrame默认构造器，详见4559行。至此，二叉树的图
25、形显示已能正常工作，在输入文本框中输入二叉树的节点系列，如“abcdef”然后点击“构造二叉树”按钮，就可以看到生成一棵二叉树，见图5-15。学习情境5 树和二叉树图5-15 构造二叉树界面学习情境5 树和二叉树2遍历二叉树的实现方法和操作步骤遍历二叉树的实现方法和操作步骤在完成上述二叉树后，可以继续编写遍历生成的二叉树算法，并将遍历结果显示在相应的文本框中。(1)设置先序遍历结果文本框Jtf_preJOrder()，详见132145行。(2)编写先序遍历二叉树算法preOrder(BiTreeNode tree)，详见341367行。(3)编写“先序遍历”按钮Jbt_preOrder()及事
26、件处理代码，详见216241行。完成先序遍历的处理后，类似地，完成中序遍历和后序遍历，如图5-14下半部分所示。至此，二叉树操作程序实现全部完成。学习情境5 树和二叉树3二叉树二叉树BiTreeFrame.java完整代完整代001package ch5Tree;002003import java.awt.Color;004import java.awt.Font;005import java.awt.Graphics;006import java.awt.Graphics2D;007import javax.swing.BorderFactory;008import javax.swing.
27、JOptionPane;009import javax.swing.JPanel;010import javax.swing.JFrame;011import javax.swing.JTextField;012mport java.awt.Rectangle;学习情境5 树和二叉树013import java.awt.event.ActionEvent;014import java.awt.event.ActionListener;015import java.awt.geom.Ellipse2D;016import javax.swing.JButton;017import javax.s
28、wing.JLabel;018import javax.swing.border.EtchedBorder;019/二叉树操作窗体类020public class BiTreeFrame extends JFrame/二叉树操作窗体类，继承JFrame021022BiTreeNode tree=null;/声明二叉树023private BiTreeNode bitreenode=new BiTreeNode50;/创建二叉树节点024/以下18行，按操作界面从上到下的顺序，声明各组件025private JPanel jContentPanel=null;/声明容器面板,用于装载所有二叉树操
29、作组件026 private JLabel jlbl_in=null;/声明输入说明标签学习情境5 树和二叉树027private JTextField jtf_in=null;/声明输入文本框(二叉树数据)028private JButton jbt_create=null;/声明“构造二叉树”按钮029private String str_tree=ABCD#E;/声明二叉树的节点数据串，初始值用于启动时画树030int depth=3;/二叉树深度，初始二叉树ABCD#E的深度为3031private String str_order;/声明遍历结果字符串032/调用构建显示二叉树面板的
30、构造方法，画二叉树的图形033private BiTree_Panel bitree_panel=new BiTree_Panel(depth,str_tree);034private JLabel jlbl_preOrder=null;/声明“先序遍历结果”标签035private JLabel jlbl_inOrder=null;/声明“中序遍历结果”标签036private JLabel jlbl_postOrder=null;/声明“后序遍历结果”标签037private JTextField jtf_preOrder=null;/声明“先序遍历结果”文本框038private JTe
31、xtField jtf_inOrder=null;/声明“中序遍历结果”文本框039private JTextField jtf_postOrder=null;/声明“后序遍历结果”文本框040private JButton jbt_preOrder=null;/声明“先序遍历”按钮041private JButton jbt_inOrder=null;/声明“中序遍历”按钮042private JButton jbt_postOrder=null;/声明“后序遍历”按钮学习情境5 树和二叉树043044/默认构造器045public BiTreeFrame()046super();/调用父类
32、047initialize();/调用初始化界面048方法initialize()048jContentPanel.add(bitree_panel(),null);/加入画二叉树面板059 jContentPanel.repaint();/重画050 051052/初始化界面方法initialize()053private void initialize()054this.setSize(800,600);/设置操作窗体大小055/调用面板生成方法，并把面板显示在frame上056this.setContentPane(JContentPanel();057this.setTitle(树的可
33、视化);/设置操作窗体标题058this.setLocation(100,100);/设置操作窗体在屏幕中的位置坐标(x,y)学习情境5 树和二叉树059 060061/面板生成方法，装载各标签、文本框和按钮等062private JPanel JContentPanel()063if(jContentPanel=null)064/以下7行创建“输入说明标签”，并设置相应属性065jlbl_in=new JLabel();/创建输入说明标签066/设置标签在容器中的坐标、宽度和高度(x,y,宽,高)067jlbl_in.setBounds(new Rectangle(16,10,500,32)
34、;068/设置标签的字体风格、大小069jlbl_in.setFont(new Font(u5e7cu5706,Font.BOLD,14);070jlbl_in.setForeground(new Color(0,51,204);/设置标签的字体颜色071jlbl_in.setText(按层次输入树的节点:(提示：#表示空节点，072+如ABCD#E的树如下图所示);/设置标签显示的文字 学习情境5 树和二叉树073/以下5行创建“先序遍历结果”标签，与其类似，不一一注释074jlbl_preOrder=new JLabel();075jlbl_preOrder.setBounds(new R
35、ectangle(15,400,147,32);076jlbl_preOrder.setFont(new Font(u5e7cu5706,Font.BOLD,16);077jlbl_preOrder.setForeground(new Color(255,0,153);078jlbl_preOrder.setText(先序遍历结果:);079/以下5行创建“中序遍历结果”标签，与其类似，不一一注释080jlbl_inOrder=new JLabel();081jlbl_inOrder.setBounds(new Rectangle(15,450,147,32);082jlbl_inOrder.
36、setFont(new Font(u5e7cu5706,Font.BOLD,16);083jlbl_inOrder.setForeground(new Color(255,0,153);084jlbl_inOrder.setText(中序遍历结果:);085/以下5行创建“后序遍历结果”标签，与其类似，不一一注释086jlbl_postOrder=new JLabel();学习情境5 树和二叉树087jlbl_postOrder.setBounds(new Rectangle(15,500,147,32);088jlbl_postOrder.setFont(new Font(u5e7cu570
37、6,Font.BOLD,16);089jlbl_postOrder.setForeground(new Color(255,0,153);090jlbl_postOrder.setText(后序遍历结果:);091/以下2行，创建面板、设置布局管理器092jContentPanel=new JPanel();/创建面板093jContentPanel.setLayout(null);/设置布局管理器094/以下12行在面板中加入各标签、文本框和按钮095jContentPanel.add(jlbl_in,null);/加入输入提示说明标签096jContentPanel.add(Jtf_in(
38、),null);/加入输入文本框097jContentPanel.add(Jbt_create(),null);/加入创建按钮098jContentPanel.add(jlbl_preOrder,null);/加入“先序遍历结果”标签099jContentPanel.add(jlbl_inOrder,null);/加入“中序遍历结果”标签100jContentPanel.add(jlbl_postOrder,null);/加入“后序遍历结果”标签101jContentPanel.add(Jtf_preOrder(),null);/加入“先序遍历结果”文本框102jContentPanel.ad
39、d(Jtf_inOrder(),null);/加入“中序遍历结果”文本框学习情境5 树和二叉树103jContentPanel.add(Jtf_postOrder(),null);/加入“后序遍历结果”文本框104jContentPanel.add(Jbt_preOrder(),null);/加入“先序遍历结果”按钮105jContentPanel.add(Jbt_inOrder(),null);/加入“中序遍历结果”按钮106jContentPanel.add(Jbt_postOrder(),null);/加入“后序遍历结果”按钮107108return jContentPanel;1091
40、10111/设置画二叉树面板方法112private BiTree_Panel bitree_panel()113bitree_panel.depth=depth;/设置二叉树高度114bitree_panel.str_tree=str_tree;/设置二叉树的节点数据串，如果ABCD#E,#为空115/则设置画二叉树面板的位置及大小,边框设置116bitree_panel.setBounds(new Rectangle(15,96,750,280);117bitree_panel.setBorder(BorderFactory.createEtchedBorder(EtchedBorder.
41、RAISED);118return bitree_panel;学习情境5 树和二叉树119120121/设置输入文本框122private JTextField Jtf_in()123if(jtf_in=null)/如果文本框未创建124jtf_in=new JTextField();/则创建文本框125/设置文本框的位置、长度、高度；输入的文字风格大小126jtf_in.setBounds(new Rectangle(15,45,377,32);127jtf_in.setFont(new Font(宋体,Font.BOLD,24);128129return jtf_in;130131学习情境
42、5 树和二叉树132/设置先序遍历结果文本框133private JTextField Jtf_preOrder()134if(jtf_preOrder=null)/如果文本框未创建135 jtf_preOrder=new JTextField();/则创建文本框136 /设置文本框的位置、长度、高度；显示字体颜色；不可编辑；组件可见；背景/颜色，字体字号137 jtf_preOrder.setBounds(new Rectangle(164,400,330,32);138 jtf_preOrder.setForeground(Color.red);139 jtf_preOrder.setEd
43、itable(false);140 jtf_preOrder.setEnabled(true);141 jtf_preOrder.setBackground(Color.white);142 jtf_preOrder.setFont(new Font(Trebuchet MS,Font.BOLD,24);143 144 return jtf_preOrder;145146学习情境5 树和二叉树147/设置中序遍历结果文本框148private JTextField Jtf_inOrder()149if(jtf_inOrder=null)/如果文本框未创建150jtf_inOrder=new J
44、TextField();/创建文本框151/设置文本框的位置、长度、高度；显示字体颜色；不可编辑；组件可见；背景/颜色，字体字号152jtf_inOrder.setBounds(new Rectangle(164,450,330,32);153jtf_inOrder.setForeground(Color.red);154jtf_inOrder.setEditable(false);155jtf_inOrder.setEnabled(true);156jtf_inOrder.setBackground(Color.white);157jtf_inOrder.setFont(new Font(T
45、rebuchet MS,Font.BOLD,24);158159return jtf_inOrder;160161学习情境5 树和二叉树162/设置后序遍历结果文本框163private JTextField Jtf_postOrder()164 if(jtf_postOrder=null)/如果文本框未创建165 jtf_postOrder=new JTextField();/创建文本框166 /设置文本框的位置、长度、高度；显示字体颜色；不可编辑；组件可见；背景/颜色，字体字号 167 jtf_postOrder.setBounds(new Rectangle(164,500,330,32
46、);168 jtf_postOrder.setForeground(Color.red);169 jtf_postOrder.setEditable(false);170 jtf_postOrder.setEnabled(true);171 jtf_postOrder.setBackground(Color.white);172 jtf_postOrder.setFont(new Font(Trebuchet MS,Font.BOLD,24);173 174 return jtf_postOrder;175176学习情境5 树和二叉树177/“创建二叉树”按钮：创建、设置、响应按钮事件178p
47、rivate JButton Jbt_create()179if(jbt_create=null)/如果按钮未创建180 jbt_create=new JButton();/创建按钮181 /设置按钮的位置大小,字体风格、颜色、文字说明182 jbt_create.setBounds(new Rectangle(407,45,150,32);183 jbt_create.setFont(new Font(u6977u4f53_GB2312,Font.BOLD,18);184 jbt_create.setForeground(new Color(255,50,0);185 jbt_create.
48、setText(构造二叉树);186 /以下响应点击按钮事件187jbt_create.addActionListener(new ActionListener()/添加监听器188学习情境5 树和二叉树189 Override/覆盖actionPerformed方法190 public void actionPerformed(ActionEvent e)/处理按钮事件191 try 192 String str_in=jtf_in.getText();/获得文本框数据193 if(str_in.equals()/如果文本框为空194 JOptionPane.showMessageDialo
49、g(null,输入不能为空！);195 return;196 else if(check(str_in)=false)/输入不合法则返回false197 198 JOptionPane.showMessageDialog(null,输入不合规则！);199 return;200 学习情境5 树和二叉树201 str_tree=str_in;/str_in如果合法，赋给str_tree202 tree=createBiTree(tree,str_tree);/创建二叉树203 depth=depth(tree);/调用计算高度方法204 /加入图形框并赋予当前值205 jContentPanel
50、.add(bitree_panel(),null);206 jContentPanel.repaint();/重画面板207 catch(Exception err)/异常处理，弹出提示对话框208 JOptionPane.showMessageDialog(null,输入有误！);209 210 211 );212 213 return jbt_create;214 215学习情境5 树和二叉树216/“先序遍历”按钮：创建、设置、响应按钮事件217 private JButton Jbt_preOrder()218 if(jbt_preOrder=null)/如果按钮未创建219 jbt_
