A few days ago, I wrote an article about binary tree and traversal. The reason is to see some discussion is keen to study how to give a linear Ireator for a binary tree.
As a result, the article came out, because I originally wanted to talk, and 9CBS post code is too bad, no one understands me.
However, through discussion on AllaboutProgram and the paper crash, I found that this thing is worth writing anyway. I understand that it is very beneficial to understand the interface, concept rather than design ideas.
You are interested in http://www.allaboutprogram.com/bb/viewtopic.php?t=629 to see code and specific discussion. There is also the design of Iterator, which is independent of any binary tree, has also been extended to the n fork tree, such as the Iterator.
I will not post the code here. But briefly introduce the idea.
In the post I criticized, study how to do a binary tree in detail, and how to create a linear pre-sequence, order and rear sequence Iterator to this binary tree.
I criticized it because these traversal logics are achieved independent of any binary tree. Stirring the concept between the two mutually coupled, will only be complex.
I mentioned the concept of "independent implementation Iterator" in my article. However, I want to come to this proposal may have different understandings, so it has caused a later quarrel.
Here, I will give an example.
Suppose your boss tells you: Can you be a linear access to the linear access to the binary tree?
You said: No problem. Yes, where is this binary tree code?
Boss: code? Not yet. We will get it in Canada's programmers. But I haven't started writing yet.
You said: Oh. Ok. So do you have a document, or the SPEC's and the like?
Boss: I let you write iterator, and I don't let you write a binary tree. Besides, "Binary Tree", don't you understand? What do you want to do? We may write a binary tree yourself, or you may look at the price of the price from outside, and even if you can mix it and write it yourself. So, there is no document yet.
So, is this demanding implementation?
I want to say that it is fully implemented. In fact, you can even write an Iterator library, implement these traversal logic, and then sell to different trees as additional features. (The premise is that some people will spend money to buy such a simple thing). Or, at least, I can sell my Iterator library to the people who want to give yourself to realize Iterator.
To achieve the traversal logic of these standards, it is not necessary to know the specific implementation of the tree. Just like you can write a sorting algorithm without having to know the specific container.
Why do many STL containers do not provide similar sorting features? It is because these algorithms tend to be independent of the implementation of specific containers. As long as you can provide a random Iterator interface for your container.
Similarly, the linearization of the tree is also achieved independently of the specific tree. As long as you can provide linearization required for your tree.
In the paper crane and my discussion, I applied an Adapter to apply an N-forked traversal logic to the file directory system.
Therefore, in the tree realization, how to linearize how to sort it in the std :: Vector, how to sort it, a bit of the wrong direction.
