Computer Programming 1 Lab

2020-12-24

Chang, Chi-Hung

Outline

  • Stack
  • Queue
  • Tree
  • Exercise 12

Stack

  • Last In, First Out (LIFO)
  • Operations
    • push
    • pop

Stack

w:9in center

Queue

  • First In, First Out (FIFO)
  • Operations
    • enqueue
    • dequeue

Queue

w:8in center

Tree

  • Parent & child
  • A parent can have more than one child
  • All nodes are connected by pointers
  • A node with no child is called leaf

Tree

Binary Tree

The most common tree that for any parents, there will be at most 2 children
w:4in center

Tree

Tree Structure

struct node{
    int value;
    struct node* left;
    struct node* right;
}

struct node* root = malloc(sizeof(struct node));

Tree

Insertion

Suppose AA is a node that we are going to insert a new node BB to its left child.

struct node* B = malloc(sizeof(struct node));
B->left = NULL;
B->right = NULL;
A->left = B;

Tree

Deletion

Suppose we want to remove AA's left node.

free(A->left);
A->left = NULL;

Tree

Tree Order

Inorder

Order: left →\to root →\to right
w:3in center
1→3→4→6→7→8→10→13→141 \to 3 \to 4 \to 6 \to 7 \to 8 \to 10 \to 13 \to 14

Tree

Tree Order

Preorder

Order: root →\to left →\to right
w:3in center
8→3→1→6→4→7→10→14→138 \to 3 \to 1 \to 6 \to 4 \to 7 \to 10 \to 14 \to 13

Tree

Tree Order

Postorder

Order: left →\to right →\to root
w:3in center
1→4→7→6→3→13→14→10→81 \to 4 \to 7 \to 6 \to 3 \to 13 \to 14 \to 10 \to 8

Exercise 12

Give you the elements of a binary tree. The first element is the root node. When getting a new node (number), you should add the node into the binary tree. Please create the binary tree and print out the tree in postorder.

  • Input
    8 3 10 1 6 14 4 7 13
  • Output
    1 4 7 6 3 13 14 10 8

Any Question?