The concept of binary tree, I don’t want to talk about it here, but you need to know the basics of full binary tree, complete binary tree, etc.
Concept, enter the topic below.
First create a binary tree, look at the code below:
Node* _Create(T* a, size_t size,size_t& index ,const T& invalid) {assert(a); Node* root = NULL; while (index _left = _Create( A, size, ++ index, invalid; root -> _ right = _create (a, size, ++ index, invalid);} return root;}
What needs attention here is the assertion on array a. Develop a good habit, just assert the assertion. There is also the index
which must be a reference, because each element is only accessed once, that is, the externally changed index, and the internal Need to change. So
, is to pass by reference.
Destruction of the binary tree:
void _Destroy(Node* root) {if (root == NULL) return; _Destroy( root->_left); _Destroy(root->_right); }
递归代码， It looks very simple, but don't forget to destroy, otherwise the memory leaks.
Three kinds of traversal of binary tree----preorder, middle order, postorder
void _PreOrder(Node* root ) {Node* cur = root; if (cur != NULL) {cout << cur->_data<<" "; _PreOrder(cur->_left); _PreOrder(cur->_right);}} void _InOrder(Node * root) {Node* cur = root; if (cur != NULL) {_InOrder(cur->_left); cout << cur->_data<<" "; _InOrder(cur->_right);}} void _PostOrder (Node* root) {Node* cur = root; if (cur != NULL) {_PostOrder(cur->_left); _PostOrder(cur->_right); cout << cur->_data<<" ";}}
层序遍历：
void _TiertOrder(Node* root) {queue< Node*> q; Node* cur = root; q.push(cur); while (!q.empty()) {Nod e* tmp = q.front(); cout << tmp->_data << ""; if (tmp->_left) {q.push(tmp->_left);} if (tmp->_right) {q .push(tmp->_right); } q.pop(); } }
This process uses queues, so let’s talk about the idea here: if it’s not an empty tree, the root node will join the team, if it’s enqueued
The subtree of the point is not empty, and the subtree is also enqueued, and the root node will pop up after enqueuing, and so on. For example, the left child you are following
The child exists and has joined the team. If the left child has left and right children, the left and right children will also be added to the team. Pop up the left child who started joining the team.
Depth of the binary tree:
size_t _Depth(Node* root) {if (root == NULL) return 0; size_t left = _Depth(root->_left); size_t right = _Depth(root->_right); return left > right ? left + 1 : right + 1; }
The recursive process is time-consuming, so the two variables above are necessary. Never try to keep the code simple
The feeling of the computer is not considered.
Number of nodes in the binary tree:
size_t _Size(Node* root) {if (root == NULL) return 0; return _Size(root->_left) + _Size(root->_right) + 1; }
Finding elements in the binary tree
Node* _Find(Node* root, const T& x) {Node* cur = root; if (cur == NULL) return NULL; if (cur->_data == x) return cur; //If the left subtree is not found, the right subtree will be traversed if (!_Find(cur->_left, x)) _Find(cur->_right,x); }
Well, that’s all about the recursive implementation of binary trees--