Categories: Data structures. Categories: Data structures

concept

  • The maximum degree of the tree is 2;

  • Left and right subtrees;




Inclined tree

  • Left inclined tree: a binary tree in which all nodes have only left subtrees;
  • Right-inclined tree: a binary tree in which all nodes have only right subtrees;
  • In fact, if there is such a need in the business directory, it is directly usedThe linear tableIt’s ok;



Full binary tree

  • The degree of all branch nodes is 2;
  • All leaf nodes can only be distributed on the bottom layer;

  • In the same depth of binary tree, the number of nodes in full binary tree is the largest, and the number of leaves is the largest.




Complete binary tree

  • The position of the ith node is exactly the same as that of the corresponding node in the full binary tree.
  • All leaf nodes can only appear in the bottom two layers;
  • If the node degree is 1, the node has only the left subtree, and there is no case of only the right subtree.
  • Distribution of nodesLeft right after the first;



Rules (Features)

  1. Number of nodes per layer: the i-th layer of the binary tree has at most (n=2^i-1), (I >=1);
  • All nodes: a binary tree of depth K has at most (n=2^K-1) nodes, (K>=1);
  • For any binary tree, n0= total number of leaf nodes, n1= total number of nodes with degree 1, n2= total number of nodes with degree 2, n = number of summary points: n0=n2+1
  • The total number of branching lines = N-1 = N1 +2n2;
  • N = n0 + n1 + n2;
  • n0+n1+n2-1 = n1+2n2 => n0=n2+1;
  • Full binary tree depth: log2(n+1);
  • Full binary tree depth: integer down (log2n)+1;
  • Since all leaf nodes of a complete binary tree can only appear in the bottom two layers and the penultimate layer is full, the depth of the penultimate layer +1 is also the depth of the complete binary tree.
  • For any node number I (1<= I <=n), I can be interpreted as array subscript +1, because array subscript starts at 0:
  • Parent node number: round down (I /2);
  • If 2i>n, this node has no left child, otherwise the left child is 2i;

  • If 2i+1>n, the node has no right child, otherwise the right child is 2i+1;




storage

  • Sequential storage, convenient query operation, and can be traversed according to the sequence, reasonable use of the above features;




    binary-tree-arr

  • Chain storage, easy to add, delete operations; The structure is data field + left child pointer + right child pointer (binary linked list). If necessary, parents can be added to point to the parent of the node (three-fork linked list), which is based on business requirementsFlexible control;



    binary-tree-arr

Conclusion: It is because of the above rules and characteristics of complete binary tree, so we try to use complete binary tree in daily use, the best way to choose sequential storage;

Traversal of binary trees

  • Mainly for chain storage, each node is accessed in a certain order to ensure that each node is accessed onlyAt a time, the following is defined according to the node access order;
    1. Foreword: beforeaccessRoot -> traverse left subtree -> traverse right subtree;First access the root
    • Middle order: Traverse left subtree ->accessRoot -> traverse the right subtree;Intermediate access to the root
    • After: traverses the left subtree -> traverses the right subtree -> accesses the root node;After accessing the root

    • Hierarchy: top-down, layer by layer from left to right access nodes;




derivation

  • Given the antecedent and middle order, a binary tree can be uniquely determined.
  • Given the postorder and middle order, a binary tree can be uniquely determined.
  • However, it is impossible to determine a binary tree if the antecedent and the antecedent are known.

Cue binary tree

  • In the case of node degree <1, the corresponding null pointer field points to its precursor or successor when traversing;
  • A traversal can be used many times, in the future application to reduce the traversal calculation method, can directly use the results of the first traversal;



Hoffman tree

  • 2. A branch between nodes forms a path between two nodes;
  • Path length: the number of branches between two nodes;
  • Tree path length: sum of path lengths from the root to each node;
  • Weighted path length of leaf node: path length from leaf node to root node * weight of leaf node;
  • WPL: The sum of the weighted path length of all leaf nodes;
  • Hoffman tree: the smallest binary tree in WPL Also known asOptimal binary tree;



    WPL

Huffman coding

  • The left branch of the Huffman tree represents 0 and the right branch represents 1
  • The sequence of 0s and 1s from the root node to the leaf node is called the character encoding corresponding to the leaf node, i.eHuffman coding.



    WPL-code