preface

Infinite pole classification is something I learned a long time ago. When I was doing a project today, I found the concept of it was a little vague, so I will talk about infinite pole classification today.

First, let’s talk about the infinite pole classification. According to my understanding, it is to complete multiple classifications of data, just like a tree, from the root to the trunk, branches, leaves…

Two main methods are used to complete the classification of infinite poles, one is recursive method and the other is iterative method. The main uses of infinite pole classification are address resolution, breadcrumb navigation and so on. The following is a detailed introduction to the principles and implementation of the two methods.

Family tree and descendant tree

The genealogical tree is one of the manifestations of infinite pole classification, the other is the descendant tree. When I first started learning the infinite pole classification, I often confused the two trees, but now I understand a lot. The difference can also be seen in the Chinese meaning.

Genealogy, now many places are popular to repair genealogy, that how to repair genealogy, according to my understanding, is to find their own ancestors, generation after generation to find up, the formation of a system, so compiled and become called genealogy. A family tree is similar in that it starts at a node and goes up to its parent, and then to the parent’s parent, until it can’t be found. According to this search, the formation of a similar tree structure, is called a family tree.

A descendant tree, by contrast, is like a genetic map in a biology book, starting at a node and finding its children, and then finding their children, until they are done. The tree-like structure thus formed is called a descendant tree.

When I translate the description of family tree and descendant tree from above into code, my first impression is to use recursion, family tree, find the parent of the parent, descendant tree, find the child of the child. It’s perfectly recursive. So first let’s talk about using recursion to complete the family tree and descendants tree.

recursively

Realization of family tree

For a clearer explanation, I will first post the data to be classified below, which is about the address data:

$address = array (array (' id '= > 1, the' address '= >' anhui ', 'parent_id' = > 0), array (' id '= > 2,' address '= >' 'in jiangsu, 'parent_id' = > 0), array (' id '= > 3,' address '= >' hefei ', 'parent_id' = > 1), array (' id '= > 4,' address '= >' luyang district, 'parent_id' = > 3), array (' id '= > 5,' address '= >' big Yang Town ', 'parent_id' = > 4), array (' id '= > 6,' address '= >' nanjing ', 'parent_id' = > 2), array (' id '= > 7,' address '= >' xuanwu borough ', 'parent_id' = > 6), array (' id '= > 8,' address '= >' garden new village streets, 'parent_id' = > 7), array (' id '= > 9,' address '= >' Shanghai ', 'parent_id' = > 0), array (' id '= > 10,' address '= >' huangpu district, 'parent_id' = > 9), array (11, 'id' = > 'address' = > 'on the bund, "parent_id" = > 10) array (' id' = > 12, 'address' = > 'anqing, 'parent_id' => 1) );Copy the code

According to the introduction above, the above data are classified into infinite poles of family tree. Suppose that we want to find the family tree of Dayang Town, first find the information related to it.

'id'=>5, 'address'=>' dayang ', 'parent_id' => 4Copy the code

It can be seen that the ID of its parent node, namely parent_id ==4, then the node with id==4 is its parent node, thus finding luyang region:

'id'=>4, 'address'=>' luyangzao ', 'parent_id' => 3Copy the code

Similar to the above, search for nodes with ID =3 and search up in turn to find the family tree of Dayang Town

Dayang Town -> Luyang District -> Hefei -> Anhui

So how do you do that in code? Is the parent ID equal to the node id? Parent_id? = id, equal is the parent node to be searched, and the parent_id of this node is taken as the id to search recursively. The flow chart is as follows:

Let’s start coding:

/** * retrieve family tree * @param array $data * @param int/string $pid parent node */ function Ancestry($data, $pid) { static $ancestry = array(); foreach($data as $key => $value) { if($value['id'] == $pid) { $ancestry[] = $value; Ancestry($data , $value['parent_id']); } } return $ancestry; }Copy the code

According to the flow chart, the code is completed. Note that the array where the nodes are stored, $ancestry, is static or initialized with each recursion. You can also use array_merge to merge each returned array with the previous one.

The key to finding a family tree is conditional judgment. The parent_id is equal to the ID value of a node, which is obviously the parent node to be found.

Code written, to see if it meets our expectations, to find the big Poplar town family tree:

Ancestry($address , 4);
Copy the code

Results:

Array ([0] = > Array ([id] = > 4 [address] = > luyang district [parent_id] = > 3) [1] = > Array ([id] 3 [address] = = > > in hefei [parent_id] = > 1) [2] = > Array ([id] = > 1 [address] = > anhui [parent_id] = > 0))Copy the code

We can see that the results are in line with our expectations. So the recursive method of the family tree is done, and now the implementation of the descendant tree.

The realization of the descendant tree

Still using the above data, descendant tree is a tree-like graph formed by starting from the parent node and looking down for its descendant nodes.

Parent_id =0; these nodes are all children of id=0. Then, use the ID of the parent_id=0 node as the query ID until no child nodes are found. As follows:

The flow chart is as follows:

The process is similar to that of a family tree, but the key difference is the execution of conditional statements. The family tree determines whether the ID of the current node is equal to the parent_id of the previous node. The descendant tree determines that the parent_id of the current node is equal to the ID of the previous node. According to this condition, the descendant tree can have multiple descendant nodes, while the family tree can only have one ancestor. The code is as follows:

@param array $data * @param int/string $id id of the child node * @param int $Lev node level */ function getSubTree($data , $id = 0 , $lev = 0) { static $son = array(); foreach($data as $key => $value) { if($value['parent_id'] == $id) { $value['lev'] = $lev; $son[] = $value; getSubTree($data , $value['id'] , $lev+1); } } return $son; }Copy the code

I added a variable Lev to the function to mark the rank of the stored nodes, so as to see the structure of the descendant tree. Here are the test results:

getSubTree($data , 0 , 0);
Copy the code

Due to limited space, the results are partially processed:

foreach($tree as $k => $v) {
	echo str_repeat('--' , $v['lev']) . $v['address'] . '<br/>';
}
Copy the code

Results:

Anhui, hefei, luyang district -- -- -- -- -- - big Yang Town - anqing in jiangsu province - nanjing - xuanwu borough -- -- -- -- -- -, huangpu district, Shanghai bund garden new village streetCopy the code

It is easy to understand the family tree and descendants tree in a recursive way. As long as you understand the idea of recursion, it is not difficult to write it down step by step. The iterative approach can be more difficult to understand than the recursive approach. The following is to introduce iterative family tree and descendant tree compilation.

Iterative way

Family tree

Before we complete the descent of the family tree, let’s talk about the termination conditions for finding ancestral nodes. Although it is called the infinite pole classification, it is not an absolute infinite, but only a theoretical infinite.

As our country up and down five thousand years of history, any big surname, upward looking for its ancestors, either find Yan Emperor is to find the Yellow Emperor, there was no historical record in the past. Therefore, there are termination conditions in the search of the family tree, that is, when the parent node can no longer be found in the classification data, it is reflected in the instance data, that is, there is no node with parent_id < 0.

This is also the key to complete the iteration. It is used as the iteration condition to make circular judgment on the data, and the parent_id of each node found is used as the iteration condition again until the iteration condition is not satisfied. The flow chart is as follows:

Clear up the process and start coding now:

function Ancestry($data , $pid) {
	$ancestry = array();

	while($pid > 0) {
		foreach($data as $v) {
			if($v['id'] == $pid) {
				$ancestry[] = $v;

				$pid = $v['parent_id'];
			}
		}
	}

	return $ancestry;
}
Copy the code

Iteration condition $PID >0. If PID >0, it indicates that there are ancestors and the iteration can continue; otherwise, it indicates that there are no ancestors and the iteration ends. $pid = $v[‘parent_id’] $pid = $v[‘parent_id’]

Running this function gives the same result as using the recursive method.

The realization of the descendant tree

Using iteration to complete the descendant tree, which is more complex, requires the idea of using a stack. Every time in the process of iteration, will find the id of the stack, find a node, the node will be deleted from the original data, when find the leaf nodes, namely there is no descendant node, will the leaf node corresponding to the id of the pop up from the stack, then find the stack id of the sons of nodes, until the stack to empty, the end of the iteration. Here’s an example:

$address = array (array (' id '= > 1, the' address '= >' anhui ', 'parent_id' = > 0), array (' id '= > 2,' address '= >' 'in jiangsu, 'parent_id' = > 0), array (' id '= > 3,' address '= >' hefei ', 'parent_id' = > 1), array (' id '= > 4,' address '= >' luyang district, 'parent_id' = > 3), array (' id '= > 5,' address '= >' big Yang Town ', 'parent_id' = > 4), array (' id '= > 6,' address '= >' nanjing ', 'parent_id' = > 2), array (' id '= > 7,' address '= >' xuanwu borough ', 'parent_id' = > 6), array (' id '= > 8,' address '= >' garden new village streets, 'parent_id' = > 7), array (' id '= > 9,' address '= >' Shanghai ', 'parent_id' = > 0), array (' id '= > 10,' address '= >' huangpu district, 'parent_id' = > 9), array (11, 'id' = > 'address' = > 'on the bund, "parent_id" = > 10) array (' id' = > 12, 'address' = > 'anqing, 'parent_id' => 1) );Copy the code

Find the descendant node whose ID =0, push the node whose id=0, find the node, where

Array (' id '= > 1, the' address '= >' anhui ', 'parent_id' = > 0)Copy the code

At this point, the stack is [0], and the node is deleted from the original data, then the node id=1 is added to the stack, and the descendant node id=1 is found:

Array (' id '= > 3,' address '= >' hefei ', 'parent_id' = > 1),Copy the code

At this point, stack [0][1], delete the node, add id=3 to the stack, find the descendant node whose ID =3, find:

Array (' id '= > 4,' address '= >' luyang district ', 'parent_id' = > 3)Copy the code

[0][1][3], delete this node, add id=4 to the stack, find the descendant node whose ID =4, find:

Array (' id '= > 5,' address '= >' big Yang Town ', 'parent_id' = > 4),Copy the code

[0][1][3][4], delete the node, add id=5 to the stack, push [0][1][3][4][5], search for the child node with ID =5, failed to find after traversal, remove id=5 from the stack, search for the child node with ID =4 again, and proceed in sequence. Finally complete the entire iteration.

During the stack, the situation is as follows:

[0] [0] [1] [0] [1] [3] [0] [1] [3] [4] [0] [1] [3] [4] [5] [0] [1] [3] [4] [0] [1] [3] [0] [1] [0] [1] [12] [0] [1] [0]...Copy the code

The code is as follows:

function getSubTree($data , $id = 0) { $task = array($id); $son = array(); while(! empty($task)) { $flag = false; Foreach ($data as $k => $v) {if($v['parent_id'] == $id) {$son[] = $v; $task ($v['id']); $id = $v['id']; $data[$k]; $data[$k]; $flag = true; If ($flag == false) {array_pop($task); $id = end($task); }} return $son; }Copy the code

The node must be deleted from the original data after it is found; otherwise, the node will be found every time, forming the bug of infinite iteration. Here, array_push and array_POP are used to simulate the loading and unloading operations.

Iterating to create a descendant tree is complicated, and I haven’t tested it against recursion, but iterating to create a family tree is obviously more efficient than recursion.

application

Breadcrumb navigation

Having said the realization principle and method of infinite pole classification, now let’s talk about the application of infinite pole classification in the website. The most common is breadcrumb navigation.

What is breadcrumb navigation? The name comes from the fairy tale “Hansel and Gretel”, which I won’t tell you, but you can Google it. Breadcrumb navigation tells visitors where they are on the site and how to get back. Here is a typical breadcrumb navigation.

Breadcrumb is a typical family tree application. Don’t think of it as a descendant tree application because it’s going from left to right and getting lower and lower, because descendant trees can have multiple branches, whereas breadcrumb navigation requires a single trunk.

The breadcrumb navigation can be completed by modifying the family tree code above. We use a recursive family tree. The code is as follows:

function Ancestry($data , $pid) {
	static $ancestry = array();

	foreach($data as $key => $value) {
		if($value['id'] == $pid) {

			Ancestry($data , $value['parent_id']);
			
			$ancestry[] = $value;				
		}
	}
	return $ancestry;
}
Copy the code

If the recursive call is made first, and the found node is stored in the array at the end of the recursion, the ancestor node can be arranged in the front of the array, and the descendants node in the back of the array, which is convenient for data extraction.

Simplify the demonstration steps, instead of fetching data from the database, simulate data instead:

$TMP = array (array (' cate_id = 1, 'name' = > 'front page', 'parent_id' = > '0'), array (' cate_id = 2, 'name' = > 'news center, 'parent_id' = > '1'), array (' cate_id '= 3,' name '= >' entertainment news', 'parent_id' = > '2'), array (' cate_id '= 4,' name '= >' military news, 'parent_id' = > '2'), array (' cate_id = 5, 'name' = > 'sports',' parent_id '= >' 2 '), array (' cate_id '= 6,' name '= >' blog ', 'parent_id' = > '1'), array (' cate_id '= 7,' name '= >' travel log ', 'parent_id' = > '6'), array (' cate_id '= 8,' name '= >' mood ', 'parent_id' = > '6'), array (' cate_id = 9, 'name' = > 'affair', 'parent_id' = > '6'), array (' cate_id '= 10,' name '= >' star ', 'parent_id' = > '3'), array (' cate_id = 11, 'name' = > 'web celebrity', 'parent_id' = > '3'));Copy the code

Assuming that the user clicks star navigation, the navigation displayed on the website is:

$tree = Ancestry($tmp , 10);
foreach ($tree as $key => $value) {
    echo $value['name'] . '>';
}
Copy the code

Prevents setting a parent class as a subclass

In the establishment of the website, there may be user editing errors, the parent node of a column is set as the child node of the column, such a setting will lead to data loss in the database, so before data update should pay attention to this point.

With a family tree, you can avoid this kind of mistake. When the user submits the form, we take out the family tree of the parent node of the column to be modified and traverse the family tree. If the node to be modified is found in the family tree, it indicates that the operation is wrong. It’s a little convoluted. Here’s an example:

To change the parent node of the column news center to entertainment news, take out the family tree of entertainment news:

Entertainment News Center home page

If a node to be modified is found in the tree, news center, then an error has occurred. The specific code is as follows:

$data = Ancestry($tmp , 3); foreach ($data as $key => $value) { if($value['cate_id'] == 3) { echo 'Error'; break; }}Copy the code

conclusion

The explanation of infinite pole classification is written here, I hope to give some inspiration to the students who are confused about infinite pole classification. In the next talent, there may be mistakes in the description, hope to see the students can point out.

At the same time, THANKS to Bull Education liu Daocheng, namely Yan Shiba teacher, from his teaching video to learn a lot, this time to re-watch infinite pole classification, Yan teacher’s video gave me a lot of help. Thank you again, Miss Yan.