Suppose
\(
1\leq k\leq n
\rightarrow
V=k, E=k-1
\) is right.
To proof V=k+1 is right.
E=(k-1)+1=k.
\(V\) split to
\( \{V_0, V_1, V_2,\dots, V_k \}\)
\( V_0 \) is root.
\( \{V_1, V_2,\dots,V_k \}\) is set of sum of vertex of subtree of \( V_0 \).
\(
E=E_1+E_2+\dots+E_k+k
\)
The k is number of connecting of \(\{V_1,V_2,\dots,V_k\}\)
The nodes on level i are up to
\[
2^{i-1},i\geq 1
\]
The binary tree have k depth.
The number of nodes are up to
\[
2^k-1, k\geq 1
\]
On binary tree.
Suppose number of degree 0 nodes is \( n_0 \),
number of degree 1 nodes is \( n_1 \),
number of degree 2 nodes is \( n_2 \),
number of all nodes is \( n \).
\[
n_0 = n_2+1
\]
proof
\(
n=n_0+n_1+n_2
\)
Let \( B \) is the number of edges.
\(
n=B+1
\)
\(
\rightarrow
B = n_1+2n_2
\)
\(
\rightarrow
n=n_1+2n_2+1
\)
\(
\rightarrow
n_0+n_1+n_2 = n_1+2n_2+1
\)
\(
\therefore
n_0=n_2+1
\)
Full binary tree
Fulled all nodes on binary tree.
Therefore, number of nodes are \( 2^k-1 , k\geq 0\)
depth of complete / full binary tree
\[
\lceil \log_{2}(n+1) \rceil
\]
formal binary tree
Internal node is the node of tree and is not the leaf.
All Internal nodes have two child nodes that named formal binary tree.
put binary tree into array
Label of node is same as array index(omitted index 0).
Suppose the node i (\( i\neq 1 \))
Its label of parent is \( i/2 \).
Suppose the node i.
Its label of left child is \( 2i \).
\( 2i>n \rightarrow \not\exists \text{left child}\).
Suppose the node i.
Its label of right child is \( 2i+1 \).
\( 2i+1>n \rightarrow \not\exists \text{right child}\).
缺點
如果不是完備/完滿二元樹，會造成陣列空間的浪費。
節點的新增、刪除會搬動大部分的節點，造成cpu的負擔，使用
link list可以解決這個問題。
