《数据结构》实验指导/实验六:二叉树的存储及操作1 《数据结构》实验指导 实验六:二叉树的存储及操作 、实验目的 1、掌握树和二叉树抽象数据类型的定义。 2、掌握树和二叉树的存储实现 3、掌握二叉树的操作算法实现。 4、了解二叉树的应用 二、实验学时 、实验类型 验证性实验 四、实验需求 1、硬件 每位学生配备计算机一台: 2、软件 Windows XP/ Windows7操作系统:开发工具软件: Microsoft visual studio2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、树和二叉树的特点和基本运算 4、二叉树在二叉链表存储结构下的操作算法 六、实验任务 1、二叉树抽象数据类型的代码实现 2、编写应用程序,用相关数据验证运算算法 管理科学与工程学科/共6页第1页
《数据结构》实验指导 / 实验六：二叉树的存储及操作 1 管理科学与工程学科 / 共6页,第1页 《数据结构》实验指导 实验六：二叉树的存储及操作 一、实验目的 1、 掌握树和二叉树抽象数据类型的定义。 2、 掌握树和二叉树的存储实现。 3、 掌握二叉树的操作算法实现。 4、 了解二叉树的应用。 二、实验学时 2 学时 三、实验类型 验证性实验 四、实验需求 1、硬件 每位学生配备计算机一台； 2、软件 Windows XP/ Windows 7 操作系统；开发工具软件：Microsoft Visual Studio 2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、树和二叉树的特点和基本运算 4、二叉树在二叉链表存储结构下的操作算法 六、实验任务 1、二叉树抽象数据类型的代码实现 2、编写应用程序，用相关数据验证运算算法
《数据结构》实验指导/实验六:二叉树的存储及操作 2 七、实验内容及步骤 任务:代码实现二叉树的二叉链表存储结构;编写应用程序,用相关数据验证运算算法。 实验步骤: (1)启动 sual studio2010,创建窗体应用程序。 (2)增加二叉链表类,代码参考如下 public class BTNode ∥二叉树的结点类型类 public char data 数据元素 public BTNode Child; /指向左孩子结点 public BTNode rchild; 指向右孩子结点 }; class BTNode Class ∥二叉树类 const int Max Size 1000; BTNode r= new BTNode(; ∥二叉树的根结点r public string bstr; ∥)于递归算法中建立返回字符串 public BTNode class ∥构造函数 r lchild =r rchild= null: 二叉树的基本运算算法 public void CreateBTNode(string str) ∥由正确的二叉树括号表示str创建二 叉链的算法 BTNodell st= new BTNode Maxsizel;∥创建一个顺序栈 BTNode p=null; 建立的二叉树初始时为空 while gi< str Length) ∥循环扫描sr中每个字符 h=str[jl; switch(ch) case'(:top++; Stltopl=p;k=1; break;〃开始处理左孩子结点 case): top--; break case’,’:k=2; break; 开始处理右孩子结点 default: p= new BTNodeO pChild=p rchild= null p data=ch if(r== null) 若尚未建立根结点 管理科学与工程学科/共6页第2页
《数据结构》实验指导 / 实验六：二叉树的存储及操作 2 管理科学与工程学科 / 共6页,第2页 七、实验内容及步骤 任务：代码实现二叉树的二叉链表存储结构；编写应用程序，用相关数据验证运算算法。 实验步骤： （1） 启动 Visual Studio 2010，创建窗体应用程序。 （2） 增加二叉链表类，代码参考如下： public class BTNode //二叉树的结点类型类 { public char data; //数据元素 public BTNode lchild; //指向左孩子结点 public BTNode rchild; //指向右孩子结点 }; class BTNodeClass //二叉树类 { const int MaxSize = 1000; BTNode r = new BTNode(); //二叉树的根结点 r public string btstr; //用于递归算法中建立返回字符串 public BTNodeClass() //构造函数 { r.lchild = r.rchild = null; } //----------二叉树的基本运算算法------------------------------- public void CreateBTNode(string str) //由正确的二叉树括号表示 str 创建二 叉链的算法 { BTNode[] St = new BTNode[MaxSize]; //创建一个顺序栈 BTNode p = null; int top = -1, k = 0, j = 0; char ch; r = null; //建立的二叉树初始时为空 while (j < str.Length) //循环扫描 str 中每个字符 { ch = str[j]; switch (ch) { case '(': top++; St[top] = p; k = 1; break; //开始处理左孩子结点 case ')': top--; break; case ',': k = 2; break; //开始处理右孩子结点 default: p = new BTNode(); p.lchild = p.rchild = null; p.data = ch; if (r == null) //若尚未建立根结点
《数据结构》实验指导/实验六:二叉树的存储及操作 3 ∥p为二叉树的根结点 已建立二叉树根结点 case 1: St top Child= p; break; 2: St top) rchild=p; bi reak: public int BTNode height 二叉树高度的算法 return BTNodeHeightI(r); private int BTNodeHeightI(BTNode t) ∥被 BTNodeheight方法调用 nt lchild, rchildh return 0; ∥树的高度为0 Achild= BTNode heigh(hid;/求左子树的高度为 Achild lchild= BTNode Height(t rchild);/求右子树的高度为 rchildh return(Ichildh >rchildh)?(childh+1): (rchildh+1); ∥-叉树的遍历算法 public string Pre Ordero ∥先序遍历的递归算法 PreOrder(r); return btst private void Pre Orderl(bTNode t) 被 PreOrder方法调用 if(t! = null) ∥问根结点 PreOrder(t Child) 先序遍历左子树 PreOrderl(t rchild) ∥先序遍历右子树 管理科学与工程学科/共6页第3页
《数据结构》实验指导 / 实验六：二叉树的存储及操作 3 管理科学与工程学科 / 共6页,第3页 r = p; //*p 为二叉树的根结点 else //已建立二叉树根结点 { switch (k) { case 1: St[top].lchild = p; break; case 2: St[top].rchild = p; break; } } break; } j++; } } public int BTNodeHeight() //求二叉树高度的算法 { return BTNodeHeight1(r); } private int BTNodeHeight1(BTNode t) //被 BTNodeHeight 方法调用 { int lchildh, rchildh; if (t == null) return 0; //空树的高度为 0 else { lchildh = BTNodeHeight1(t.lchild); //求左子树的高度为 lchildh rchildh = BTNodeHeight1(t.rchild); //求右子树的高度为 rchildh return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1); } } //------------二叉树的遍历算法-------------------------------------- public string PreOrder() //先序遍历的递归算法 { btstr = ""; PreOrder1(r); return btstr; } private void PreOrder1(BTNode t) //被 PreOrder 方法调用 { if (t != null) { btstr += t.data.ToString() + " "; //访问根结点 PreOrder1(t.lchild); //先序遍历左子树 PreOrder1(t.rchild); //先序遍历右子树
《数据结构》实验指导/实验六:二叉树的存储及操作 public string InOrder 中序遍历的递归算法 bstr InOrder(r); return bstr: private void In Orderl(BTNode t) 被 In Order方法调用 if(t!=null) InOrderl(tChild); ∥中序遍历左子树 btsr+= t data. Tostring+"";/问根结点 InOrderl(t rchild); ∥中序遍历右子树 public string PostOrder ∥序遍历的递归算法 bstr= PostOrder(r); return bstr; private void PostOrder(bTNode t) /被 PostOrder方法调用 if (t!= null) PostOrder(tlchild) ∥后序遍历左子树 PostOrder(t rchild) ∥后序遍历右子树 btsr+= t data. ToString0+"";∥访问根结点 (3)设计窗体,界面参考如下 管理科学与工程学科/共6页第4页
《数据结构》实验指导 / 实验六：二叉树的存储及操作 4 管理科学与工程学科 / 共6页,第4页 } } public string InOrder() //中序遍历的递归算法 { btstr = ""; InOrder1(r); return btstr; } private void InOrder1(BTNode t) //被 InOrder 方法调用 { if (t != null) { InOrder1(t.lchild); //中序遍历左子树 btstr += t.data.ToString() + " "; //访问根结点 InOrder1(t.rchild); //中序遍历右子树 } } public string PostOrder() //后序遍历的递归算法 { btstr = ""; PostOrder1(r); return btstr; } private void PostOrder1(BTNode t) //被 PostOrder 方法调用 { if (t != null) { PostOrder1(t.lchild); //后序遍历左子树 PostOrder1(t.rchild); //后序遍历右子树 btstr += t.data.ToString() + " "; //访问根结点 } } } （3） 设计窗体，界面参考如下：
《数据结构》实验指导/实验六:二叉树的存储及操作 5 操作步骤1-建立二叉链b 输入括号表示: (B(D(G),C(E, F建立二叉链 注意:每个结点只用一个字符来表示,不能含空格 递归算法 先序遍历 先序序列: 中序遍历 中序序列: 后序遍历 后序序列 求高度输出结果: (4)编写窗体中按钮等控件的代码,调用循环顺序队列类,参考如下: BTNodeClass b= new BTNodeCl ass o //二叉链 private void button1 Cl ick ( object sender, EventArgs e) string mystr= text Box1. Text; b. CreateBTNode (mystr) pr ivate void but ton2 CI ick object sender, EventArgs e) text Box2, Text =b PreOrder o pr ivate void but ton 3 CI ick ob ject sender, EventArgs e) text 3. Text b InOrder O private void button cl ick (ob ject sender, EventArgs e text Box4 Text=b Post Order o 管理科学与工程学科/共6页第5页
《数据结构》实验指导 / 实验六：二叉树的存储及操作 5 管理科学与工程学科 / 共6页,第5页 （4） 编写窗体中按钮等控件的代码，调用循环顺序队列类，参考如下：
《数据结构》实验指导/实验六:二叉树的存储及操作 6 (5)调试运行,并观察运行情况 (6)在二叉链表类中增加求叶子结点个数的方法: (7)在窗体中增加相应控件和代码,调用步骤(6)中的方法,调试运行并观察运行结果。 八、实验分析 1、分析程序的运行过程,并将核心代码、错误提示及纠错内容记录至实验报告册 2、二叉树的存储和运算的代码实现; 3、数据结构的应用特点 九、课外自主实验 1、编写二叉树层次遍历的代码,并调试运行 2、编写代码实现通过输入先序序列创建二叉树的二叉链表存储,并调试运行。例如如下图所 示二叉树,通过输入序列ABC##DE#G##F##,创建二叉链表 管理科学与工程学科/共6页第6页
《数据结构》实验指导 / 实验六：二叉树的存储及操作 6 管理科学与工程学科 / 共6页,第6页 （5） 调试运行，并观察运行情况。 （6） 在二叉链表类中增加求叶子结点个数的方法： (7）在窗体中增加相应控件和代码，调用步骤（6）中的方法，调试运行并观察运行结果。 八、实验分析 1、 分析程序的运行过程，并将核心代码、错误提示及纠错内容记录至实验报告册； 2、 二叉树的存储和运算的代码实现； 3、 数据结构的应用特点。 九、课外自主实验 1、编写二叉树层次遍历的代码，并调试运行。 2、编写代码实现通过输入先序序列创建二叉树的二叉链表存储，并调试运行。例如如下图所 示二叉树，通过输入序列 ABC##DE#G##F###，创建二叉链表