# Data Structure (II) - 01 Tree
> PART (II) - 01
> Other parts in this series $\rightarrow$ [Data Structure - Syllabus ](/bU7575BKTwmwkvmJ5742xA)
>
> This part will only have binary tree codes for explanation, we will just introduce the data structure. For the more implementation please go to [Binary Search Trees](https://hackmd.io/@benny-liu/BkKAJdloA) and [Multiway Search Trees]().
# Tree as ADT
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be connected to exactly one parent, except for the root node, which has no parent (i.e., the root node as the top-most node in the tree hierarchy).
These constraints mean there are **no cycles or "loops"** (no node can be its own ancestor), and also that **each child can be treated like the root node of its own subtree, making *recursion* a useful technique for tree traversal.**
## Constructor
According to the last paragraph, we need a root and nodes.
Take the tree below for example:
* 0 is the root.
* 1 have two children(3 and 4) $\leftrightarrow$ 1 is parent of 3 and 4
* node 1, 3, 4 are a subtree for whole tree.
* node 3, 5, 6 are leaves in this tree, since they don't have child
* node 3, 4, 6 are at same level, level 2.
* 0 is the ancestor of 4 $\leftrightarrow$ 4 is the descendent of 0, since we can walk from 0 to 4
```mermaid
flowchart
root(0) --> 1(1)
root(0) --> 2(2)
2 --> 6(6)
1 --> 3(3)
1 --> 4(4)
4 --> 5(5)
level0(level 0)--> level1(level 1)--> level2(level 2) --> level3(level 3)
```
Fun fact, if we have n nodes, then their will be n-1 edges. In this case there are 5 nodes and 4 edges.
## Depth and Height
* Height of tree : number of the edges in the **longest path** from root **to a leaf**. (Height of empty tree = -1)
* Depth of node x : number of the edges in the path from x **to root**.
* Height of node x : number of the edges in the **longest path** from x **to a leaf**, which is the descendent of x.
Take node 1 in below tree for example, the depth of node 1 is 1 (1 $\rightarrow$ 0), and the height of node 1 is 2 (1 $\rightarrow$ 5).
Lets take other node for example, for node 3, the depth is 2 (3 $\rightarrow$ 0), and the height is 0 (3 is the leaf).
# Binary Tree
## Intro
The tree that can only have at most 2 chidren, left and right.
```mermaid
flowchart
b(is a binary tree) --> 0(0)-->1(1)
0 --> 2(2)
1 --> 3(3)
1 --> 4(4)
4 --> 5(5)
n(not a binary tree) --> n0(0)--> n1(1)
n0 --> n2(2)
n1 --> n3(3)
n1 --> n4(4)
n1 --> n5(5)
```
The max number of nodes of level i is $2^i$ (i is numebr of edges of path from root to the furthest leaf).
There are several kind of binary tree:
* [strict/proper/full binary tree](https://www.programiz.com/dsa/full-binary-tree)
* each node can have either 0 or 2 children.
* [complete binary tree](https://www.programiz.com/dsa/complete-binary-tree)
* all the levels are completely filled except possibly the lowest one, which is filled from the left.
* Calculate max number of nodes `m` of level `i`:
$m=2^i$
* Calculate the height of tree `h` from the number of nodes `n` in the tree:
$h=\lceil log_2(n)\rceil$
* [perfect binary tree](https://www.programiz.com/dsa/perfect-binary-tree)
* every internal node has exactly two child nodes and all the leaf nodes are at the same level.
* Calculate the number of nodes `n` in the tree from height of tree `h`:
$n=2^0+2^1+2^2+...+2^h$
$=2^{h+1}-1$
* Calculate the height of tree `h` from the number of nodes `n` in the tree:
$h=log_2(n+1)-1$
* [balanced binary tree](https://www.programiz.com/dsa/balanced-binary-tree)
* the height of the left and right subtree of any node differ by not more than 1.
$differ=\vert height_{left}-height_{right}\vert$
## Implementation
we can still use the array, but we will spend a lot of space, and most of them are unnecessary, unless it is a perfect binary tree. At the begining we set a arry `arr`, and the `arr[0]` is the root.
* Root is at index 0 in array.
* Left child of i-th node is at (2*i + 1)th index.
* Right child of i-th node is at (2*i + 2)th index.
* Parent of i-th node is at (i-1)/2 index.
To implementation a binary tree, we use the method of link list more often, each node have 3 elements.
1. data
1. address of left child
1. address of right child
```cpp=
class Node{
public:
int data;
Node* left, *right;
Node(){
left=right=NULL;
}
Node(int x){
data=x;
left=right=NULL;
}
};
```
### initialize a tree
```cpp
int main(){
Node* root=new Node(0);
root->left=new Node(1);
root->right=new Node(2);
root->left->left=new Node(3);
root->left->right=new Node(4);
root->left->right->right=new Node(5);
}
```
```mermaid
flowchart
0(0)-->1(1)
0 --> 2(2)
1 --> 3(3)
1 --> 4(4)
4 --> 5(5)
```
### traversal tree
:::warning
there are too many way to travel the tree so I put them in another page $\rightarrow$ [Binary Tree Traversal ](/rKpDVs5rTeO27T8OfWTwzw)
**The concept of traversal is really important for continue implementation**, so please read through.
:::
#### print tree(Inorder)
```cpp=
void print(Node* root, string prefix){
if(root!=NULL){
print(root->left,prefix+ " ");
cout<< prefix << root->data << endl;
print(root->right,prefix+ " ");
}
}
```
result of `print(root);` (the root in the last part)
```
3
1
4
5
0
2
```
### height of tree
Height of tree is the number of the edges in the **longest** path from root to a leaf. (Height of empty tree = -1).
At the biginning, we can break the tree to two subtree, the left subtree and right subtree.
Then we can say that the
$$\text{height of tree} = \text{height of heigher subtree} +1$$In this case, the heigher subtree is right subtree. Then, what is the height of right subtree? We break it again and do the same thing!(Do the recursion). If it comes to NULL, it represent we come across a empty tree (Height of empty tree = -1), just return -1.
```cpp=
int height(Node* root){
if(root==NULL) return -1;
int leftHeight=height(root->left), right_Height=height(root->right);
if(leftHeight>right_Height){
return leftHeight+1;
}else{
return right_Height+1;
}
}
```
# More trees
* [Heap]()
* [Binary Search Tree](https://hackmd.io/@benny-liu/BkKAJdloA) (also a kind of binary tree)
* Multiway Search Trees
Sign in with Wallet
Connect another wallet