Represents the tree and the tree

table of Contents

    First, what is the tree

  • 二、查找
    • 2.1 静态查找

        2.1.1 Method 1: sequential search

        2.1.2 Method 2: binary search (Binary Search)

  • Third, the determination binary search tree

    Fourth, the definition of the tree

  • 五、树与非树

      5.1 Non-tree

      5.2 tree

  • Six, some basic terminology tree

  • 七、树的表示

      7.1 tree representation of the list

      7.2 list tree (son – brother) notation

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
            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 sub-node 7

    Node 7 is less than 8, the left to find the sub-node 7

    Found 8

    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 \)

  • \(ASL = (4*4+4*3+2*2+1)/11 = 3\)

Fourth, the definition of the tree

Tree (Tree): \ ((\ {0}) \ n n geq) finite set of nodes configured.

    When n = 0, called null tree

  • 对于任一颗

    Non-empty 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)

V. tree and non-tree

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 N-1 edges

5.1 Non-tree

5.2 trees

VI. Some basic terms of trees

    The number of sub-tree 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

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

  2. 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

  3. Ancestor: All nodes along the tree root to a node path are ancestors of this node

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

  5. 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

  6. Depth of the tree: The largest level among all nodes in the tree is the depth of the tree

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 sub-nodes), 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.

Leave a Reply