java数据结构典型题

四、 (1) 队列（循环）

else{ }}

if(!isEmpty()){

Object t=queueElem[front]; return t;

front=(front+1)%queueElem.length;

public interface IQueue {

public void clear(); public boolean isEmpty(); public int length(); public Object peek();

public void offer(Object x) throws public Object poll(); }

public void display(){

for(int i=front;i!=rear;i=(i+1)% System.out.print(queueElem[i].toString(

else

Exception; queueElem.length) )+\); }

System.out.println(\此队列为空\); }}

public class CircleSqQueue {

private Object[] queueElem; private int front; private int rear;

public CircleSqQueue(int maxSize){ }

public void clear(){ }

public boolean isEmpty(){ }

public int length(){

return(rear-front+queueElem.length)%que}

public Object peek(){ }

public void offer(Object x) throws }

public Object poll(){

if(front==rear)

return null;

- 5 -

import java.util.*; public class test {

public static void main(String[] args) throws Exception {

CircleSqQueue S = new CircleSqQueue(100); // 初始化一个新的容量为100的顺序栈 Scanner sc=new Scanner(System.in); System.out.print(\请输入循环队列的长度:\); int n=sc.nextInt();

System.out.println(\请输入循环队列中的各个数据元素值(数字):\); for(int i=0;i

S.offer(sc.nextInt()); System.out.println(\建立的循环队

front=rear=0;

queueElem=new Object[maxSize];

front=rear=0;

return front==rear;

ueElem.length;

列中各元素为： \); S.display();

System.out.println();

System.out.println(\取队首元素

if(front==rear)

return null;

return queueElem[front]; else

值为： \); System.out.println(S.peek());

System.out.println(\去除队首元素后，循环队列中各元素为： \); S.poll();

S.display();

}}

Exception{

if((rear+1)%queueElem.length==front) throw new Exception(\队列已满\);

else { }

queueElem[rear]=x;

rear=(rear+1)%queueElem.length;

请输入循环队列的长度:5

请输入循环队列中的各个数据元素值(数字): 1 2 3 4 5

建立的循环队列中各元素为： 12345

取队首元素值为： 1

去除队首元素后，循环队列中各元素为： 2345

（2）队列（链式）

public class Node { private Object data; private Node next; public Node()

{ this(null,null); } public Node(Object data) { this(data,null); }

public Node(Object data,Node next) { this.data=data; this.next=next; } public Object getData(){

return data; } public Node getNext() { return next; }

public void setData(Object data) { this.data=data; }

public void setNext(Node next)

{ this.next=next; } }

public interface IQueue { public void clear(); public boolean isEmpty(); public int length(); public Object peek();

public void offer(Object x) throws Exception;

public Object poll(); }

< LinkQueue.java >

import java.util.Scanner;

public class LinkQueue implements IQueue{ private Node front; private Node rear; public LinkQueue(){ front=rear=null; } public void clear(){

front=rear=null; } public boolean isEmpty() { return front==null; } public int length() { if(!isEmpty()) { Node p=front; int length = 0; while(p!=null) { p=p.getNext(); ++length; }

}

return length(); }

public Object peek(){ if(front!=null) return front.getData(); else

return null; } public void offer(Object x) { Node p=new Node(x); if(front!=null){ rear.setNext(p); rear=p; } else

front=rear=p; }

public Object poll(){

if(front!=null){ Node p=front;

front=front.getNext(); if(p==rear)

rear=null;

return p.getData(); } else

return null; }

public void display(){

Node p=front;

while(p!=null){

System.out.print(p.getData().toString()+\);

p=p.getNext(); }

System.out.println(); }

public static void main(String[] args) throws Exception{

Scanner sc=new Scanner(System.in);

LinkQueue L=new LinkQueue();

System.out.print(\请输入链队列的长度:\); int n=sc.nextInt();

System.out.println(\请输入链队列中的各个数据元素值:\); for(int i=0;i

System.out.println(\建立的链队列中各元素为： \); L.display();

System.out.println();

System.out. println(\取队首元素值为： \); System.out.println(L.peek()); System.out.println(\去除队首元素后，链队列中各元素为： \); L.poll();

L.display(); }}

答案与循环队列相同

- 6 -

五、二叉树

class BiTreeNode { { }

public BiTreeNode(Object data) {

}

public BiTreeNode(Object data, BiTreeNode

this(data,null,null);

this(null); private Object data;

private BiTreeNode lchild, rchild; public BiTreeNode()

public BiTree (String preOrder,String inOrder,int preIndex,int inIndex,int count){

if(count>0){

char r=preOrder.charAt(preIndex); int i=0;

for(;i

break;

if(r==preOrder.charAt(i+inIndex))

root=new BiTreeNode(r);

root.setLchild(newBiTree(preOrder, inOrder,preIndex+1,inIndex,i).root); root.setRchild(new BiTree(preOrder,

inOrder,preIndex+i+1,inIndex+i+1,count-i-1).root); } } }

private static int index = 0; public BiTree(String preStr) {

public Object getData()

return data;

char c = preStr.charAt(index++); if (c != '#') {

root = new BiTreeNode(c);

lchild, BiTreeNode rchild) {// 构造一棵数据元素和左右孩子都不为空的结点 this.data = data; } { } { } { } { }

public void setRchild(BiTreeNode rchild) { this.rchild = rchild; }}

public class BiTree {

protected BiTreeNode root; public BiTree() { root = null; }

public BiTree(BiTreeNode root) { this.root = root; }

- 7 -

this.lchild = lchild; this.rchild = rchild;

root.setLchild(new BiTree(preStr).root); root.setRchild(new BiTree(preStr).root);

} else

root = null; }

public void setData(Object data)

this.data = data;

public void preRootTraverse(BiTreeNode T){

if(T!=null){ }}

if(T!=null){ }}

if(T!=null){ }}

int count=0; if(T!=null){

++count;

count+=countNode(T.getLchild()); count+=countNode(T.getRchild()); postRootTraverse(T.getLchild()); postRootTraverse(T.getRchild()); System.out.print(T.getData()); inRootTraverse(T.getLchild()); System.out.print(T.getData()); inRootTraverse(T.getRchild()); System.out.print(T.getData()); preRootTraverse(T.getLchild()); preRootTraverse(T.getRchild());

public BiTreeNode getLchild()

return lchild;

}

public void setLchild(BiTreeNode lchild) { this.lchild = lchild;

public BiTreeNode getRchild()

return rchild;

public void inRootTraverse(BiTreeNode T){

public void postRootTraverse(BiTreeNode T){

public int countNode(BiTreeNode T){

} return count; }}

}

public int getDepth(BiTreeNode T){ if(T!=null)

{ int lDepth=getDepth(T.getLchild());

int rDepth=getDepth(T.getRchild()); return 1+(lDepth>rDepth?lDepth:rDepth); 先根遍历： ABCD 中根遍历： BADC 后根遍历： BDCA

} return 0; } public BiTreeNode getRoot() {

return root;

}

public void setRoot(BiTreeNode root) { this.root = root; }

public int leaf(BiTreeNode T) { if (T == null) return 0;

else {

int left = leaf(T.getLchild()); int right = leaf(T.getRchild()); if (T.getLchild() == null && T.getRchild() == null)

return left + right + 1; else

return left + right;

}

}}

public class TestTree { public static void main(String[] arg){ String preStr=\; BiTree T= new BiTree(preStr); BiTreeNode root=T.getRoot(); System.out.println(\先根遍历：\); T.preRootTraverse(root); System.out.println();

System.out.println(\中根遍历：\); T.inRootTraverse(root); System.out.println();

System.out.println(\后根遍历：\); T.postRootTraverse(root);

System.out.println(); System.out.println(\结点个数为：\+T.countNode(root));

System.out.println(\叶子节点总数为：\+T.leaf(root));

System.out.println(\深度为：\+T.getDepth(root));

结点个数为：4 叶子节点总数为：2 深度为：3

- 8 -