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

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

return data; }

public double getWight() { return weight; }

@Override

public int compareTo(BiTNode o) { if (o.getWight() > this.getWight()) return 1;

if (o.getWight() < this.getWight()) return -1; return 0; } }

2.BinaryTree()构造 package kcsj;

import java.util.LinkedList; import java.util.Queue;

public class BinaryTree> { AnyType[] pre, in;

BiTNode rootNode = new BiTNode(); int count = 0;

public BinaryTree() { rootNode = null; }

public BinaryTree(AnyType rootNodeItem) { rootNode.data = rootNodeItem;

rootNode.left = rootNode.right = null; }

public BinaryTree(BiTNode t) { rootNode = t; }

//1. 先序遍历建树

20

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

public BiTNode creatTree(AnyType[] a) { return rootNode = creatBinaryTree(a); }

private BiTNode creatBinaryTree(AnyType[] a) { BiTNode p = null; if (count < a.length) {

AnyType data = a[count]; count++;

if (data != null) {

p = new BiTNode((AnyType) data); p.left = creatTree(a); p.right = creatTree(a); } }

return p;

}

//1.层次遍历排序建树

public void creatPathTree(AnyType[] a) { if (a != null) {

creatPathBinaryTree(a);

} }

private void creatPathBinaryTree(AnyType[] a) {

Queue> q = new LinkedList>(); BiTNode node = new BiTNode(a[0]); rootNode = node; q.offer(node); int i = 1;

while (i < a.length) {

if (a[i] != null) {

node = new BiTNode(a[i]); q.element().left = node; q.offer(q.element().left); }

if (i < a.length - 1) {

if (a[++i] != null) {

21

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

}

}

}

node = new BiTNode(a[i]); q.element().right = node; q.offer(q.element().right); }

q.poll(); i++;

//2.实现二叉树的层次遍历 public void pathOrder() { if (rootNode != null) pathOrder(rootNode); }

public void pathOrder(BiTNode t) {

Queue> q = new LinkedList>(); q.offer(t);

while (!q.isEmpty()) {

if (q.element().left != null) q.offer(q.element().left); if (q.element().right != null) q.offer(q.element().right);

System.out.print(q.poll().data + \);

}

}

// 先序遍历

public void preOrder() { if (rootNode != null) preOrder(rootNode); }

private void preOrder(BiTNode t) { if (t != null) {

System.out.print(t.data+\);

22

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

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

}

// 统计节点的个数

public int countNode() {

return countNode(rootNode); }

private int countNode(BiTNode t) { int m, n;

if (t == null) return 0;

m = countNode(t.left); n = countNode(t.right); return m + n + 1; }

// 3.统计叶子节点个数（递归） public int countLeafNode() {

return countLeafNode(rootNode); }

private int countLeafNode(BiTNode t) { int m = 0, n = 0; if (t == null) return 0;

if (t.left == null && t.right == null) { return 1; }

m = countLeafNode(t.left); n = countLeafNode(t.right); return m + n; }

// 4.将二叉树左+右子树相互交换（递归） public void exchangeTree() { if (rootNode != null) {

23