table of Contents
 二、查找
 2.1 静态查找
2.1.1 Method 1: sequential search
2.1.2 Method 2: binary search (Binary Search)
 2.1 静态查找
 五、树与非树
5.1 Nontree
5.2 tree
 七、树的表示
7.1 tree representation of the list
7.2 list tree (son – brother) notation
First, what is the tree
Third, the determination binary search tree
Fourth, the definition of the tree
Six, some basic terminology tree
First, what is the tree
There is hierarchy of the objective world in many things
Genealogy human society
Social structure
Book Information Management
Wherein the human society family tree as shown below:
Through the above mentioned hierarchical organization, it can make us more efficient in the management of data! So, for basic data management operations – look, we have to find how efficient it?
Second, look for
Finding: According to a given keyword K, K with the same keywords to find the records from the set R
Static lookup: the collection record is fixed, there is no set of operations that is inserted and removed, only to find
Dynamic look: the collection record is dynamic, that set of operations of both the search, insertion and deletion may also occur (dynamic we find not taken into account)
2.1 static lookup
2.1.1 Method 1: sequential search
/* c语言实现 */
int SequentialSearch (StaticTable *Tbl, ElementType K)
{
// 在表Tbl[1]~Tb1[n]中查找关键字为K的数据元素
int i;
Tbl>Element[0] = K; // 建立哨兵，即没找到可以返回哨兵的索引0表示未找到
for (i = Tbl>Length; Tbl>Element[i] != K; i); // 查找成功返回所在单元下标；不成功放回0
return i;
}
Sequential search algorithm of time complexity of O (n)
2.1.2 Method 2: binary search (Binary Search)
Let n data elements satisfy ordered keywords (for example: small to large), namely \ (k_1
Example: Suppose there are 13 data elements, in ascending order according to keywords stored. Binary search keywords for data elements of process 444 as shown below:
Still above 13 ordered linear elements constituting the table data example, binary search key data elements 43 as shown below:
/* c语言实现 */
int BinarySearch (StaticTable *Tbl, ElementType K)
{
// 在表中Tbl中查找关键字为K的数据元素
int left, right, mid, NoFound = 1;
left = 1; // 初始左边界
right = Tbl>Length; // 初始右边界
while (left <= right)
{
mid = (left + right) / 2; // 计算中间元素坐标
if (K < Tbl>Element[mid]) right = mid  1; // 调整右边界
else if (K > Tbl>Element[mid]) left = mid + 1; // 调整左边界
else return mid; // 查找成功，返回数据元素的下标
}
return NotFound; // 查找不成功，返回1
}
# python语言实现
def binary_chop(alist, data):
n = len(alist)
first = 0
last = n  1
while first <= last:
mid = (last + first) // 2
if alist[mid] > data:
last = mid  1
elif alist[mid] < data:
first = mid + 1
else:
return True
return False
Binary search algorithm has a time complexity of the number of O (logN)
Binary search algorithm solves the time complexity of the problem to find, but for the insertion and deletion of data is indeed O (n), so there a data structure, the time complexity of the data search can be either reduced, but also can reduce data the complexity of the insert and delete it?
Third, the determination binary search tree
In addition to the search key using the above two methods, we can also complete binary tree search key by this data structure.
As can be seen from the figure, if we need to find the number 8, can be achieved (may not understand that the future will be able to understand) the following four steps:
6 is smaller than the root node 8, to the right child of 6 to find 9
Node 9 is greater than 8, 9 to the left to find the subnode 7
Node 7 is less than 8, the left to find the subnode 7
Found 8
 \(ASL = (4*4+4*3+2*2+1)/11 = 3\)
Determine the tree each node needs to find just the number of nodes where the number of layers that;
Find a number of times to find success does not exceed the depth of the decision tree
The depth of the decision tree nodes is N \ ([log_2 {n}] + 1 \)
Fourth, the definition of the tree
Tree (Tree): \ ((\ {0}) \ n n geq) finite set of nodes configured.
 对于任一颗
Nonempty tree (n>0)
，它具备以下性质：
Tree has a special node called the root (Root), expressed by r
The remaining nodes can be divided into a finite set of m (m> 0) disjoint \ (T_1, T_2, \ cdots, T_m \), wherein each set is itself a tree, called subtrees of the original tree (SubTree)
When n = 0, called null tree
V. tree and nontree
Bear in mind that the tree has the following three characteristics:
Subtree are disjoint;
In addition to the root, each node has only one parent node;
A tree with N nodes has N1 edges
5.1 Nontree
5.2 trees
VI. Some basic terms of trees

Sibling (Sibling): each node having the same parent node is a sibling of another

Path and path length: The path from node (n_1) to (n_k) is a sequence of nodes (n_1, n_2, cdots, n_k), and (n_i) is the parent of (n_ {i+1}). The number of edges the route contains is the length of the route

Descendant: All nodes in the subtree of a node are descendants of this node

Node Level: specifies that the root node is at layer 1, the number of layers of any other node is the number of layers of its parent node plus 1

Depth of the tree: The largest level among all nodes in the tree is the depth of the tree
The number of subtree nodes: node degree (Degree)
Tree degree: all the nodes in the tree maximum degree
Leaf nodes (Leaf): degree of node 0
Parent node (Parent): with a subtree node is the root node of its parent node subtree
Child nodes (Child): If A node is the parent node B node, the node B is called a child node A node; child nodes, also known as child nodes
Ancestor: All nodes along the tree root to a node path are ancestors of this node
Represents seven trees
7.1 tree representation of the list
List tree representation shown above have great drawbacks, assuming a depth of the tree is very large, and can not guarantee that all child nodes of the tree have three, it will cause a large degree of waste.
7.2 list tree (son  brother) notation
In order to solve the waste will be represented by one of ordinary space list tree defects, we can set two link list pointers, a link to son nodes, links to another sibling node, as shown below:
Tree representation shown above has been perfectly adequate, but if we list tree represents the rotation angle of 45 °, will find as follows:
After a 45 ° angle of rotation, we will find a binary tree (a tree node has at most two subnodes), that is in fact the most common tree can represent binary tree, that is to say as long as we have thoroughly studied the binary tree , that is, we have thoroughly studied the tree.