When we search for an integer among n dynamic integers, there are several methods

① Using dynamic arrays, the average time complexity is O(n)

② Using an ordered dynamic array and binary search method, although its worst time complexity is only O(logn), its average time complexity of addition and depth is too high, which is O(n).

③ Using a linked list is not much different from using a dynamic array. You need to start searching from the first element. The average time complexity is also O(n), which is too high.

Therefore, we consider whether there is a more optimized policy

Next, the binary search tree is introduced, which arranges the data in order. The worst complexity of the search is O(logn), because the worst time complexity of the methods of data connection, addition and deletion in the linked list is also optimized to O(logn).

Binary Search Tree is a kind of binary tree, abbreviated as BST, also known as Binary Search Tree and binary sort tree. Its characteristics are: ① the value of any node is greater than that of all nodes in its left subtree

② The value of any node is less than that of all nodes in its right subtree

③ Its left and right subtrees are also a binary search tree

The first is the creation of binary search tree. We use template to make the code more complete. Any type of data can be put into the search tree.

In the creation of the node, the parent node is added on the basis of the element and the left and right child nodes, and the implementation of the following code. In the member function, the functions of whether it is a leaf node and whether there are two child nodes are also added. Because these judgments are more used in later applications, they are encapsulated.

In the establishment of binary search tree, only the number of elements and root node are used, and the whole code can be implemented completely. The implementation of member functions is divided into two parts. One is object-oriented, and the functions placed in the public area are used by objects. The other is to better implement the function encapsulation and put them in the private area.

The binary search tree in this paper adds four traversal methods: pre order, middle order, follow-up and sequence in addition to the most basic addition, deletion, number of elements, whether it is empty, emptying and search. The height of the binary tree is calculated by using recursive and iterative algorithms, and the implementation of checking whether it is a complete binary tree is completed.

Here is binarysearchitree H code.

#pragma once #include <iostream> #include <queue> using namespace std; template<typename E> class Node //Create node { public: E element; Node<E> *left; Node<E> *right; Node<E> *parent; Node(E element, Node<E>* parent) //Constructor { this->element = element; this->parent = parent; left = NULL; right = NULL; } bool Check_Is_Leaf()//Check whether it is a leaf node { return left == NULL && right == NULL; } bool Is_Has_TwoChildren() //Do you have two child nodes { return left != NULL && right != NULL; } ~Node() {} //Destructor }; template<typename E > class BST { private: int size; Node<E>* root; int compare(E e1, E e2); //Compare two elements void Element_Not_Null_Check(E element); //Check whether the element is empty void Node_Pre_Oreder_Traversal(Node<E>* node); //The interface access order of preorder traversal is: root node - > preorder traversal of left subtree - > preorder traversal of right subtree void Node_In_Oreder_Traversal(Node<E>* node); //The interface access order of middle order traversal is: middle order traversal of the left subtree - > root node - > middle order traversal of the right subtree (from small to large). If the right subtree is first, it is from large to small void Node_Post_Oreder_Traversal(Node<E>* node); //The interface access order of post order traversal is: subsequent traversal of left subtree - > post order traversal of right subtree - > root node int node_recursion_calcu_height(Node<E>* node); //Interface function for height The height of a node in a binary tree (recursive algorithm) Node<E>* Find_predecessor(Node<E>* node); //According to the middle order traversal, find the precursor node of a node Node<E>* Find_successor (Node<E>* node); //According to the middle order traversal, find the successor node of a node Node<E>* Find_Node(E element); //Find the node corresponding to an element void Node_Remove(Node<E>* node); //Delete a node public: int calcu_size(); //Number of elements bool isEmpty(); //Is it empty void clear(); //Empty all elements void add(E element); //Add element void remove(E element); //Delete element bool contains(E element); //Whether to include an element void Pre_Oreder_Traversal(); //Preorder traversal void In_Oreder_Traversal(); //Ergodic middle order void Post_Oreder_Traversal(); //Subsequent traversal void Level_Oreder_Traversal(); //Layer continuous traversal int recursion_calcu_height(); //Find the height of binary tree (recursive algorithm) int iteration_calcu_height(); //Find the height of binary tree (iterative algorithm) bool Check_Is_Complete(); //Check whether it is a complete binary tree ~BST() {} };

Next, several functions of binary search tree are analyzed.

First, add:

There are two situations to add:

① The root node is added: the constructor is directly used to assign a value to the root node

② The added node is not the root node: determine the location of the added node and increase the connection between nodes

To determine the location of adding nodes, we must constantly compare these nodes with the added data, and finally find an empty node and put it in. Therefore, we added the compare() internal function

Because we define a generic class that can pass in any data type, and the return value needs to be an int data type, we need to consider more comprehensively for comparison.

For integer and character types, we can directly subtract to detect the relationship between them and 0 to compare their size. However, the floating-point type is still floating-point type after addition and subtraction. Direct subtraction may have data error. Therefore, we use the functions of floor() rounding down and ceil() rounding up to process it.

The following is the code of the int compare(E e1,E e2) function.

/** *return If the return value is equal to 0, it means e1 and e2 are equal. If the return value is greater than 0, it means e1 is greater than e2. If the return value is less than 0, it means e1 is less than e2, */ template <typename E> int BST<E>::compare(E e1, E e2) //Because C + + cannot implement the interface, it is impossible to conduct user-defined comparison on the data of class types, which can be implemented by Java and c# { if (e1 - e2 > 0) //Prevent incoming data types from both integer and floating-point types { return ceil(e1 - e2); //The ceil() and floor() functions are used to change the compared value into an integer return } else if (e1 - e2 < 0) { return floor(e1 - e2); } else { return 0; } }

The implementation of the add() method is relatively simple. You can roughly understand it by directly looking at the comments after the code.

The following is the code of the void add(E element) function.

template <typename E> void BST<E>::add(E element) //Add element { Element_Not_Null_Check(element); //Prevent the added element from being empty if (root == NULL) //Add first node { root = new Node<E> (element, NULL); size++; } //Add not the first node Node<E> *parent = NULL; //Find parent node Node<E> *node = root; int cmp = 0; while (node != NULL) { cmp = compare(element, node->element); //Save the compared values to determine whether to insert left or right parent = node; //Where to save the parent node if (cmp > 0) { node = node->right; } else if (cmp < 0) { node = node->left; } else //Equal coverage { node->element = element; return; } } //See where the parent node is inserted Node<E> *newnode = new Node<E>(element, parent); if (cmp > 0) //Larger than on the right { parent->right = newnode; } else //Less than on the left { parent->left = newnode; } size++; }

Then there are four traversal methods:

① Preorder traversal:

Access order: root node - > pre order traversal of left subtree - > pre order traversal of right subtree

According to the data in the figure above, our access order is:

Because 7 is the root node, access to its left subtree will be 4, and then take 4 as the root node, access to its left subtree will be 2, and then take 2 as the root node, access to its left subtree will be 1, 1 has no child node, and then access to the right subtree 3 of 2, and so on, all access sequences can be deduced.

7->4->2->1->3->5->9->8->11->10->12

According to the above derivation, we can easily think of recursion

First, implement the interface function of the preorder traversal function

Here is the node_ Pre_ Oreder_ The code of the traversal (node < E > * node) function.

template <typename E> void BST<E>::Node_Pre_Oreder_Traversal(Node<E>* node) //The interface access order of preorder traversal is: root node - > preorder traversal of left subtree - > preorder traversal of right subtree { if (node == NULL) { return; } cout << "element->" << node->element<<" "; Node_Pre_Oreder_Traversal(node->left); Node_Pre_Oreder_Traversal(node->right); }

Then we implement the object-oriented preorder traversal function

Here is pre_ Oreder_ Code for the traversal() function.

template <typename E> void BST<E>::Pre_Oreder_Traversal() //Preorder traversal { Node_Pre_Oreder_Traversal(root); //Traverse from the root node }