Chapter 19.1: Algorithms

Posted on Edited on In , Views: Disqus:

Prerequisite:

1
2
static int[] mylist1= {12,45,21,22,7,39,88};
static int[] mylist2= {7,12,21,22,39,45,88};
  • 9618 s21 41 Q2
1
2
3
4
5
6
7
8
9
public static int linearSearch(int item){
    for(int i=0;i<mylist1.length;++i){//从头开始一个一个看数组里的`element`是否是正在找的`item`
        if(item==mylist1[i]){//如果相等
            return i;//返回当前index
        }
    }
    System.out.println("item not found");//如果找到最后了都没找到 则打印"item not found"
    return -1;//终止程序并返回一个不是index的数字
}
1
2
3
4
5
6
7
8
9
10
11
FUNCTION LinearSearch(item:INTEGER, arr: ARRAY[1:10] OF INTEGER) RETURNS INTEGER
	FOR i <- 1 TO 10 
		IF arr[i] = item
			THEN
				OUTPUT "Item found"
				RETURN i
		ENDIF
	NEXT i
	OUTPUT "Item not found"
	RETURN -1
ENDFUNCTION

二分查找 可以用递归Recursion实现 也可以用循环iteration实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public static int binarySearch(int item){//the item to be searched
    int lwb=0,upb=7;//lowerbound和upperbound的初始化
    int mid;
    Boolean found=false;//初始化
    while(!found && lwb<=upb){//还没找到且范围正常
        mid=(lwb+upb)/2;//算出区间中值 然后对比区间中间的element和寻找的element的大小
        if(mylist2[mid]==item){//如果刚好找到 则fouund=true, 终止循环
            found=true;
        }
        else if(mylist2[mid]<item){//如果要找的item比区间中值大 则lwb变成mid+1
            lwb=mid+1;
        }
        else{
            upb=mid-1;
        }
    }
    if(found){
        return mid;
    }
    else{
        System.out.println("item not found");
        return -1;
    }
}

public static int recursiveBinarySearch(int[] bsarr, int lwb, int upb, int snum){//snum: the number to be searched; bsarr: array for binary search
    int mid=(upb-lwb)/2+lwb;
    if(lwb>upb){
        System.out.println("not found");
        return -1;
    }
    if(bsarr[mid]==snum){
        return mid;
    }
    else if(bsarr[mid]<snum){
        return recursiveBinarySearch(bsarr, mid+1, upb, snum);
    }
    else{
        return recursiveBinarySearch(bsarr, lwb, mid-1, snum);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
FUNCTION binarySearch(item:INTEGER, arr: ARRAY[1:10] OF INTEGER)
	DECLARE upb: INTEGER
	DECLARE lwb: INTEGER
	DECLARE mid: INTEGER
	upb <- 10
	lwb <- 1
	WHILE lwb<upb
		mid<-(upb+lwb)/2 // mid <- (upb-lwb)/2+lwb
		IF arr[mid]=item
			THEN
				OUTPUT "found"
				RETURN mid
			ELSE 
				IF arr[mid]<item
					THEN
						lwb=mid+1
					ELSE
						upb=mid-1
				ENDIF
		ENDIF
	ENDWHILE
OUTPUT "not found"
RETURN -1

Running:

1
2
3
4
5
6
7
8
System.out.println("binary search:");
System.out.println("Position of 7 in mylist2: "+ binarySearch(7));
System.out.println("Position of -2 in mylist2: ");
binarySearch(-2);
System.out.println("linear search:");
System.out.println("Position of 22 in mylist1: "+linearSearch(22));
System.out.println("Position of -2 in mylist1: ");
linearSearch(-2);

Result:

1
2
3
4
5
6
7
8
binary search:
Position of 7 in mylist2: 0
Position of -2 in mylist2:
item not found
linear search:
Position of 22 in mylist1: 3
Position of -2 in mylist1:
item not found

Sort

Factors that may affect the performance of a sorting algorithms:

  • The initial order of data
  • The number of data items to be sorted
  • The efficiency of the sorting algorithm

Prerequisite

1
2
3
int[] thedata = {34,43, 2, 4, 25, 98, 32, 43, 9, 11};
int[] a=Bubblesort(thedata);
int[] b=insertionsort(thedata);

Bubble Sort

  • 9618 s21 41 Q2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int[] Bubblesort(int[] arr){
    int top,temp;
    Boolean swap;
    top=arr.length-1;
    do{
        swap=false;
        for(int i=0;i<top;++i){
            if(arr[i]>arr[i+1]){
                temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
                swap=true;
            }
        }
        top--;
    }
    while(swap && top>0);
    return arr;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
FUNCTION BubbleSort(arr : ARRAY [1:10] OF INTEGER) RETURNS ARRAY [1:10] OF INTEGER
	DECLARE top : INTEGER
	DECLARE tmp : INTEGER
	DECLARE swap : BOOLEAN
	top=9
	REPEAT
		swap=FALSE
		FOR i <- 1 TO top
			IF arr[i]>arr[i+1] 
				THEN
					tmp<-arr[i]
					arr[i]=arr[i+1]
					arr[i+1]=tmp
					swap<-TRUE
			ENDIF
		NEXT i
		top <- top -1
	UNTIL NOT swap AND top<1
	RETURN arr
ENDFUNCTION

Insertion Sort

Describe how an insertion sort will sort the data

  • Set the first element to be the sorted list
  • Store the next element in a temporary variable // store the value to be sorted in a temporary variable
  • … Compare this next element to each element in the sorted list
  • Move the elements that are greater than it one space to the right and insert the temporary variable// swap the element down until in the correct position
  • Loop through all items from 2nd to end of array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static int[] insertionsort1(int[] arr){
    int lwb=0;
    int upb=arr.length-1;
    for(int i=lwb+1;i<=upb;++i){
        int key=arr[i];
        int place=i-1;
        if(arr[place]>key){
            while(place>=lwb && arr[place]>arr[place+1]){
                int tmp=arr[place+1];
                arr[place+1]=arr[place];
                arr[place]=tmp;
                place--;
            }
        }
    }
    return arr;
}
public static int[] insertionsort2(int[] arr){// this is more preferrable and more efficienct compared to insertionsort1
    int lwb=0;
    int upb=arr.length-1;
    for(int i=lwb+1;i<=upb;++i){
        int key = arr[i];
        int j = i-1;
        while(arr[j]>key && j>=lwb){
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=key;
    }
    return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
FUNCTION insertionSort (arr : ARRAY[1:10] OF INTEGER) RETURNS ARRAY[1:10] OF INTEGER
	DECLARE key : INTEGER
	DECLARE place:INTEGER
	FOR i < 2 TO 10
		key <- arr[i]
		place <- i-1
		WHILE arr[place-1] > arr[place] && place>1
			arr[place]=arr[place-1]
			place <- place -1
		ENDWHILE
		arr[place+1]<-key
	NEXT i
	RETURN arr
ENDFUNCTION

Abstract Data Types

Stack

  • Insert
  • Delete
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class stack{
    int[] sta;
    int basepointer=0;
    int toppointer=-1;//初始化为-1 代表stack为空的情况
    int item;
    int size;//最大容量
    public stack(int si){
        this.sta= new int[si];
        this.size=si;
    }
    public int pop(){
        if(toppointer==-1){//也可以写成 if(toppointer==basepointer-1)
            System.out.println("stack is empty, cannot pop");
            return -1;
        }
        else{
            item=sta[toppointer];
            toppointer--;
            return item;
        }
    }
    public void push(int item){//添加item进入stack
        if(toppointer==size-1){
            System.out.println("stack is full, cannot push");
        }
        else{
            sta[++toppointer]=item;
            //也可以写成: toppointer=toppointer+1;
            //           stack[toppointer]=item;
        }
    }
    public boolean isEmpty(){//大概率不会考
        if(toppointer==-1){
            return true;
        }
        else{
            return false;
        }
        //return (toppointer==-1)? true: false;
    }
    public int peek(){
        if(this.isEmpty()){
            System.out.println("stack is empty");
            return -1;
        }
        else{
            return sta[toppointer];
        }
    }
}

Queue

  • Insert
  • Delete
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class queue{
    int[] que= new int[10];
    int front=0;
    int rear=-1;
    int queueFull=10;//store the maximum size of the queue
    int queueLength=0;// store the current size of the queue
    public void enqueue(int item){
        if(queueLength<queueFull){
            if(rear<queueFull-1){
                rear++;
            }
            else{
                rear=0;
            }
            queueLength=queueLength+1; 
            que[rear]=item;
        }
        else{
            System.out.println("queue is full, cannot enqueue");
        }
    }
    public int dequeue(){
        if(queueLength==0){
            System.out.println("Queue is empty, cannot dequeue");
            return -1;
        }
        else{
            int item=que[front];
            if(front==queueFull-1){
                front=0;
            }
            else{
                front=front+1;
            }
            queueLength--;
            return item;
        }
    }
}

Linked List

  • Insert
  • Delete
  • Find

Initialization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CONSTANT nullPointer=-1
TYPE node
	DECLARE data:STRING
	DECLARE nextPointer:INTEGER
ENDTYPE
DECLARE startPointer,freePointer:INTEGER
DECLARE list : ARRAY[0:N] OF node
PROCEDURE Initialization
	startPointer <- -1
	freePointer <- 0
	FOR i <- 0 TO N-1
		list[i].nextPointer<-i+1
	NEXT i
	list[N].nextPointer<-nullPointer
ENDPROCEDURE

Insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
static void insert(String value) {//根据大小插入 这里对比的是String的字典序
    if (freepointer != nullPointer) {
        int newNodePtr = freepointer;
        list[newNodePtr].data = value;
        freepointer = list[freepointer].pointer;
        int previousPtr = nullPointer;
        int thisPtr = startpointer;
        while((thisPtr != nullPointer) && (value.compareTo(list[thisPtr].data) > 0)){//如果value比thisptr的data大
            previousPtr = thisPtr;
            thisPtr = list[thisPtr].pointer;
        }
        //最终 value会比previousptr的大，比thisptr的小
        if (previousPtr == nullPointer) { // insert at the start of the node
            list[newNodePtr].pointer = startpointer;
            startpointer = newNodePtr;
        } else {
            list[newNodePtr].pointer = list[previousPtr].pointer;
            list[previousPtr].pointer = newNodePtr;
        }
    } else {
        System.out.println("no space");
    }
}
static void insertAtend(String value){
    if(freepointer!=nullPointer){
        int newNodeptr=freepointer;
        list[newNodeptr].data=value;
        freepointer=list[freepointer].pointer;
        int prevPointer=nullPointer;
        int thisptr=startpointer;
        while(thisptr!=nullPointer){
            prevPointer=thisptr;
            thisptr=list[thisptr].pointer;
        }
        if(prevPointer==nullPointer){
            startpointer=newNodeptr;
        }
        else{
            list[prevPointer].pointer=newNodeptr;
        }
        list[newNodeptr].pointer=nullPointer;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
PROCEDURE insert(item:STRING)
	DECLARE newPointer,prevPointer,thisPointer:INTEGER
	IF freePointer<>nullPointer
		THEN
			newPointer<-freePointer
			freePointer<-list[freePointer].nextPointer
			list[newPointer].data<-item
			prevPointer<-nullPointer
			thisPointer<-startPointer
			WHILE thisPointer<>nullPointer
				prevPointer<-thisPointer
				thisPointer<-list[thisPointer].nextPointer
			ENDWHILE
			IF prevPointer=nullPointer
				THEN
					startPointer<-newPointer
				ELSE
					list[prevPointer].nextPointer<-newPointer
			ENDIF
			list[newPointer].nextPointer<-nullPointer
	ENDIF
ENDPROCEDURE

Delete

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void deleteNode(String data){
    int thisPtr = startpointer;
    int previousPtr = nullPointer;
    while ((thisPtr != nullPointer) && (!data.equalsIgnoreCase(list[thisPtr].data))) {
        previousPtr = thisPtr;
        thisPtr = list[thisPtr].pointer;
    }
    if (thisPtr == nullPointer)
        System.out.println("data is not present");
    else {
        if (thisPtr == startpointer)//删除startPointer存的元素
            startpointer = list[startpointer].pointer;//把startPointer设置为下一个linked的元素
        else
            list[previousPtr].pointer = list[thisPtr].pointer;//若是删除链表中的元素，把previousPtr的元素link的要删除元素的下一个元素上
    	list[thisPtr].pointer = freepointer;//把删除的元素设置为free
    	freepointer = thisPtr;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
PROCEDURE delete(item: STRING)
	DECLARE prevPointer, thisPointer:INTEGER
	prevPointer<-nullPointer
	thisPointer<-startPointer
	WHILE list[thisPointer]<>null && list[thisPointer].data<>item
		prevPointer<-thisPointer
		thisPointer<-list[thisPointer].nextPointer
	ENDWHILE
	IF thisPointer<>nullPointer
		THEN
			IF thisPointer=startPointer
				THEN
					startPointer<-list[startPointer].nextPointer
				ELSE
					list[prevPointer].nextPointer<-list[thisPointer].nextPointer
			ENDIF
			list[thisPointer].nextPointer<-freePointer
			freePointer<-thisPointer
		ELSE
			OUTPUT "not found the item to be deleted"
	ENDIF
ENDPROCEDURE

Find

1
2
3
4
5
6
7
8
9
10
static int findNode(String data) {
    int currentNode = startpointer;
    while (currentNode != nullPointer) {
        if (data.equalsIgnoreCase(list[currentNode].data)) {
            return currentNode;
        }
        currentNode = list[currentNode].pointer;
    }
    return currentNode;
}
完整代码 
public class Main {
    static class ListNode {
        String data;
        int pointer;
        public ListNode() {
            data = "";
            pointer = nullPointer;
        }
    }
    static final int nullPointer = -1;
    static int startpointer, freepointer;
    static Scanner input = new Scanner(System.in);
    static ListNode[] list = new ListNode[8];
    static void initializeList() {
        startpointer = nullPointer;
        freepointer = 0;
        for (int i = 0; i < 7; i++) {
            list[i] = new ListNode(); // set all nodes as free nodes;
            list[i].pointer = i + 1;
        }
        list[7] = new ListNode();
        list[7].pointer = -1; // last node is intilized as -1;
    }
    static int menu() {
        System.out.println("1. insert an item");
        System.out.println("2. delete an item");
        System.out.println("3. search an item");
        System.out.println("4. display an item");
        System.out.println("Enter your choice 1/2/3/4");
        int ch = input.nextInt();
        return ch;
    }
    static void insert(String value) {//根据大小插入 这里对比的是String的字典序
        if (freepointer != nullPointer) {
            int newNodePtr = freepointer;
            list[newNodePtr].data = value;
            freepointer = list[freepointer].pointer;
            int previousPtr = nullPointer;
            int thisPtr = startpointer;
            while((thisPtr != nullPointer) && (value.compareTo(list[thisPtr].data) > 0)){//如果value比thisptr的data大
                previousPtr = thisPtr;
                thisPtr = list[thisPtr].pointer;
            }
            //最终 value会比previousptr的大，比thisptr的小
            if (previousPtr == nullPointer) { // insert at the start of the node
                list[newNodePtr].pointer = startpointer;
                startpointer = newNodePtr;
            } else {
                list[newNodePtr].pointer = list[previousPtr].pointer;
                list[previousPtr].pointer = newNodePtr;
            }
        } else {
            System.out.println("no space");
        }
    }
    static void insertAtend(String value){
        if(freepointer!=nullPointer){
            int newNodeptr=freepointer;
            list[newNodeptr].data=value;
            freepointer=list[freepointer].pointer;
            int prevPointer=nullPointer;
            int thisptr=startpointer;
            while(thisptr!=nullPointer){
                prevPointer=thisptr;
                thisptr=list[thisptr].pointer;
            }
            if(prevPointer==nullPointer){
                startpointer=newNodeptr;
            }
            else{
                list[prevPointer].pointer=newNodeptr;
            }
            list[newNodeptr].pointer=nullPointer;
        }
    }
    static void display(){
        int currentNode = startpointer;
        if (startpointer == nullPointer)
            System.out.println("no data in list");
        while (currentNode != nullPointer) {
            System.out.print(list[currentNode].data + "  ");
            currentNode = list[currentNode].pointer;
        }
    }
    static int findNode(String data) {
        int currentNode = startpointer;
        while (currentNode != nullPointer) {
            if (data.equalsIgnoreCase(list[currentNode].data)) {
                return currentNode;
            }
            currentNode = list[currentNode].pointer;
        }
        return currentNode;
    }
    static void deleteNode(String data){
        int thisPtr = startpointer;
        int previousPtr = nullPointer;
        while ((thisPtr != nullPointer) && (!data.equalsIgnoreCase(list[thisPtr].data))) {
            previousPtr = thisPtr;
            thisPtr = list[thisPtr].pointer;
        }
        if (thisPtr == nullPointer)
            System.out.println("data is not present");
        else {
            if (thisPtr == startpointer)//删除startPointer存的元素
                startpointer = list[startpointer].pointer;//把startPointer设置为下一个linked的元素
            else
                list[previousPtr].pointer = list[thisPtr].pointer;//若是删除链表中的元素，把previousPtr的元素link的要删除元素的下一个元素上
        }
        list[thisPtr].pointer = freepointer;//把删除的元素设置为free
        freepointer = thisPtr;
    }
    public static void main(String[] args) {
        initializeList();
        String Data, Choice = "";
        do {
            System.out.println("enter your choice");
            int ch = menu();
            switch (ch) {
                case 1:
                    System.out.println("Enter the value");
                    Data = input.next();
                    insert(Data);
                    display();
                    break;
                case 2:
                    System.out.println("Enter the value");
                    Data = input.next();
                    deleteNode(Data);
                    display();
                    break;
                case 3:
                    System.out.println("Enter the value");
                    Data = input.next();
                    int find = findNode(Data);
                    System.out.println(" item found " + find);
                    if (find == nullPointer)
                        System.out.println("data not found");
                    display();
                    break;
                case 4:
                    System.out.println("Print complete list");
                    display();
            }
            System.out.println("do you want to continue enter Y /y ");
            Choice = input.next();
        } while (Choice.equalsIgnoreCase("Y"));
    }
}

Binary tree

State the purpose of the free pointer:

  • To point to the start/ first of the empty node/nodes

Initialization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TYPE node
	DECLARE leftPointer: INTEGER
	DECLARE rightPointer : INTEGER
	DECLARE data : STRING
ENDTYPE
DECLARE N : INTEGER
DECLARE freePointer,rootPointer, nullPointer : INTEGER
DECLARE tree : ARRAY [0:N] OF node
PROCEDURE initialization 
	freePointer <- 0
	nullPointer <- -1
	rootPointer <- nullPointer
	FOR i <- 0 TO N-1
		tree[i].leftPointer <- i+1
	NEXT i
	tree[N].leftPointer <- -1
ENDPROCEDURE

Insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public static void AddNode(){
    Scanner sca = new Scanner(System.in);
    System.out.println("input the data to be Added");
    int data = sca.nextInt();
    if(FreeNode<=19){//如果Binary tree没用满
        int newPtr=FreeNode;
        ArrayNodes[newPtr]=new node(-1,data,-1);
        if(RootPointer==-1){//如果当前为空
            RootPointer=newPtr;
        }
        else{
            Boolean placed=false;
            int CurrentNode=RootPointer;
            while(placed==false){
                if(data<ArrayNodes[CurrentNode].data){//如果插入数值比当前数值小，则看左边
                    if(ArrayNodes[CurrentNode].leftPointer==-1){//如果左节点为空 则放到左节点
                        ArrayNodes[CurrentNode].leftPointer=newPtr;
                        placed=true;
                    }
                    else{//如果不为空 则继续往下搜空的地方插入
                        CurrentNode=ArrayNodes[CurrentNode].leftPointer;
                    }
                }
                else{//如果插入数值比当前数值大，则看右边
                    if(ArrayNodes[CurrentNode].rightPointer==-1){
                        ArrayNodes[CurrentNode].rightPointer=newPtr;
                        placed=true;
                    }
                    else{
                        CurrentNode=ArrayNodes[CurrentNode].rightPointer;
                    }
                }
            }
        }
        FreeNode=FreeNode+1;
    }
    else{
        System.out.println("Tree is full");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
PROCEDURE insert
	DECLARE newPointer,thisPointer,prevPointer:INTEGER
	DECLARE turnedLeft : BOOLEAN
	IF freePointer<>-1
		THEN 
			newPointer<-freePointer
			freePointer<-tree[freePointer].leftPointer
			INPUT data
			tree[newPointer].data <- data
			tree[newPointer].leftPointer<- nullPointer
			tree[newPointer].rightPointer <- nullPointer
			IF rootPointer = nullPointer
				THEN
					rootPointer<- newPointer
				ELSE
					thisPointer<-rootPointer
					prevPointer<-nullPointer
					WHILE thisPointer<>-1
						prevPointer<-thisPointer
						IF tree[thisPointer].data < data
							THEN
								turnedLeft<-FALSE
								thisPointer<-tree[thisPointer].rightPointer
							ELSE
								turnedLeft<-TRUE
								thisPointer<-tree[thisPointer].leftPointer
						ENDIF
					ENDWHILE
					IF turnedLeft
						THEN
							tree[prevPointer].leftPointer<-newPointer
						ELSE
							tree[prevPointer].rightPointer<-newPointer
					ENDIF
			ENDIF
	ENDIF
ENDPROCEDURE

Search🔍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void search(int element){
    int nownode=RootPointer;
    while(nownode!=-1){
        if(ArrayNodes[nownode].data==element){
            System.out.println("found, the position is:"+ nownode);
            return;
        }
        else if(ArrayNodes[nownode].data>element){
            nownode=ArrayNodes[nownode].leftPointer;
        }
        else{
            nownode=ArrayNodes[nownode].rightPointer;
        }
    }
    System.out.println("not found");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
FUNCTION search(item : STRING) RETURNS INTEGER
	DECLARE thisPointer : INTEGER
	thisPointer<-rootPointer
	WHILE thisPointer<>nullPointer
		IF tree[thisPointer].data=item
			THEN
				RETURN thisPointer
			ELSE
				IF tree[thisPointer].data>item
					THEN
						thisPointer<-tree[thisPointer].leftPointer
					ELSE
						thisPointer<-tree[thisPointer].rightPointer
				ENDIF
		ENDIF
	ENDWHILE
ENDFUNCTION

Traversal

1
2
3
4
5
6
public static void inorderTraverse(int ptr){
    if(ptr==-1) return;
    inorderTraverse(ArrayNodes[ptr].leftPointer);
    System.out.println(ArrayNodes[ptr].data);
    inorderTraverse(ArrayNodes[ptr].rightPointer);
}
完整代码 
class Main{
    static node[] ArrayNodes = new node[20];
    static int RootPointer=-1;
    static int FreeNode=0;
    public static void main(String[] args){
        //Adding: 23 5 8 100 9 88
        System.out.println("Adding Nodes");
        AddNode();
        AddNode();
        AddNode();
        AddNode();
        AddNode();
        AddNode();
        System.out.println("Printing Tree Content");
        printContent();
        System.out.println("Inorder Traverse");
        inorderTraverse(0);
        search(5);
    }
    public static void AddNode(){
        Scanner sca = new Scanner(System.in);
        System.out.println("input the data to be Added");
        int data = sca.nextInt();
        if(FreeNode<=19){//如果
            int newPtr=FreeNode;
            ArrayNodes[newPtr]=new node(-1,data,-1);
            if(RootPointer==-1){//如果当前为空
                RootPointer=newPtr;
            }
            else{
                Boolean placed=false;
                int CurrentNode=RootPointer;
                while(placed==false){
                    if(dataelement){
                nownode=ArrayNodes[nownode].leftPointer;
            }
            else{
                nownode=ArrayNodes[nownode].rightPointer;
            }
        }
        System.out.println("not found");
    }
    static class node{
        int leftPointer;
        int data;
        int rightPointer;
        public node(int lp,int da, int rp){
            this.leftPointer=lp;
            this.rightPointer=rp;
            this.data=da;
        }
    }
}

Past paper questions

Describe ways in which a queue differs from a stack:

  • In a stack the last item in is the first out/LIFO and in a queue the first item in is the first out/FIFO
  • Queue can be circular, but a stack is linear
  • Stack only needs a pointer to the top (and can have a base pointer, and a queue needs a pointer to the front and the rear