Shulou(Shulou.com)06/03 Report--

We learned about sorting earlier, and starting today, we'll learn about trees in data structures. So what is a tree? Tree is a kind of nonlinear data structure.

A tree is a finite set of n (n > = 0) nodes. If n = 0, it is called an empty tree; if n > 0, then: a > has a specific node called root; b > root nodes have only direct successors but no direct precursors; c > nodes other than roots are divided into m (m > = 0) disjoint finite sets T0, T1, … Tm-1, each set is a tree and is called a sub tree of the root. Let's take a look at the schematic diagram of the tree, as shown below

Let's take a look at the concept of moderate tree. It refers to the degree that a node in a tree contains a data and several branches that point to a subtree, and the number of a single subtree is called the degree of nodes. A node with degree 0 is called a leaf node, and a node with a degree not equal to 0 is called a branch node. The degree of the tree is defined as the maximum moderate value of all nodes. Let's look at an example of a number with a degree of 3, as shown in the following figure.

Come down and introduce the forerunners and successors in the tree. The direct successor of the node is called the child of the node, and accordingly, the node is called the child's parents; the child of the node. It is called the descendant of the node, and accordingly, the node is called the ancestor of the descendant; the children of the same parents are called brothers to each other. Let's take a look at the schematic diagram of the front and follow-up structure of the tree.

Let's take a look at the hierarchy of nodes in the tree, as shown in the following figure

Trees also have order. What is the order of trees? If the subtrees of the nodes in the tree are ordered from left to right and the positions of the subtrees cannot be exchanged, the tree is called an ordered tree, otherwise it is an unordered tree. The schematic diagram is shown below.

So since there is the concept of tree, there must be the concept of forest. A forest is a collection of n (n > = 0) disjoint trees. Then there must be some common operations in the tree, as follows

1. Insert elements into the tree

2. Delete the element from the tree

3. Get the number of nodes of the tree

4. Get the height of the tree

5. Get the degree of the tree

6. Clear the elements in the tree

7 、.

The class relationship between trees and nodes can be expressed as follows

So let's come down and see how the concrete source code of the tree and node abstract class is written.

Tree.h source code

# ifndef TREE_H#define TREE_H#include "TreeNode.h" # include "SharedPointer.h" namespace DTLib {template

< typename T >

Class Tree: public Object {protected: TreeNode* massively rootworthy public: Tree () {m_root = NULL;} virtual bool × × × ert (TreeNode* node) = 0; virtual bool × × × ert (const T & value, TreeNode* parent) = 0; virtual SharedPointer

< Tree >

Remove (const T & value) = 0; virtual SharedPointer

< Tree >

Remove (TreeNode* node) = 0; virtual TreeNode* find (const T & value) const = 0; virtual TreeNode* find (TreeNode* node) const = 0; virtual TreeNode* root () const = 0; virtual int degree () const = 0; virtual int count () const = 0; virtual int height () const = 0; virtual void clear () = 0;} # endif / / TREE_H

TreeNode.h source code

# ifndef TREENODE_H#define TREENODE_H#include "Object.h" namespace DTLib {template

< typename T >

Class TreeNode: public Object {public: t value; TreeNode* parent; TreeNode () {parent = NULL;} virtual ~ TreeNode () = 0;}; template

< typename T >

TreeNode::~TreeNode () {}} # endif / / TREENODE_H

Let's take a look at how the storage structure of trees and nodes is designed. The structure diagram is as follows.

Design points: 1, GTree is a general tree structure, each node can have multiple successor nodes; 2, GTreeNode can contain any number of pointers to successor nodes; 3, to achieve all the operations of the tree structure (add, delete, query, etc.).

The implementation framework of GTree (Universal Tree structure) is shown in the following figure

Let's take a look at how the general tree structure (framework) is created. The source code is as follows

GTree.h source code

# ifndef GTREE_H#define GTREE_H#include "Tree.h" # include "GTreeNode.h" namespace DTLib {template

< typename T >

Class GTree: public Tree {public: bool × × × ert (TreeNode* node) {bool ret = true; return ret;} bool × × ert (const T & value, TreeNode* parent) {bool ret = true; return ret;} SharedPointer

< Tree >

Remove (const T & value) {return NULL;} SharedPointer

< Tree >

Remove (TreeNode* node) {return NULL;} GTreeNode* find (const T & value) const {return NULL;} GTreeNode* find (TreeNode* node) const {return NULL;} GTreeNode* root () const {return dynamic_cast (this- > m_root);} int degree () const {return 0 } int count () const {return 0;} int height () const {return 0;} void clear () {this- > m_root = NULL;} ~ GTree () {clear ();}};} # endif / / GTREE_H

GTreeNode.h source code

# ifndef GTREENODE_H#define GTREENODE_H#include "Tree.h" namespace DTLib {template

< typename T >

Class GTreeNode: public TreeNode {public: LinkList child;};} # endif / / GTREENODE_H

In the design of the tree, why should we include a pointer to the precursor node in each tree node? From the root node to the leaf node is a nonlinear data structure, but from the leaf node to the root node is a linear data structure (linked list). The results are as follows

Next, let's implement the search, insertion and other operations above one by one.

1. Find operation

There are two ways to search: a > search based on the value of data elements: GTreeNode* find (const T & value) const;b > search based on nodes: GTreeNode* find (TreeNode* node) const.

A > based on the lookup of data element values, we first define the find (node, value) function in the protected attribute, and find the node where value is located in the tree with node as the root node. The implementation idea is as follows

B > based on the node search, or define the find (node, obj) function in the protected attribute, and find out whether the obj node exists in the tree with node as the root node. The implementation idea is as follows

Find the relevant source code and implement it as follows

# ifndef GTREE_H#define GTREE_H#include "Tree.h" # include "GTreeNode.h" namespace DTLib {template

< typename T >

Class GTree: public Tree {protected: GTreeNode* find (GTreeNode* node, const T & value) const {GTreeNode* ret = NULL; if (node! = NULL) {if (node- > value = = value) {return node;} else {for (node- > child.move (0) ! node- > child.end () & & (ret = = NULL); node- > child.next () {ret = find (node- > child.current (), value);} return ret;} GTreeNode* find (GTreeNode* node, GTreeNode* obj) const {GTreeNode* ret = NULL If (node = = obj) {return node;} else {if (node! = NULL) {for (node- > child.move (0);! node- > child.end () & & (ret = = NULL) Node- > child.next () {ret = find (node- > child.current (), obj);} return ret;} public: GTreeNode* find (const T & value) const {return find (root (), value) } GTreeNode* find (TreeNode* node) const {return find (root (), dynamic_cast (node));} GTreeNode* root () const {return dynamic_cast (this- > m_root);}};} # endif / / GTREE_H

2. Insert operation

There are two ways to insert: a > insert new node: bool × × ert (TreeNode* node); b > insert data element: bool × × ert (const T & value, TreeNode* parent).

So how do you specify the location of the new node in the tree? Problem analysis: a > tree is nonlinear and can not locate data elements in the form of subscript; b > each tree node has a unique precursor node (parent node); c > therefore, the precursor node must be found before the insertion of the new node can be completed.

A > insert of the new node, as shown in the following figure

The process of inserting a new node is shown in the following figure

B > insert data elements, as shown in the following figure

Let's take a look at how the source code is implemented.

# ifndef GTREE_H#define GTREE_H#include "Tree.h" # include "GTreeNode.h" # include "Exception.h" namespace DTLib {template

< typename T >

Class GTree: public Tree {public: bool × × ert (TreeNode* node) {bool ret = true; if (node! = NULL) {if (this- > m_root = = NULL) {node- > parent = NULL; this- > m_root = node } else {GTreeNode* np = find (node- > parent); if (np! = NULL) {GTreeNode* n = dynamic_cast (node); if (np- > child.find (n)

< 0 ) { np->

Child. × × ert (n);}} else {THROW_EXCEPTION (INvalidOPerationException, "Invalid parent tree node...");} else {THROW_EXCEPTION (InvalidParameterException, "Parement node cannot be NULL...") } return ret;} bool × × ert (const T & value, TreeNode* parent) {bool ret = true; GTreeNode* node = GTreeNode::NewNode (); if (node! = NULL) {node- > value = value; node- > parent = parent; × × ert (node) } else {THROW_EXCEPTION (NoEnoughMemoryException, "No memory to create new tree node...");} return ret;}};} # endif / / GTREE_H

Let's write some test code to see if the previously implemented find and insert code is correct.

# include # include "GTree.h" using namespace std;using namespace DTLib;int main () {GTree t; GTreeNode* node = NULL; t. Xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxert ('GTree, node); t. Xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx T. Xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx T. Xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx Clear the tree with node as the root node, and release each node in the tree. The idea of implementation is as follows

The specific source code implementation is as follows

# ifndef GTREE_H#define GTREE_H#include "Tree.h" # include "GTreeNode.h" namespace DTLib {template

< typename T >

Class GTree: public Tree {protected: void free (GTreeNode* node) const {if (node! = NULL) {for (node- > child.move (0);! node- > child.end (); node- > child.next ()) {free (node- > child.current ());} delete node } public: void clear () {free (root ()); this- > m_root = NULL; m_queue.clear ();} ~ GTree () {clear ();}};} # endif / / GTREE_H

The test code is as follows

# include # include "GTree.h" using namespace std;using namespace DTLib;int main () {GTree t; GTreeNode* node = NULL; GTreeNode root; root.value = 'Agar; root.parent = NULL; t. × × × ert (& root); node = t.find (' A'); t. × × × ert ('baked, node); t. × × × ert (' Che, node); t. × × ert ('Downs, node) Node = t.find ('B'); t. Xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx Node = t.find ('D'); t. Xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx } # endif / / GTREENODE_H

Judge node- > flag () outside during the above delete node operation. If it is true, we will delete it again. As a convenient example, let's add a debug statement to this block, and then an else statement, which prints the data elements of different storage areas. Let's take a look at the results.

We see that all the remaining data elements have been cleared except for the A we specified on the heap.

4. Delete operation

There are also two ways to delete: a > deletion based on the value of data elements: SharedPointer

< Tree >

Remove (const T & value); b > Node-based deletion: SharedPointer

< Tree >

Remove (TreeNode* node)

Delete operation member function design points: 1, delete the subtree represented by the deleted node; 2, delete the function to return a heap space tree; 3, the specific return value is only the pointer object pointing to the tree. The deletion of nodes in the tree is shown in the following figure

If we need to return objects in the heap from a function, use the smart pointer (SharedPointer) as the return value of the function. The definition of delete operation function: void remove (GTreeNode* node, GTree*& ret); delete the subtree with node as the root node from the original tree, and ret is returned as a subtree (ret points to the tree object in the heap space). The idea of deleting a function is as follows

The specific source code implementation is as follows

# ifndef GTREE_H#define GTREE_H#include "Tree.h" # include "GTreeNode.h" # include "Exception.h" namespace DTLib {template

< typename T >

Class GTree: public Tree {protected: void remove (GTreeNode* node, GTree*& ret) {ret = new GTree (); if (ret! = NULL) {if (root () = = node) {this- > m_root = NULL } else {LinkList& child = dynamic_cast (node- > parent)-> child; child.remove (child.find (node)); node- > parent = NULL;} ret- > m_root = node } else {THROW_EXCEPTION (NoEnoughMemoryException, "No memory to create new tree...");}} public: SharedPointer

< Tree >

Remove (const T & value) {GTree* ret = NULL; GTreeNode* node = find (value); if (node! = NULL) {remove (node, ret); m_queue.clear ();} else {THROW_EXCEPTION (InvalidParameterException, "Can not find the node via parament value...");} return ret } SharedPointer

< Tree >

Remove (TreeNode* node) {GTree* ret = NULL; node = find (node); if (node! = NULL) {remove (dynamic_cast (node), ret); m_queue.clear ();} else {THROW_EXCEPTION (InvalidParameterException, "Parament node is invalid...");} return ret };} # endif / / GTREE_H

Let's write some test code, delete subtree D, and the test code is as follows

# include # include "GTree.h" using namespace std;using namespace DTLib;int main () {GTree t; GTreeNode* node = NULL; GTreeNode root; root.value = 'Agar; root.parent = NULL; t. × × × ert (& root); node = t.find (' A'); t. × × × ert ('baked, node); t. × × × ert (' Che, node); t. × × ert ('Downs, node) Node = t.find ('B'); t. Xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx Node = t.find ('D'); t. Xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxert ('node); node = t.find (' H`); t. × × xxxxxxxxxxxxx

< Tree >

P = t.remove (t.find ('D')); t.remove (t.find ('D')); const char* s = "KLFNMIJ"; for (int itree; I tree number of nodes, function definition: count (node); count the number of nodes in the tree with node as the root node, the implementation idea is as follows

An example of calculating the number of nodes of a tree is as follows:

B > height of the tree. Function definition: height (node). Get the height of the tree with node as the root node. The idea of implementation is as follows

An example of height calculation for a tree is as follows:

C > degree of the tree, function definition: degree (node); get the degree of the tree with node as the root node, the idea of implementation is as follows

An example of degree calculation of a tree

Let's take a look at the specific source code implementation.

# ifndef GTREE_H#define GTREE_H#include "Tree.h" # include "GTreeNode.h" # include "Exception.h" namespace DTLib {template

< typename T >

Class GTree: public Tree {protected int count (GTreeNode* node) const {int ret = 0; if (node! = NULL) {ret = 1; for (node- > child.move (0);! node- > child.end (); node- > child.next ()) {ret + = count (node- > child.current ()) }} return ret;} int height (GTreeNode* node) const {int ret = 0; if (node! = NULL) {for (node- > child.move (0);! node- > child.end (); node- > child.next ()) {int h = height (node- > child.current ()) If (ret

< h ) { ret = h; } } ret = ret + 1; } return ret; } int degree(GTreeNode* node) const { int ret = 0; if( node != NULL ) { ret = node->

Child.length (); for (node- > child.move (0);! node- > child.end (); node- > child.next () {int d = degree (node- > child.current ()); if (ret)

< d ) { ret = d; } } } return ret; }public: int degree() const { return degree(root()); } int count() const { return count(root()); } int height() const { return height(root()); }};}#endif // GTREE_H 测试代码如下 #include #include "GTree.h"using namespace std;using namespace DTLib;int main(){ GTree t; GTreeNode* node = NULL; GTreeNode root; root.value = 'A'; root.parent = NULL; t.×××ert(&root); node = t.find('A'); t.×××ert('B', node); t.×××ert('C', node); t.×××ert('D', node); node = t.find('B'); t.×××ert('E', node); t.×××ert('F', node); node = t.find('E'); t.×××ert('K', node); t.×××ert('L', node); node = t.find('C'); t.×××ert('G', node); node = t.find('G'); t.×××ert('N', node); node = t.find('D'); t.×××ert('H', node); t.×××ert('I', node); t.×××ert('J', node); node = t.find('H'); t.×××ert('M', node); cout 访问队头元素指向的数据元素；iii. next() -->

The header element pops up and presses the children of the opposite element into the queue (core); iv. End ()-- > determines whether the queue is empty. Examples of hierarchical traversal algorithms are as follows

Let's take a look at the specific source code implementation.

GTreeNode.h source code

# ifndef GTREENODE_H#define GTREENODE_H#include "Tree.h" # include "LinkList.h" namespace DTLib {template

< typename T >

Class GTreeNode: public TreeNode {protected: bool masks; GTreeNode (const GTreeNode&); GTreeNode* operator = (const GTreeNode&); void* operator new (unsigned int size) throw () {return Object::operator new (size);} public: LinkList child; GTreeNode () {m_flag = false;} bool flag () {return m_flag } static GTreeNode* NewNode () {GTreeNode* ret = new GTreeNode (); if (ret! = NULL) {ret- > m_flag = true;} return ret;}};} # endif / / GTREENODE_H

GTree.h source code

# ifndef GTREE_H#define GTREE_H#include "Tree.h" # include "GTreeNode.h" # include "Exception.h" # include "LinkQueue.h" namespace DTLib {template

< typename T >

Class GTree: public Tree {protected: LinkQueue masked queue; GTree (const GTree&); GTree* operator = (const GTree&); public: GTree () {} bool begin () {bool ret = (root ()! = NULL); if (ret) {m_queue.clear (); m_queue.add (root ()) } return ret;} bool end () {return (m_queue.length () = = 0);} bool next () {bool ret = (m_queue.length () > 0); if (ret) {GTreeNode* node = m_queue.front (); m_queue.remove () For (node- > child.move (0);! node- > child.end (); node- > child.next () {m_queue.add (node- > child.current ());}} return ret;} T current () {if (! end ()) {return m_queue.front ()-> value } else {THROW_EXCEPTION (InvalidParameterException, "No value at current position...");};} # endif / / GTREE_H

Then the corresponding queue clearance should be added to the operation of remove: m_queue.clear (); the test code is as follows

# include # include "GTree.h" using namespace std;using namespace DTLib;int main () {GTree t; GTreeNode* node = NULL; GTreeNode root; root.value = 'Agar; root.parent = NULL; t. × × × ert (& root); node = t.find (' A'); t. × × × ert ('baked, node); t. × × × ert (' Che, node); t. × × ert ('Downs, node) Node = t.find ('B'); t. Xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx Node = t.find ('D'); t. Xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxert ('t.find,' D`); t. × × × ert ('Hou, node)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.