---
tags: APCS Preparation
---

# Tree
## Binary Tree Implementation
### Using Arrays
Given the index of the node is $n$
* the left child of the node: $2n+1$
* the right child of the node: $2n+2$

缺點：**空間浪費！**
* **Given a binary tree with only three nodes in right sub trees**, we can discovered that there are a lot of empty memory spaces.

### Using pointers

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

#### 最簡單的建立！

#include<iostream>
using namespace std;
struct node
{
    char data;
    struct node *left;
    struct node *right;
};
int main()
{
    node *root,*p1,*p2,*p3,*p4,*p5,*p7;
    p1 = new node;
    p1->data = 'A';
    
    p2 = new node;
    p2->data = 'B';
    
    p3 = new node;
    p3->data = 'C';
    
    p4 = new node;
    p4->data = 'D';
    
    p5 = new node;
    p5->data = 'E';
    
    p7 = new node;
    p7->data = 'F';
    
    p1->left = p2;
    p1->right = p3;
    
    p2->left = p4;
    p2->right = p5;
    
    p3->left = NULL;
    p3->right = p7;
    
    p4->left = NULL;
    p4->right = NULL;
    
    p5->left = NULL;
    p5->right = NULL;
    
    p7->left = NULL;
    p7->right = NULL;
}