Section 1 -Introducing General Trees
data structure代写 A tree is a data structure containing nodes that are organized by a parent- child-sibling relationship. There is always
9B.1.1 The Language of Trees data structure代写
A tree is a data structure containing nodes that are organized by a parent- child-sibling relationship. There is always a root node that is at the highest level of the tree (which makes it more of an upside-down tree), and below the root are one or more direct children, each pictorially attached to the root with a line. Each of these children can be the parent of further children, and so on, until you come to some nodes that have no children. These are referred to as leafs or leaf nodes. Here is a picture from a textbook by Nyhoff that summarizes the general structure of a tree.
Every node is the root of a subtree. For example, node 2 is the root of the subtree consisting of it and everything below it (which is the left side of the main tree in the above picture). Node 3 is the root of a small subtree consisting of it and its three children, nodes 5, 6 and 7.
Depth refers to how many levels below the root a node is. A root node,
like node 1 is said to be at depth zero and nodes 8 and 9 would be at depth three.data structure代写
The height of any node tells how many levels, “worst case,” there are below that node (going towards the deepest node). So, the height of node 2 is two, the height of node 1 is three, and the height of node 6 is zero.
If we are discussing the depth of a node in a subtree, we consider its position only in that subtree, not the larger tree. So, in the subtree whose root is node 4, node 4 has depth zero and node 9 has depth one.
Therefore, we see that depth is not an absolute but can change depending on which subtree we are talking about.data structure代写
Height, on the other hand, is independent of the subtree we are considering, because height is measured downward, not upward.
9B.1.2 Example Applications data structure代写
Examples of tree data structures are:
- Thedirectory/folder structure of any operating system like Linux, Mac or Windows.
- Ataxonomic organization of plants or animals by their official names (kingdom, phylum, class, …, genus, species).
- Temporary structures built by your compiler that represent numerical expressions like “(2*x + exp(s – .5) * ( (s + 3)/(s – 2) +sin(x))“.
4.An object in a computer game, such as a zebra or a person. Each movable assembly, like an arm, is the root of a subtree whose children all move together with the root. For example, an arm would have an elbow and forearm as its children. The forearm would have the hand as its child. The hand would havethe five fingers as its five children. data structure代写
Each finger would have a single child for the bone section below When computing motion of the object in the tree, we would move an entire subtree by moving its root, all the other items going along for the ride. If, in addition to the arm movement, the thumb also moves, we have to combine the two movements to determine theresultant position of the thumb. Computer animation and real-time simulation programmers deal with this in great detail.
5.Linguistic phrase structure of a sentence can be organizedlike a tree,data structure代写
with each phrase containing sub- phrases. This would be used in determining the meaning of the sentence in a translation or speech comprehension Programmers who work with artificial intelligence and language use these sorts of trees.data structure代写
6.A program that locates, orders and track parts of acar would be a candidate for a tree data structure.
- Most data structures that require fast access and sorting are built using trees. For instance, we’ll see thatmany of our current or future data structures such as maps, sets, and priority queues all use trees as their underlying
Of the above list, items 3, 5 and 7 differ from the others. They show a tree as a means, not an end. As with all data structures, we sometimes use a tree because it is helpful to solve a problem (search, sort, etc.), not because we really have an intrinsic set of data in that particular form. Bullet items 1, 2, 4 and 6 have data that must be stored somewhat permanently, and the tree really is the structure of the data. Items 3, 5 and 7 will create the structures just to make something else work, not because the data really is in a tree form, intrinsically.data structure代写
9B.1.3 General Tree Design Strategy
In the study of tree data structures, one inevitably begins with the most
general and ill-behaved type of tree. It is so ill-behaved, it doesn’t even have a name. We just call it a general tree, or tree, and reserve all the cool terms (like binary search tree, AVL tree, etc.) for certain sub-types that have structures which make specialized operations easier to implement. But the general tree, as wild and challenging as it is, is worth studying because sometimes that’s what we’re handed, and we need to have a plan for how to face it. And it does, after all, represent many of the types of applications listed above.data structure代写
This most general tree can have nodes with variable numbers of children. Here is such a tree, in its logical from:
(Yes, I know — there’s no Node O. That’s to avoid confusion with the number
“0”).data structure代写
If I were to ask you to implement a tree data structure that supported some of the typical operations like addChild(), removeNode(), find() and printAll(), I would probably get some interesting and creative answers.
Some such solutions might attempt to define a TreeNode with an array list of pointers to children. If a TreeNode had three children, we might allocate an array list of three child TreeNodes. Of course when we added or deleted children, we would have to resize the array list.
There is, however,data structure代写
a smarter and more accepted technique for lashing up these beasts which is quite flexible and more efficient than the array list approach. It entails giving each TreeNode a structure that is a fixed, small size: each node consists of a data member plus three references. The member rferences are firstChild, sib and prev (the last two meaning next sibling and previous item, respectively). This would cause the above logical tree to be stored, internally, in the following manner:
The diagram only shows the firstChild and sib connections.data structure代写
The prevconnections will be described now. Consider a few of the nodes above:
- TreeNode A: firstChild points to B, sib is null and prev is null
- TreeNode C: firstChild is null, sib points to D and prev points to B
- TreeNode K: firstChild is null, sib points to L and prev points to F
- TreeNode H: firstChild is null, sib is null and prev points to D
So you see, we’ll need three “next-like” member references compared with the one next of our list nodes. The references will be, as shown, firstChild, sib and prev. Also, notice that prev serves double duty: it will point either to the parent or the left sibling, since a tree node can’t have both at once (in this internal structure). Finally, notice that the only node in the tree with a prev == null is the root node.data structure代写
更多其他：C++代写 考试助攻 C语言代写 finance代写 lab代写 计算机代写 report代写 project代写 物理代写 数学代写 经济代写 java代写 python代写 程序代写
