《数据结构（Java语言版）实验指导书-树和二叉树实验.docx》由会员分享，可在线阅读，更多相关《数据结构（Java语言版）实验指导书-树和二叉树实验.docx（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、树和二叉树实验答案str)Stack st = new Stack();BTNode p = null;boolean flag = true;char ch;int i = 0;class BTNode (E data;BTNode Ichild;BTNode rchild;public BTNode() (Ichild = rchild = null; )public BTNode(E d) (data = d;Ichild = rchild = null;) class BTreeClass BTNode b; String bstr;public BTreeClass () (b =
2、null;)public void CreateBTree (String/二叉链中结点类/数据元素/指向左孩子结点/指向右孩子结点/默认构造方法/重载构造方法/二叉树类/根结点/二叉树的括号表不串/构造方法/创建以b为根结点的二叉链存储结构/建立一个栈while (i str.length ()(ch = str.charAt(i);/System.out.printin(v); switch (ch) case 1 ( * :st push (p);flag = true;break;case ):/循环扫描str中每个字符/刚刚新建的结点有孩子,将其进栈st .pop (); break
3、;/栈顶结点的子树处理完,出栈case ，:flag = false;/开始处理栈顶结点的右孩子break;default:p = new(ch) ; /用 ch 值新建一个结点if (b = null)b = p;/若尚未建立根结点通作为根结点else/已建立二叉树根结点(if (flag)/新结点p作为栈顶结点的左孩子(if (!st.empty() st.peek().Ichild = p; else/新结点p作为栈顶结点的右孩子( if (!st.empty() st.peek().rchild = p; ) break;)i+；/ /继续遍历) public String toStr
4、ing ()/返回二叉链的括号表示串( bstr = n;toStringl (b);return bstr;)private void toStringl (BTNode t) /被DispBTNode 方法调用if (t != null) bstr += t.data;if (t.Ichild != null | | t.rchild != null)bstr += H (n; toStringl(t.Ichild); if (t.rchild != null) bstr += ,n;toStringl(t.rchild); bstr += H)n;/输出根结点值/有孩子结点时输出” (n
5、/递归输出左子树/有右孩子结点时输出/递归输出右子树/输出)public class 实验 7_1 public static BTreeClass Swap(BTreeClass bt) BTreeClass btl = new BTreeClass ();btl.b = Swapl(bt.b); return btl;)private static BTNode Swapl(BTNode b) BTNode t, tl, t2;if (b = null) t = null;else t = new BTNodeCharacter(b . data); 复捌便统力tl = Swapl(b.l
6、child) ;/交换左子树t2 = Swapl (b. rchi Id) ;/交换右子树t. Ichild = t2;t.rchild = tl;) return t;)public static void main(String args) String s = A(B(D(,G) ) ,C(E,F) ) H;BTreeClass bt = new BTreeClass ();bt CreateBTree (s);System.out.printin();System.out.printIn ( bt: + bt.toString ();BTreeClass btl;System.out.
7、printin(n bt-btln);btl = Swap(bt);System.out.printIn( btl: + btl.toString (); ) ) class Node int data;char op;/构造方法Node Ichild, rchild;public Node(int data) (this.data = data;Ichild = rchild = null;)this.op = op; Ichild = rchild = null; ) public class 实验 7_2 static Node root;/表达式二叉树根结点static String
8、bstr;/二叉树的括号表示串public static void CreateEt(String str) Node p, a, b; int i = 0; char ch;Stack st = new Stack () ;/定义一个栈while (i str.length () ch = str.charAt(i);if (ch = 1+1 | | ch = * - * | | ch = T * * | | ch = * / 1) /遇到 运算符(p = new Node (ch);a = st.pop ();b = st.pop();p.Ichild = b; p.rchild = a;
9、 st push(p); i + +； else/其他为运算数( int d = 0;while (i 1) bstr += n ( ;/有子表达式加一层括号Displnl (t. Ichild, h + 1) ; /处理左子树bstr+= t. op;/输出运算符Displnl (t.rchild, h + 1) ; /处理右子树 if (h 1) bstr += n ) ;/有子表达式加一层括号)public static void main(String args) String str = n10 7 -3 5 2 /* + ”；/后缀表达式 System.out.printin();System.out.printin( System.out.printin(n CreateEt(str);System.out.printin( System.out.printin(n System.out.printin( System.out.printin(H后缀表达式：+ str);(1)创建表达式二叉树rootn);(2)输出表达式二叉树”);root: ” + DispEt();(3)计算表达式值：” + Comp ();(4)对应的中缀表达式：” + Dispin ();