These days participated in the discussion of the 9CBS Forum and changed some of my previous opinions. Looking back, I am very dissatisfied with this book, but I still follow it in a little bit of writing; this will lead, I am in the bias of the book, I wrote more It is said that "this book", and deviates from the original intention to write - some help for those who are learning the data structure. Just as I said earlier, although the existing textbook is not very reasonable, if it is just complaining, it is tantamount to the street. Although my level is not enough, I will try at least from me, and the teaching method of this class will have a little bit reasonable.
Therefore, the following is not in accordance with the order in accordance with the order, and the "actual application (algorithm) determine the data structure" thinking, it is common to the common textbook, it is basically no longer a focus (except for the focus, such as the balance of the AVL tree). , - Therefore, while reading this article, it must have a textbook. This is just an attempt, I hope everyone can more valuable comments.
tree
Because this "tree" in the real world, this "tree", the classification, the classification classification, etc., and to study this problem, it is necessary to store the tree, and how to store will depend on the required operation. There is a problem here that it allows an empty tree. Some books believe that the tree is non-empty, because the tree indicates a realistic structure, and 0 is not a natural number; I have used the textbooks that can have a space, of course, for the bifurcation. There is no in principle difference, anything is a habit.
Binary tree
The binary tree can be said to be a model of people's imaginary, so that the spaceless binary tree is not controversial. The binary tree is ordered, and there is a binary tree on the left side of the left. There is a different tree. To do this, it is because people give the left child and the right kids different significance. In various applications of the binary tree, you will see it clearly. Only the chain structure is explained below. Look at all kinds of books, you will find an interesting phenomenon: in the binary tree, the basic operation has the high calculation tree, all kinds of traversal, is not inserted, deleted - how is the tree established? In fact, this is well understood that for non-linear tree structures, inserting deleted operations is not meaningful, it is meaningless. Therefore, there is only an insertion deletion operation only in a specific application.
Node structure
Data domains, left pointers, right pointers are definitely necessary. Unless few parents who use nodes, or resources are tight, it is recommended to attach a double-pro-pointer, which will bring convenience, especially in this "space change time".
Template
Struct btnode
{
BtNode (t data = t (), btnode
: DATA (DATA), LEFT (LEFT), Right (Right), Parent (PARENT) {}
Btnode
T data;
}
Basic binary tree
Template
Class Btree
{
PUBLIC:
BTree (btNode
~ Btree () {makeempty ();
Void makeempty () {destroy (root); root = NULL;}
protected:
BTNode
Void Destroy (btNode
{
IF (p)
{
DESTROY (P-> Left);
DESTROY (P-> Right);
Delete P;
}
}
}
Two-fork tree traversal
There are basically four types of traversal methods, first, middle, and then root, layer-by-layer. I was confused about this, what did you do? It will be understood later, this is a different application needs. For example, it is necessary to determine whether the two binary trees are equal, as long as the substru root node is different, it will not wait, it is obvious to use the order, and delete the binary tree, you must first delete the left and right trees, then you can delete the root node, then It is necessary to use the sequence.
In fact, in so many traversal methods, the root cause is that the tree stored in memory is a nonlinear structure. There are no necessary methods for the binary tree stored with an array. With C packages and overload features, these traversal methods can be clearly expressed.
Pretty sequence traversal
PUBLIC:
Void Preorder (VOID (* VIT) (T & DATA) = Print) {Preorder (root, visit);}
Private:
Void Preorder (BTNode
{
IF (p) {VIT (P-> DATA); Preorder (P-> Left, Visit); Preorder (P-> Right, Visit);
}
2. Sedential traversal
PUBLIC:
Void inorder (T & DATA) = Print) {inorder (root, visit);}
Private:
Void inorder (btNode
{
IF (p) {inorder (P-> Left, Visit); Visit (P-> Data); Inorder (P-> Right, Visit);
}
3. Back sequence traversal
PUBLIC:
Void PostOrder (T & DATA) = Print {PostRDER (root, visit);}
Private:
Void PostOrder (BTNode
{
IF (p) {PostORDER (P-> Left, Visit); PostORDER (P-> Right, Visit); VISIT (P-> Data);
}
4. Hierarchical traversal
Void LevelORDER (Void (* Visit) = Print)
{
Queue
While (p)
{
Visit (P-> DATA);
IF (p-> left) a.push (p-> left); if (p-> right) a.push (p-> right);
IF (a.empty ()) Break; P = a.front (); A.POP ();
}
}
Note: The default Visit function print is as follows
Private:
Static Void Print (T & DATA) {cout << Data << '';} 5. Non-recursive orderless traverses without stack
When there is a Parent pointer, you can do not have a stack to achieve non-recuperated middle-sequence traversal, and this method is mentioned, but it does not give the routine.
PUBLIC:
Btnode
{
IF (! current) return null;
IF (current-> right) {current = current-> Right; while (current-> left) current = current-> left;}
Else
{
BTNODE
While (Y && Current == Y-> Right) {current = y; y = y-> parent;}
Current = Y;
}
Return Current;
}
Private:
BTNODE
The above function allows the Current pointer to move forward, if you want to pass through the entire binary tree, you need to point the current to the first node of the middle sequence, such as the following member function:
PUBLIC:
Void first () {current = root; while (current-> left) current = current-> left;}
