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], TreeView's generation is substantially three ways: 1. The treeView node is populated directly in the TreeView designer or code when designing the interface. This approach generates a tree by dragging and dropping the control, a narrow application range 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, using XML as a general purpose data transfer format has been universally recognized; 3. Get data from the database (in .NET, we can understand a data set) to create a tree structure. 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 TreeView node generation flow diagram algorithm 2: By bottoming upwards (depth) traversal generation tree algorithm L Step 0: Data Preparation, GivenTValue, DepthID, Tagvalue is the actual value of nodes, ContentValue It is the value of the node or the tag value, and the 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. At this time, if a given data set (we put the "R & D Department" and "marketing one" filter out), 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 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 5 Given the data set Then generate trees as 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: [1] Zane Thomas. DataViewTree for Windows Forms, http://www.abderaware.com/whitepapers/ DataReview.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/ color.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. Microsoft.com/?kbid=320755 [6] Scott Mitchell. Displaying XML Data In The Internet Explorer TreeView Control, http: // aspnet. 4guysfromrolla.com/articles/051403-1.aspx ----- . /// public class treeoperty {public Treeoperty () {// // Todo: Add constructor logic //} /// IcurDeplen> /// /// private static void collectnodes (Dataset Dssource, Int ItagIndex, IconDex , int iDepthIndex, int iCurDepLen, int iMinDepLen, ref Hashtable objArrNode) {// collection node System.Data.DataView dv; System.Windows.Forms.TreeNode tempNode; // Find the given node layer int i = iCurDepLen; do {dv = New DataView (dssource.tables [0]); string strexpr = "LEN (Trim (" DSSource.tables [0] .COLUMNS [IdePTHINDEX] .COLUMNNAME ") =" Convert.TOSTRING (i); DV. Rowfilter = strexpr; i-;} while (i> = iMindeplen && Dv.count <= 0); icdeplen = i 1; #Region is backward-backed by layer, collecting node foreach (System.Data.DataRowView DROW IN DV) { // Find the parent node string [] strArrParentInfo = LookupParentNode (dsSource, iDepthIndex, drow [iDepthIndex] .ToString () Trim (), iTagIndex, iContentIndex.); string strTagValue = drow [iTagIndex] .ToString () Trim ().; String strcontentValue = drow [icontent "] .tostring (); // If you don't have a parent node, add IF directly (strarrparentInfo == null) {// this node is not in the Hashtable if (objArrNode [strTagValue] == null) {// add the current node tempNode = new TreeNode (strContentValue); tempNode.Tag = strTagValue; objArrNode.Add (strTagValue, tempNode) }}} Else // has a parent node, first find if the parent node is already in HashTable {string strpartagvalue = strarrparentInfo [0] .trim (); string strparcontentValue = strarrparentInfo [1] .trim (); // Parent node Has been in HashTable (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 Not in HashTable {// The current node is not in HashTable if (objarrnode [stratagvalue] == null) {TempNode = new Treenode (StrContentValue); TempNode.tag = stratagvalue;} else {// Remove and remove the node then inserted into the parent node tempNode = new TreeNode (); tempNode = (TreeNode) objArrNode [strTagValue]; objArrNode.Remove (strTagValue);} // Create a parent node and the current node is inserted into the parent node TreeNode tempParNode = new Treenode (StrParContentValue); tempParnode.tag = strpartagvalue; tempordagvalue; tempordaGvalue (TempNode); objArrNode.Add (strParTagValue, tempParNode);}}} #endregion // there is not traversed layer if (iCurDepLen> iMinDepLen) {CollectNodes (dsSource, iTagIndex, iContentIndex, iDepthIndex, iCurDepLen-1, iMinDepLen, ref Objarrnode);}} /// SUMMARY string array values, and depth values of the composition, otherwise null private static string [] LookupParentNode (DataSet dsSource, int iDepthIndex, string strSubDepth, int iTagIndex, int iContentIndex) {System.Data.DataView dv; int iSubLen = strsuBDepth.length; if (iSUBLEN <= 1) {return null;} int i = 1; do {DV = new data; string strexpr = "Trim (" DSSource.tables [0 ] .Columnns [IdePTHINDEX] .COLUMNNAME ") = '" strsubDepth.substring (0, isublen-i) "'"; dv.rowfilter = strexpr; i ;} while (i
