学位论文-—双向循环链表的创建及相关操作的实现课程设计说明书

山东建筑大学计算机学院课程设计说明书

exchangeTree(rootNode); } }

private BiTNode exchangeTree(BiTNode t) { if (t != null) {

BiTNode p = t.right; t.right = t.left; t.left = p;

exchangeTree(t.right); exchangeTree(t.left); }

return t;

}

// 计算树的深度

public int depth() {

return depth(rootNode); }

private int depth(BiTNode t) { // 返回二叉树的深度 int depthleft, depthright; if (t == null) return 0;

depthleft = depth(t.left); depthright = depth(t.right);

return Math.max(depthleft, depthright) + 1; }

//横向输出树状图

public void showTree(BiTNode t,int n){ if (t==null) return; showTree(t.right,++n);

for (int i = 0; i < n; i++) System.out.print(\); System.out.print(t.data+\); showTree(t.left,n++); } }

24

山东建筑大学计算机学院课程设计说明书

3.测试函数 package kcsj;

public class Test {

public static void pln(Object o) {

System.out.println(o); }

public static void main(String[] args) {

BinaryTree bt = new BinaryTree(); Character[] charsPre = { 'a', 'b', 'd', null, null, null, 'c', 'e', null, null, 'f' };

Character[] charsPath = { 'a', 'b', 'c', 'd', null, 'e', 'f' };

pln(\先序建树：{'a','b','d',null,null,null,'c','e',null,null,'f'}\); bt.creatTree(charsPre); pln(\层序遍历结果：\); bt.pathOrder();

pln(\);

pln(\树图为(横向)：\);

bt.showTree(bt.rootNode, 1); pln(\);

pln(\层序建树：{'a','b','c','d',null,'e','f'}\); bt.creatPathTree(charsPath); pln(\先序遍历结果：\); bt.preOrder(); pln(\);

pln(\树图为(横向)：\);

bt.showTree(bt.rootNode, 1); pln(\);

pln(\叶子节点数：\ + bt.countLeafNode()); pln(\交换后层次遍历结果：\); bt.exchangeTree(); bt.pathOrder(); pln(\);

25

山东建筑大学计算机学院课程设计说明书

}

}

pln(\树图为(横向)：\); bt.showTree(bt.rootNode, 1); pln(\);

pln(\深度为：\ + bt.depth());

五、测试数据

1、对每个函数的测试数据

利用线序遍历和层次遍历分别建树a b c d e f 2、对程序整体的测试数据 a b c d e f

六、测试情况

先序建树：{'a','b','d',null,null,null,'c','e',null,null,'f'} 层序遍历结果： a b c d e f 树图为(横向)： f c e a b d

层序建树：{'a','b','c','d',null,'e','f'} 先序遍历结果： a b d c e f 树图为(横向)： f c e a b d

26

山东建筑大学计算机学院课程设计说明书

叶子节点数：3

交换后层次遍历结果： a c b f e d 树图为(横向)： d b a

e c f

深度为：3

27