Hello everyone. In this lecture of Data Structure and Algorithm, we're going to learn Chapter 5 Binary Tree. First of all, let me introduce some basic concepts.
Binary tree is made up by a finite set of nodes.
The set is probably an empty set.
If the set isn’t empty, there exists a root, and the root node has left subtree and right one.
Binary tree has 5 basic forms.
The 5 forms are having 2 subtrees, having just left subtree, having just right subtree, and having no subtrees, that is, a binary tree with only a root node.
Don’t forget that a binary tree can have no nodes.
Node is a very important concept for a binary tree.
We have concepts such as father and son nodes, sibling nodes, branch nodes, leaf nodes and etc.
Among so many kinds of nodes, the root node is a indispensable kind of nodes.
Edge is a ordered pair of nodes.
Here, the order of each pair is from root to leaf.
It’s the direction of every edge. However,
We leave out all the arrows of edges for the directions of edges are all from root to leaves.
For some node in the tree, the length of the path
from root to it
is in fact
the number of effective paths in it.
Then in the path, the nodes close to root
are the ancestors of the nodes close to leaf nodes.
We define that
in the binary tree, the root is in level 0, and the levels of other
nodes are equal to the levels of their father nodes plus 1.
The depth is defined as
the level of the deepest leaf node. And the height is defined as the depth plus 1.
In fact the depth of some node in the tree is
equal to the number of effective edges in the path
from root to it.
And the height is equal to the number of
nodes in that path. Full binary tree is a very indispensable concept in Data Structure.
Nodes of this kind of binary tree
are either leaf nodes
or internal nodes. That is full binary tree.
As for complete binary tree. It is
a tree full of nodes
except the highest level.
Since all the nodes in the highest level should be completely on the left,
like the tree on the upper right. But the tree on lower left is not.
For such a binary tree,
if a node in the tree is a leaf node or
only has one child,
an external node or two can be added to that kind of nodes to make an extended binary tree.
Therefore, that kind of nodes become internal nodes, or we can call them branch nodes.
And the external nodes added are all leaf nodes.
For the external path lengths E,
and the internal path lengths I, E = I + 2n. There are some properties in binary tree.
For property 1, at most
2i nodes are in the i-th level of the tree。 We can see how full the binary tree
can be from this property. For property 2, in the binary tree of which the depth is k,
there exists at most 2^(k+1)-1 nodes.
That means the depth limits how full the binary tree
can be. For property 3,
in the binary tree, if the number of terminal nodes, i.e. leaf nodes of which the degrees are 0,
is n0, and the number of nodes of which the degrees are 2 is n2, n0 = n2 + 1.
As for property 4, it has relationship with property 3,
that is a property on full binary tree.
For a non-empty full binary tree,
the number of leaf nodes in the tree is equal to the number of branch nodes plus 1. And we have a deduction from it.
For the property 6, it says that if there are n nodes,
how high
the binary tree can be? Consider a special kind of binary tree — the complete binary tree,
the tree is full of nodes,
and the height can be order of logn. That means,
if there are n nodes in the tree, the height is at least logn.
Let’s think about these two questions, what is the relationship between extended binary tree
and full binary tree? And what is the relationship
among the 6 properties mentioned before?
Thank you all!