I. Introduction
In application system development, TreeView is a control of high use. Its main feature is to achieve classification, navigation, browsing and other functions more clearly. Thus, its method of use and programming skills have always been concerned about technicians. As the application demand changes, in many cases we need to implement the privilege control of data display, that is, the data seen by the user is filtered, or a continuous value, or some discrete values. For TreeView, the originally displayed is a complete strict parent-child relationship node set, and the node to display after the right is filtered, and there may be discrete, no longer have a complete inheritance relationship. In this paper, this paper is based on the analysis of the existing method, and the improved algorithm is proposed. The attached programs further explain the algorithm design ideas.
Second, a simple analysis of three common generation methods
As described in [2, 3], the generation of TreeView has substantially three ways:
1. Fill the TreeView node directly in the TreeView designer or code when designing the interface. This approach generates trees by dragging and dropping the control, the application range is narrow, and it is a non-programming method;
2. Create a tree structure from the XML file. This approach is generated through an XML file (string), from the form, this way is intuitive. Because the XML itself is a "tree", in the automatic generation code of TreeView under the .NET platform, the actual content of TreeView is also represented by XML. In addition, it is of great significance to distributed application applications in the heterogeneous environment based on XML file generation trees. In fact, it has been widely recognized as a general data transfer format using XML;
3. Get data from the database (in .NET, we can understand that the tree structure is established. This approach is a programming implementation of the most easily understood by the parent and child relationship. It is generally self-turning down to recursion to achieve widespread use.
Here, we may wish to give an actual example to explain that we have such a data set (you can see a company departments):
Tagvalue
CONTENTVALUE
ParentID
G01
Marketing department
G02
Consultant
G03
R & D department
G04
Testing Division
GS01
Marketing one
G01
GS02
Marketing
G01
GS03
Three soldiers
G01
GSL01
Marketing a Beijing Office
GS01
GSL02
Marketing a Shanghai office
GS01
GS04
Consultant
G02
GS05
Second part of the consultant
G02
GS06
Research and development
G03
GS07
Research and development
G03
GS08
Test one
G04
GS09
Test two
G04
GSL03
R & D, Hangzhou Division
GS06
GSL04
R & D, Xi'an Division
GS06
Table 1 Example Data Set
Among them, tagvalue is the actual value of the node. ContentValue is the value of the node displayed on the user interface or the tag value, and the ParentID is the Tagvalue of the parent node of the node. If the node is a root node, a ParentID is generally empty or equal to the TagValue itself.
By default, we can put all the nodes into a tree according to the algorithm below.
Algorithm 1: Recursively generating tree basic algorithm L Step 0: Data Preparation, Given Data Set. Generally speaking, the data set follows this format, ie (tagvalue, contentValue, parentid); L Step 1: Give a node that adds a child node (initially generally root node), records CURNODE, and ParentID to be added to the node Value (initial ParentID), records CurparentId; L Step 2: Find all nodes with specified ParentID values in the data set, get the node set Objarr [], if (objarr == null) return; else {/ / Traverse Node Set for (INT i = 0; I Figure 1 TreeView renderings The defect of this method is that the traversal order of the "parent node and child node" means that the parent node of each sub-node must exist, otherwise the searches are not searched, that is, tomography. In many practical applications, we have found that this implementation cannot be completely effective, the most typical situation is when the actual value characterized by the node (such as a list, person list, resource list, etc.) is required, at this time A fault occurrence of a fault occurs often from the data set of data from the database. For example, we assume that the given data is set to Table 2, that is, the first line "Marketing Department" is removed (Note: The permissions filtering operation has exceeded the scope discussed herein, this assumes that the data set is already high), then use the algorithm 1 The generated TreeView is shown in Figure 2. Tagvalue CONTENTVALUE ParentID G02 Consultant G03 R & D department G04 Testing Division GS01 Marketing one G01 GS02 Marketing G01 GS03 Three soldiers G01 GSL01 Marketing a Beijing Office GS01 GSL02 Marketing a Shanghai office GS01 GS04 Consultant G02 GS05 Second part of the consultant G02 GS06 Research and development G03 GS07 Research and development G03 GS08 Test one G04 GS09 Test two G04 GSL03 R & D, Hangzhou Division GS06 GSL04 R & D, Xi'an Division GS06 Table 2 Given the data set Figure 2 TreeView renderings It can be seen that the omission of nodes is generated here. In general, we can settle up from two aspects to solve the problem, on the one hand, can correct the data set, and on the other hand, it can modify the generated tree algorithm. Obviously, directly correcting the data set is very complicated, and it will bring efficiency. And unilateral modification spanning tree algorithm is also very good (ie, plugging the missing nodes directly below the root node), because there will be a phenomenon in the same level of the old generation. Third, the recursive generation tree algorithm by depth number Review some methods (text [1 ~ 5]), which give us some inspiration based on node depth spanning trees, we can increase the depth field when constructing data sets, but the depth of this is not a simple level number, It is an extension concept, specifically, in fact, a depth number, there is a certain correspondence with the parent number. For example, the data set shown in Table 1 can be as follows: TagvalueContentValue ParentID DEPTHID G01 Marketing department A001 G02 Consultant A002 G03 R & D department A003 G04 Testing Division A004 GS01 Marketing one G01 A001001 GS02 Marketing G01 A001002 GS03 Three soldiers G01 A001003 GSL01 Marketing a Beijing Office GS01 A001001001 GSL02 Marketing a Shanghai office GS01 A001001002 GS04 Consultant G02 A002001 GS05 Second part of the consultant G02 A002002 GS06 Research and development G03 A003001 GS07 Research and development G03 A003002 GS08 Test one G04 A004001 GS09 Test two G04 A004002 GSL03 R & D, Hangzhou Division GS06 A003001001 GSL04 R & D, Xi'an Division GS06 A003001002 Table 3 Data set with depth number Where the depthid is the depth number of the node. The process of generating depth numbers is actually not complex, first we can set the rules of the number, such as the prefix of the hierarchy, encoded length, start value, etc. When a node is numbered, just find the maximum number of the hierarchy, then increase 1. The specific implementation process is no longer detailed here. So, we naturally think of the ideological design of the algorithm 1 is based on the depth number generated tree program. At this time, we can look for its descendant set based on the depth number of the current node, but give a maximum span (can be understood as the number of intervals between the highest level and the lowest level), because it is not possible to find it without restrictions. This method can partially compensate for the defects of the traversal of "by the parent node and subtracks", because when the fault occurs, it will continue to find along the number. But it will still miss it, such as our given data set ("R & D" filter out): Tagvalue CONTENTVALUE ParentID DEPTHID G01 Marketing department A001 G02 Consultant A002 G03 R & D department A003 G04 Testing Division A004 GS01 Marketing one G01 A001001 GS02 Marketing G01 A001002 GS03 Three soldiers G01 A001003 GSL01 Marketing a Beijing Office GS01 A001001001 GSL02 Marketing a Shanghai office GS01 A001001002 GS04 Consultant G02 A002001 GS05 Second part of the consultant G02 A002002 GS07 Research and development G03 A003002 GS08 Test one G04 A004001 GS09 Test two G04 A004002 GSL03 R & D, Hangzhou Division GS06 A003001001 GSL04 R & D, Xi'an Division GS06 A003001002 Table 4 Given the data set During the spanning tree, when the child node is found in the "R & D Department" (A003), it is found to be "R & D" (A003002) because it is the nearest node. The following order is to look down on "R & D", it is obviously impossible to find "R & D, Hangzhou Branch" and "R & D, a Xi'an Division", because the number rules are different, so that the tree is the same Will miss the node. We propose a new algorithm that breaks the traditional traversal sequence and uses the bottom-up traversal order. Image stated, the traditional method is to continuously derive new child nodes (as shown in FIG. 3 (a)) through a single root node or parent node, and the new algorithm is to form a sub-tree set by constantly aggregating nodes. Finally, it will be a tree (as shown in Figure 3 (b)). Figure 3 Schematic diagram of TreeView node generation flow Algorithm 2: From the bottom up, according to the level (depth) traversal method generation tree algorithm L Step 0: Data Preparation, Tagvalue, ContentValue, DepthID, Tagvalue is the actual value of the node, ContentValue is the value displayed by the node or The tag value, depthid is the depth number of the node. If the node is the root node, the length of its depthid is generally shortest. Give maximum depth IMAXDEPLEN and minimum depth iMindeplen. Given the HashTable for storing the current subtree; L Step 1: Given the hierarchical length icdeplen, initial set to iMaxDeplen; L Step 2: Find the level of the condition in the data set according to the given icrDeplen, get this level Node Set Objarr [], IF (Objarr == Null) Return; Else {// Traversing Node Set for (INT I = 0; I In this algorithm, we have initially calculated the minimum length and maximum length of the Node depth number in the data set, with the aim of not blind search. However, if the depth number of each level in the data set is fixed, the search process can be simplified. The key value of the Hashtable of the Temporary Sub Tree is the TAG value of the current substrian root node. This is the advantage of being quite convenient and does not need to traverse one node in TreeView. So, each time you process the previous level node, just look at the parent node is not in HashTable, if you insert it into the subtree, you will increase the HashTable item. The appendix sample program implements this algorithm, here is a key function. Functional form and its parameter interpretation function PopulationCompleTree (Ref System.Windows.Forms.treeView ObjtreeView, DataSet Dssource, String StRTRTRTREECAPTION, INT. ITAGINDEX, IT ICONTENTENDEX, INT IDEPTHINDEX) 1. ObjtreeView is the TreeView that is ultimately generated; 2. DSSource is a given data set; 3. StrtreeCaption specifies the name of the TreeView root node; 4. ItagIndex is the number of Tagvalue fields in the data set; 5. icontentIndex is the number of contentValue fields in the data set; 6. iDepthIndex is the number of the data set in the DEPTHID field; 1. Use the level (depth) traversal method to generate a tree main adjustment function; 2. Call CollectNodes (Dataset Dssource, Int ItagIndex, IconDex, Int Id IdepthIndex, Int icdeplen, Int Imindeplen, Ref Hashtable Objarrnode) CollectNodes (Dataset Dssource, Int Itagindex, Int Icontex, Int IdepthIndex, Int iCurDeplen, Int Imindeplen, Ref Hashtable Objarrnode) 1. DSSource, ItagIndex, icontentIndex, IdePTHINDEX is the same; 2. IcurDeplen refers to the length of the current level depth number; 3. iMindeplen refers to the minimum depth, the top-level depth number length; 4. Objarrnode refers to a HashTable for depositing a middle child. 1. The node is collected from the bottom; 2. Call lookparentNode (Dataset Dssource, int IDepthIndex, string strsubdepth, int itagindex, int icontent " LookupparentNode (Dataset Dssource, int IDepthindex, string strsubdepth, int itagindex, int icontentindex) 1. DSSource, ItagIndex, icontentIndex, IdePTHINDEX is the same; 2. STRSUBDepth refers to the depth number of the current node (because it is recurrent lookup) 1. Find the most recent upper control level because it is possible that the parent node level does not exist. If a given data set (we put the "R & D Department" and "Marketing One"), Tagvalue CONTENTVALUE ParentID DEPTHID G01 Marketing department A001 G02 Consultant A002 G04 Testing Division A004 GS02 Marketing G01 A001002 GS03 Three soldiers G01 A001003 GSL01 Marketing a Beijing Office GS01 A001001001 GSL02 Marketing a Shanghai office GS01 A001001002 GS04 Consultant G02 A002001 GS05 Second part of the consultant G02 A002002GS07 Research and development G03 A003002 GS08 Test one G04 A004001 GS09 Test two G04 A004002 GSL03 R & D, Hangzhou Division GS06 A003001001 GSL04 R & D, Xi'an Division GS06 A003001002 Table 5 Given the data set Then the spanning tree is shown below, Figure 4 TreeView renderings This is the result we need. Of course, sometimes we will also take a so-called "neutral" method for the need for structural needs. For example, for the TreeView control node generated herein, if you do not want to write a reply number to generate a depth number, then we can also add a sign bit by adding a data set, ie, using the flag bit to identify whether the data has been filtered. After using the traditional algorithm to generate a tree, check if there is an unfilled data, if there is a procedure, insert it into the ancestor node. However, the "Find the ancestors" here is on TreeView, and when the node is much more efficient, it does not search directly on the data set. In addition, the introduction of depth numbers will not only bring convenience to the spanning tree, but also make permission settings more flexible. Specific to our example, generally if we want to filter out some departments, then one of these departments will be picked up, we call it "discrete value setting mode". When the system structure is huge, we prefer to pick a range, such as filtering a department and below the N-class, which is a "continuous value setting method", which contains the depth number containing the hierarchy concept. solve this problem. In the actual system development, we also found this way is practical. Fourth, other TreeView generation methods The front mentioned that TreeView can also be generated via an XML file (string). The key to this way is to construct an XML document or string similar to TreeView. Its basic idea should be similar to the algorithms discussed above, just slightly complex in program implementation (where the index of the XML node can be done based on the document object model (DOM)). Also note that there are a lot of third-party TreeView controls, the format of the XML document they support is different. It is limited to the space, which does not discuss the specific implementation process in detail. Five, small knot This article mainly discusses the design of TreeView control nodes under the .NET platform, combined with existing methods and actual needs, and research on design methods, gives a relatively complete solution. In the specific application of the tree, in addition to the spanning tree, the nodes increase, delete, change, and even the upgrade and degradation of the node are very common. In essence, these operations involve the operation related to the business-related database, so the implementation of these operations is consistent with the traditional approach in TreeView, which is generated by the bottom-by-hierarchical traversal method, additional Operation is nothing more than adding or modifying depth numbers. Of course, the actual demand is to change the multi-end, the design and analysis of the corresponding algorithm is also endless. Reference (REFERENCE): [1] Zane Thomas. DataViewTree for Windows Forms, http://www.abderaware.com/whitepapers/ DataReeView.htm [2] Li Honggen. Application of tree structure in development, http://www.microsoft.com/china/community/column/ 21.mspx [3] Li Honggen. WEB tree structure program design under .Net platform, http://www.microsoft.com/china/community/ column / 30.mspx [4] don schlichting. Populating the treeview control from a database, http://www.15seconds. Com / Issue / 030827.htm [5] How to: populate a treeview control from a dataset in Visual Basic .NET, HTTP: // support.COM/?kbid=320755 [6] Scott Mitchell. Displaying XML Data In The Internet Explorer TreeView Control, http: // aspnet. 4guysfromrolla.com/articles/051403-1.aspx ------------- Source Code: Using System.data; Using System.Windows.Forms; Using System.collections Namespace PoptreeView {/// /// TreeNode objRootNode = new TreeNode (strTreeCaption); // get node in the table, insert the tree foreach (object objNode in objArrNode.Values) {TreeNode objNewNode = new TreeNode (); objNewNode = (TreeNode) objNode; objRootNode.Nodes.Add ( Objnewnode);} objtreeView.nodes.add (objrootnode); /// #region back layer by layer, to collect node foreach (System.Data.DataRowView drow in dv) {// find the parent node string [] strArrParentInfo = LookupParentNode (dsSource, iDepthIndex, drow [iDepthIndex] .ToString (). Trim (), iTagIndex , icontentIndex; string stratagvalue = drow [itagindex] .tostring (). Trim (); string strcontentValue = drow [icontentIndex] .toString (); // If there is no parent node, join the IF (strrParentInfo == null) {// The current node is not in the HashTable IF (objarrnode [stratagvalue] == null) {// Add the current node TempNode = New Treenode (strContentValue); TempNode. tag = strTagValue; objArrNode.Add (strTagValue, tempNode);}} else // there is a parent node, this time to find whether the parent node is already in the Hashtable {string strParTagValue = strArrParentInfo [0] .Trim (); string strParContentValue = strArrParentInfo [1] .trim (); // Parent Node Has in HashTable IF (Objarrnode [StrPartagValue]! = Null) {// The current node is not in HashTable IF (objarrnode [stratagvalue] == null) {tempnode = new Treenode ( strContentValue); tempNode.Tag = strTagValue;} else {// removed and the node is removed, and then inserted into the parent node tempNode = new TreeNode (); tempNode = (TreeNode) objArrNode [strTagValue]; objArrNode.Remove (strTagValue);} // inserted into the parent node TreeNode tempParNode = new TreeNode (); tempParNode = (TreeNode) objArrNode [strParTagValue]; tempParNode.Nodes.Add (tempNode); objArrNode [strParTagValue] = tempParNode;} else // parent node is not the Hashtable {// Current node is not in HashTable IF (objarrnode [stratagvalue] == null) {TEMPNODE = New Treenode (StrContentValue); TempNode.tag = strtagvalue;} else {// Remove and remove the node, then inserted into the parent TempNode = New Treenode (); tempnode = (Treenode) objarrnode [start.remove (straggvalue); // Create the parent node and the current node is inserted into the parent node TreeNode tempParNode = new TreeNode (strParContentValue); tempParNode.Tag = strParTagValue; tempParNode.Nodes.Add (tempNode); objArrNode.Add (strParTagValue, tempParNode);}}} #ENDREGON / / There is no traveled layer if (icudeplen> iMindeplen) {CollectNodes (dssource, itagindex, icontent "} /// IF (DV.count <= 0) {RETURN NULL;} else {string [] strarr = {DV [0] [itagindex] .tostring (), DV [0] [icontent ", DV [0] .tostring () [IdePTHINDEX] .tostring ()}; return strarr;}} /// /// Return iMin;} }} -----------
