Tree Editor

Yossi Patt

4.94/5 (38 votes)

Dec 10, 2003

15 min read

280998

12623

A fully-editable Tree Editor

Introduction

The Tree control is one of the most useful windows controls. Using a single control, it's possible to display any structured information. However, modifying a complex tree programmatically is not straightforward.

This Tree Editor attempts to help programmers to develop Tree Control based applications. Apart from this, it can be used as a stand-alone application to create, modify, load and save any data for which the tree structure applies. Sometimes, people use graphic tools for such purpose. These tools are rather inappropriate. They require complex manipulations to define a node and draw lines between nodes. This Tree Editor provides the user with simple commands (add child, add sibling) to edit a tree quickly. The possibility of importing/exporting trees (using a file or the clipboard) to other programs such as Notepad, as a sheet in Microsoft Excel ® or a table in Microsoft WORD permits alternatively to use these software to enter data to the tree, and to turn then to Tree Editor to modify it, and/or to integrate it to an application based on the Tree Control.

References

Aside from the MSDN samples and some VISUAL C++ books, I used (and modified to my needs) code from several articles published in "The Code Project". I am mostly thankful to the code authors. These articles are:

More information on subjects developed in this article can be found in:

How to use TREE EDITOR

Cursor Functions
	Scan the tree (Up/Down Arrow)
	Scroll (Ctrl +Up/Down Arrow)
	Scan the tree while expanding/collapsing nodes (Right/Left Arrow)
Edit Nodes	F2
Move/Copy Branches
	Using Drag and Drop
		Allow scrolling while dragging	For big trees
	Using Keyboard
		Copy selected item (Ctrl+C)
		Cut selected item (Ctrl+X)
		Paste as a son of selected item (Ctrl+V) or as a new root (Ctrl+Shift+V)	Multiple Ctrl+V (or Ctrl+Shift+V) can be done for a single Ctrl+C or Ctrl+X
		Paste above selected item (Ctrl+A)	Multiple Ctrl+V (or Ctrl+Shift+V) can be done for a single Ctrl+C or Ctrl+X
Add items
	Add Child (Insert)
	Add Sibling (= brother or sister) (Space bar or Return)
Delete
	Delete Selected item (Del)
	Delete Entire Tree (Ctrl+Del)
Multi Formats supported
	Comma Separated Values		Recommended to import/export to other programs
		Example	See reference for more details about CSV Format
		1,,
		,2,
		,,3
		,,4
		,5,
		Separation character may be:
			Comma (default when dragging a CSV file from Explorer)
			Tab (Used to copy/paste from the Clipboard - See Ctrl+Ins, Shift+Ins)
			Any printable character. (Ctrl+D for instance: Load tree directory uses the Left Slash ('/') character as a delimiter character. Paths such as: d:/dir/subdir1/subdir2 are "almost" CSV records. With a slight modification inside the program, they become "totally" so)
	Indent format	(Input only)	To input from Mind Manager ®. To export to Mind Manager, use the clipboard
		Example
		1. 1
		1.1 2
		1.1.1 3
		1.2 4
		1.2.1 5
		1.3 6
		1.3.1 7
		1.3.2 8
	Tre Format	Main Format of Tree Editor	See details below
Allow Export/Import to/from
	Microsoft Excel ® Sheet	Use Clipboard (Ctrl+Ins/ Shift+Ins recommended) or CSV format
	Microsoft WORD ®, Workpad, Notepad or any other software that recognized CSV format	Use Clipboard (Ctrl+Ins/ Shift+Ins recommended) or CSV format. Inside Word, use Table > Convert Text to table/Table to Text
	Allow Copy/Paste from Clipboard
		Copy Entire Tree to Clipboard (Ctrl+Ins)
		Paste Entire Tree from Clipboard (Shift+Ins)
	Open File
		Using Open Menu or Open recent files
		Can drag files from Explorer
		Can add the file name as an Command-line argument
		Support defining of File associations for tre, csv, idt
		Build a directory tree (Ctrl+D)
			Displays the tree only
			Useful to test the program on big trees
	Save file (Ctrl+S)
		Save
		Save as
	Sort Entire Tree
		Alphabetic (Ctrl+T)
		Numeric (Ctrl+Shift+T)
	Calculate the level of a node (Ctrl+L)
	Popup Menu
		Expand all items
		Collapse all items
		All functions seen so far are also accessible through Popup Menu

Note about Edit Mode

When a node is being edited:

ESC Exits Edit Mode with no change
END Validates the changes and exits Edit Mode
INS Validates the changes, add a new sibling, and stays in Edit Mode. Thus, it's possible to press a first time INS and then to insert several children to the same parent, pressing INS after each child has been entered, and this without having to exit edit mode.
Dropping an item to a node in the dragged item SubTree is not allowed. However, we do allow this if the user uses the keyboard functions instead.

Note about Drag and Drop

When drag and drop is used to move/copy and paste items (not to be confused with dragging a file from Explorer to open it):

If the F3 key function is pressed (no matter where the mouse pointer is), then the cursor turns to an arrow with the letter "R", (A cursor indicating COPY if Ctrl is pressed ("+"), or MOVE else. If the mouse is released then, the item will be copied or moved accordingly as a new root, no matter where the mouse pointer was at dropping time.
If the mouse pointer is on the right of an item, the cursor turns to a Right Arrow (A cursor indicating COPY if Ctrl is pressed, or MOVE else. If the mouse is released then, the item will be copied or moved accordingly as a son of the dropped item.
If the mouse pointer is on an item or at its left, the cursor turns to an UP Arrow (A cursor indicating COPY if Ctrl is pressed, or MOVE else. If the mouse is released then, the item will be copied or moved accordingly as a sibling above the dropped item.

Programming notes

Overview

The application was written in MFC, using a single document architecture (SDI), and the Document / View concept. However, we preferred the classic C file functions (fopen(), fclose(), fread(), fwrite(), fgets(), fputs(), fprintf()) to the serialization mechanism.

Main classes

CTreeEditorApp

InitInstance()

CAboutDlg

CTreeEditorDoc

In response to the menu commands (Open, Save, Save as...), it calls the common dialogs for opening or saving a file.

The open and the save common dialogs have been customized with a dialog template and a hook procedure, to allow adding special controls, related to the CSV format. I used the traditional Win API. I guess I could write these functions in a more elegant manner, using the MFC classes.
To let the user select a path rather than a directory, (in response to Ctrl+D), I used, SHBrowseForFolder() and SHGetPathFromIDList().
To summarize, the proper customized common dialog is called in response to a menu command. When it returns the user selection, it calls: UpdateAllViews(NULL, lHint). The "lHint" parameter tells the CTreeEditorView class what operation to perform (New? Open/Save? Which file? In which format?)

CTreeEditorView

CView

CEditTreeCtrl

CTreeView

CTreeCtrl

OnCreate() and OnInitialUpdate() initialize the tree control
OnUpdate() transforms the request from the document class, to instructions to the CEditTreeCtrl class.

CTreeType

We must call the member function AllocateTree(count) before using a CTreeType structure. "count" is the maximum number of nodes that can contain the CtreeType structure. As we need also one node for the "imaginary root" (See explanations about the "tre" format below), count+1 nodes of type NODE_TYPE are allocated.
DeallocateTree() can be called to deallocate the CTreeType structure, when it's not needed anymore.

CMainFrame

CMainFrame

CEditTreeCtrl

CTreeCtrl.

Note about Exceptions:

The "tre" format

This is the format that we defined for this application.
The definition of this format can be found in class CTreeType (see TreeType.h)
It contains the number of items in the whole tree, followed by a structure of NODE_TYPE format (also defined in TreeType.h) for each node.
The nodes are defined in DFS (Depth First Search) order.
For each node, the NODE_TYPE defines:
WORD wNbItems; The number of children
WORD wBufSize; The size of buf
char *buf; The text of the node
HTREEITEM hti; A reference to HTREEITEM in the tree control
UINT uState; The state of the node (Expanded/Collapsed)

Below is an example of a tree along with its representation in the "tre" format (excluding hti, wBufSize and uState).

Index	Number of Children	Text
0	2	NULL
1	2	"1"
2	0	"2"
3	0	"3"
4	2	"4"
5	2	"5"
6	0	"6"
7	0	"7"
8	0	"8"

Remarks

"1" and "4" are both at the root level. Formally, a root cannot have siblings. But we can see this forest (set of trees) as a tree, if we consider all the "roots" as sons of an imaginary root. That is exactly what we do in the "tre" format. In our case, the imaginary root has 2 children ("1" and "4"). If the root of the Tree Control had only one root, then our imaginary root would had had only one children.

As we said previously, the text of the buffer is in the field *buf, its size is given by wBufSize.
This has two advantages over allocating a fixed size (say 256 bytes) to each node:

Saving disk space
Allowing to extend this format for more complex application, in which *buf will be a pointer to a structure, containing other information than the text displayed in the node.

The two most important functions are:

BOOL LoadTreeDataR(CTreeType &tt, HTREEITEM hti, OUTSIDE_PARAM op)
BOOL SaveTreeData(CTreeType &tt, HTREEITEM hti, OUTSIDE_PARAM op)</li>
As their names suggest, LoadTreeDataR (actually a wrapper to LoadTreeData to add some pre-processing and post-processing) loads a tree from a CTreeType structure to a tree control, while SaveTreeData saves a tree from the Tree Control to a CTreeType structure.

The "CSV" format

The description of this format can be found in the reference given at the beginning of this article. (Not all the characteristics of the CSV format are implemented, for example we don't handle leading and trailing blanks and we don't consider separator characters enclosed by brackets). In addition to the comma separator, we allow using of the TAB character (0x09), and of any printable characters as separator characters.

Following is the tree given in the previous example, in CSV format, using comma as the separator character.

To Import a file from Microsoft Excel ® in CSV format

Using the clipboard: Press Ctrl+Ins in TreeEditor, then Ctrl+V in Excel

Using the Save menu: Save file in TreeEditor with extension CSV, using comma as the delimiter. Select Open File in Excel. Option "delimited with comma"

To Export a file from Microsoft Excel ® in CSV format

The file is exported in CSV format using TAB as the delimiter. To make it work, the cells in Excel must represent a valid tree. A valid tree is one in which the level can decrease, remain the same or increase by 1.

Using the save menu: Select "Save as" in Excel, giving the CSV extension. Answer "Yes" to any warning. Open the file in TreeEditor with the CSV extension.

To Import/Export a file from Notepad in CSV format

The simplest way is to use the clipboard

To Import/Export a file from Microsoft Word ® in CSV format

Use the clipboard or build a WORD table, select it and then use Convert Table to/from text using comma as the delimiter character.

The IDT format

This format is used by Mind Manager (More about Mind Manager can be found below and in the link given in reference)
In this format, the tree are prefixed by their indentation level, followed by the TAB character.

Following is the tree given in the previous example, in IDT format.

1. 1
1.1 2
1.2 3
2. 4
2.1 5
2.1.1 6
2.1.2 7
2.2 8

Note: Record which do not contain an indentation level are ignored.

To import a file from Mind Manager

In MindManager:

Select: Format>Text Output
Select Text Outline Tab
Clear check box "Display notes"
Clear check box "Use bullets"
Display until level: 40
Number until level: 40
Indent until level: 40
Press OK

Then:

Select File>Export>File
Select Text Outline
Select a path
Press OK

Change the extension from txt to idt

Applications

Trees are used in a variety of applications. This Tree Editor can be used for example in the following cases:

To load/save/edit Hierarchies, classifications, decision trees (by the way a genealogical tree is not a tree in the sense we use it)
To organize ideas. It's amazing how summarizing a book, an article or a memorandum can make things much clearer. A text contains many connection words and connection sentences, that mask the main ideas. For instead: words, words, words So, to make our purpose clearer, words, words, words, and as we said previously (What on earth did they say previously, I was sleeping when I read it!). Using a tree, we can see at a glance what the main ideas are.

Brainstorming

It is based on a classic but great idea on how to find new ideas?

In "Brainstorm mode", the software asks part or all the basic questions (The option menu let us defining our precise needs), along with the basic relational operators for the current branch.
The nine basic questions are:

When? (Position in time)
Where? (Position in space)
How much / How many? (Quantification)
Which? (To select one out of many)
What? (The object)
Who? (The subject)
How? (The means)
Why? (=> The reasons)
What for? (The consequences =>)

AND
OR
NOT
(XOR can be added eventually)

The idea is to ask these questions recursively.

Example: I plan a meeting. The questions asked by the software suggest me to ask:

WHAT is the main object of this meeting?
AND WHAT ELSE...
AND WHAT ELSE...

WHEN will be the meeting?

Let's ask the basic questions RECURSIVELY on the ANSWER to that question:
WHY to choose that date?
And WHY NOT to choose it? (pros/cons),
and WHAT OTHER (= OR) date is possible? (Choose alternatives)
WHO will be the guests?

Let's detail:
WHY this guest?
and WHY NOT this one?, etc, etc.

I have used this method for years and it helps me a lot. Using this method, you can make the switch from "no idea at all!" to "too many ideas!".

Mind Maps

In general, Trees (along with images) are very useful to represent ideas. The classic book in this domain was written by Tony Buzan (See reference). Professional tools were develop, following Tony Buzan theory. The best one I know is Mind Manager ® of Mindjet (See reference)

Computer Tree-oriented applications

The tree is a very useful data type in computing. For organizing files in directories, for sorting and searching (especially binary trees), for organizing Data Bases, and to design general-purpose data entry (as in Outlook, Explorer, and Visual Studio).