编程知识 cdmana.com

Data structure learning (3) -- tree

( One ) Trees

1.  The definition of a tree

Trees are n A finite set of nodes .N=0 It's called an empty tree . In any nonempty number ,(1) Having and having only one specific node is called the root (root) The node of .(2) When n>1 when , The other nodes can be divided into m Subtrees that don't intersect each other .

The node of a tree contains a data element and several branches pointing to its remaining subtree . The subtree owned by a node is called a node's degree Degree). A point with a degree of zero is called leaf leaf) Node or terminal node . A node whose degree is not zero is called Branch node or internal node . Treelike degree Is the maximum value of each node degree . The subtree of a node is called a node's children child). Nodes are also called subtrees Parents parent). Children of the same parent are called each other brother sibling). Nodal The ancestors It is all the nodes from the root node to the current node . Any node in a subtree whose root node is a node is called the node's descendants .

The hierarchy of nodes (level) Start with the root node definition , The root is the first layer , The child of root is the second layer . If the node is at l layer , Then its child node is in the l+1 layer . The maximum level of the tree is called the depth of the tree (Depth) Or height .

The subtrees of the nodes in the tree are ordered from left to right , It can't be exchanged . Then the tree is called Ordered trees . Otherwise it is called Disordered trees .

The forest (forestm A collection of disjoint trees is called a forest .

2.  The storage structure of the tree

(1)  Parenting

Store the data elements of the tree in the form of an array .

Node design data structure .Node Include data fields data And pointer fields parent. among data Store node data . Pointer to the domain parent Store the subscript of the parent node in the array . The root node of the parent by -1.

According to need , There are some variations of the parenting notation . For example Node Add a pointer to the first child on the left in the node structure , It's called the long domain .

(2)  Child representation

Each node has multiple pointer fields , Each pointer points to the root node of a subtree . This representation is also called multiple linked list representation .

Method 1 :Node The node structure is consistent . For example, except for the data domain, there are 5 Child pointer field . It's essentially a multiple list .

Method 2 :Node Nodes are consistent . There are data fields , Degree domain and child domain . Where the value in degree is an integer , There's a couple of children's pointer fields .

Method 3 : The expression of children's parents : The children at each node are arranged , Take single chain table as storage structure .n Each node has n A child's list . If it's a leaf node , Then the single chain list is empty .n Nodes form a linear table . To store in a sequential storage structure . Stored in a one-dimensional array .

An array of vertices . The data element is of structure (1), There is a pointer in the array element Child linked list pointing to the current node . It is similar to the adjacency list in a graph .

among ,(1 Tree vertex elements The data structure of is :data【 Store the data element itself 】 and firstChild【 The address of the first child's root node 】

2) Linked list data elements structure :child【 Current child node address 】,next【 Next child node address 】

(3)  Child brother notation

Any tree , The first child of its node is unique if it exists , Right brother is the only one if it exists . So we set up two pointers . Point to the first child of the node and the brother of the node respectively . The method of characteristic yes , No matter what kind of tree , Can be converted into a binary tree .

The data structure of the node is :datafirstChildrightSib

3.  Binary tree definition 、 nature 、 establish

(1)  The definition of binary tree

The binary tree is n A finite set of nodes , The node is either an empty set ( It's called an empty binary tree ), Or it consists of a node and two disjoint binary trees .

l  characteristic

Each node has at most two subtrees , therefore , The degree of nonexistence of binary trees is greater than 2 The node of . Left subtree and right subtree have order , It can't be exchanged . Even if a node has only one subtree , We also have to distinguish between the left subtree and the right subtree .

Binary trees have 5 Medium form .A. Empty binary tree .B. Only one root node .C. The root node has only the left subtree .D. The root node has only the right subtree .E. The root node has left subtree and right subtree .

l  Special binary tree

Oblique tree ( Left oblique tree -- All nodes have only left subtree 、 Right slant tree -- All nodes have only the right subtree )

Full binary tree : All nodes have left and right subtrees , And all the leaves are on the same layer . characteristic 【 The degree of non leaf node must be 2, In a binary tree of the same depth , The leaves of the full binary tree are the most 】

Perfect binary tree : For the last leaf node of a full binary tree . Lack of from right to left n Nodes .N< The number of leaf nodes in a full binary tree .

 

 

(2)  Binary tree storage structure

Sequential storage

Number the binary tree according to the full binary tree . therefore , Each node of a binary tree has its own number . Put the binary tree into an ordered one-dimensional array . The number is used as the subscript of the array . The value is the data element in the array .

The disadvantage of this way is : The size of the array is set according to the depth of the current binary tree . If the original binary tree is sparse , The waste is greater .

l  Binary list

Each node of a binary tree has at most two children , So we design a data field and two pointer fields . We make such a list as a binary list .Node The node structure is datalchildrchild.【 If you add a pointer to a parent node parent, It's a trident list 】

4.  Traversing the binary tree

Starting from the root node , Access all nodes in a certain order . Each node is accessed once and only once .

Preface , In the definition of middle order and subsequent traversal , They all use recursive definitions .

Known preorder and mediocre traversal sequences , You can only identify a binary tree .

We know the middle order and the following traversal sequence , You can also uniquely identify a binary tree .

We know the sequence of preorder and subsequent traversal , There's no way to be sure of a binary tree .

(1)  The former sequence traversal

If the binary tree is empty , Then return to null operation . otherwise , Access the root node first , Then it traverses the left subtree in order , Then we traverse the right subtree first .

(2)  In the sequence traversal

If the binary tree is empty , Then return to null operation . otherwise , The middle order traverses the left subtree first , Then access the root node , Finally, the middle order traverses the right subtree .

(3)  Subsequent traversal

If the binary tree is empty , Then return to null operation . otherwise , The sequence traverses the left subtree , Then access the root node , Finally, the right subtree is traversed posteriorly .

(4)  Level traversal

If the binary tree is empty , Then return to null operation . Otherwise from the first floor , That is, the root node starts accessing , Access from top to bottom . In the same layer , Access node by node from left to right .

5.  Clue binary tree

(1)  Concept and node design

Two fork tree , The pointer to the precursor and the successor is called the clue . A binary list with clues is called a clue list . The corresponding binary tree is called the clue binary tree .

Clue : The process of traversing a binary tree in a certain order to turn it into a threaded binary tree is called cueing .

The node design of clue binary tree . It is divided into 5 part , Namely data: data 、lchild: Left child's address or the address of the precursor node added by some clues 、ltag0 representative lchild For the left child 1 representative lchild It's the address of the precursor node that some kind of clue joins in 、rchild: The address of the right child or the address of a successor node that is added by some clues 、rtag0 representative rchild For the right child 1 representative rchild It's the address of the successor node added by some kind of clue .

(2)  Clue steps and code implementation

Take the middle order traversal as an example , Clue the binary tree . The process of clue binary tree is also done recursively .

P For the current binary tree to be processed .

1)  In this paper, the left binary tree is cued in the middle order .

2)  If P Is the left child of null, The modified p Of ltag by 1, At the same time, the previous node pre Address assigned to lchild.

3)  If p The precursor of pre The right child of null, The modified p Of rtag by 1, At the same time p The address of is assigned to pre Of rchild.

4)  take p Assign a value to pre, pre=p

5)  Clue p The right child .

 

 

  1. void InThreading(BiThrTree &p, BiThrTree &pre) {  
  2. if (p) {    //  To p In this paper, we present a new method to solve this problem   
  3. InThreading(p->lchild, pre);    //  Left subtree clue   
  4. if (!p->lchild)      //  empty , Building the lead   
  5. { p->LTag = Thread;    p->lchild = pre; }  
  6. if (!pre->rchild)   //  empty , Build a trail   
  7. { pre->RTag = Thread;   pre->rchild = p; }   
  8. pre = p;             //  keep  pre  Point to  p  The precursor of   
  9. InThreading(p->rchild , pre);  //  Right subtree clue   
  10. } // if  
  11. }   
(3)  For the binary tree traversal code after the pre order clue

If node.isLeftThread by 0, The next element is left child , If node.isLeftThread by 1, Successor is the successor element that the pointer refers to node.right.

  1. void preThreadList(Node node) {  
  2. while(node != null) {  
  3. while(!node.isLeftThread) {  
  4. System.out.print(node.data + ", ");  
  5. node = node.left;  
  6. }  
  7. System.out.print(node.data + ", ");  
  8. node = node.right;  
  9. }  

 

6.  Trees 、 The conversion of forest and binary tree

l  Trees are converted into binary trees

(1)  Add lines : Add a line between all the brothers .

(2)  Off line : The connection between node and child node is reserved except for the left most child , Remove the rest of the lines .

(3)  Adjust the hierarchy : Take the root node of the tree as the axis , Adjust the angle of the whole tree clockwise .

l  The forest is converted into a binary tree

(1)  Every tree turns into a binary tree .

(2)  The first tree doesn't move , Start with the second tree , Take the next tree in turn The following node as the previous tree has children .

l  A binary tree is transformed into a tree

(1)  Add lines : If the left child of a node exists , Then the node and the right child of the left child , Left child's right child's right child Wait for a line .

(2)  Off line : Delete all the nodes in the original line and the connection of the right child .

(3)  Level adjustment : Make a clear hierarchy .

7.  Huffman tree

(1)  Definition

A branch from one node of a tree to another constitutes a path between two nodes . The number of branches on a path is called The length of the path .

The path length of the tree It is the sum of the paths from the root node to each node .

The length of the weighted path of a tree Is the sum of the weighted path lengths of all leaf nodes of the tree . The binary tree with the smallest sum of weighted path length is called Huffman tree .

Huffman tree is mainly used in compression and decompression .

(2)  Construct Huffman tree algorithm

①  According to the given n Weight {W1W2 ... Wn} Constructed as n A collection of binary trees , Every tree in it Ti Only one with a weight is Wi The root node . Left and right subtrees are empty .

②  from F Two trees with the smallest weight are selected as the left and right subtrees , And set the weight of the root node of the new binary tree as the sum of the weights of the left and right subtrees .

③  from F Delete these two trees , At the same time, two new trees are added to the F in .

④  repeat 2 and 3 step , until F There is only one tree in the position of . This tree is the Huffman tree .

(3)  Huffman code

The Huffman tree specifies that the left branch represents 0, The right branch represents 1. From the root node to the leaf node send through the path composed of 0 and 1 The sequence of the node is the code of the corresponding character of the node . This is the Huffman code .

版权声明
本文为[It lost schoolboy]所创,转载请带上原文链接,感谢

Scroll to Top