[Data Structure] Recurrence and non-recursion of the binary tree

The test cases used in the code below are drawn as a tree and look like this:

When creating the tree, the array is given, and’#’ represents an illegal value , That is, the node is empty.

Recursive realization of binary tree:

#pragma once# include#includeusing namespace std;templatestruct BinaryTreeNode{ BinaryTreeNode(T value=0) :_value(value), _left(NULL), _right(NULL) {} T _value; BinaryTreeNode< T>* _left; BinaryTreeNode* _right;};templateclass BinaryTree{public: typedef BinaryTreeNode Node; BinaryTree() {} BinaryTree(T* a, size_t size, const T& invalid) { size_t index = 0; _root=_CreatTree( a, size,index, invalid);} BinaryTree(const BinaryTree& bt) {_root = _Copy(bt._root);} BinaryTree& operator=(BinaryTree< T>& bt) {if (this != &bt) {BinaryTree tmp(bt); swap(tmp._root, _root);}} ~BinaryTree() {_Distory(_root);} void PrevOrder() { _PrevOrder(_root); cout << endl;} void InOrder() {_InOrder(_root); cout << endl;} void PostOrder() {_PostOrder(_root); cout << endl;} void LevelOrder() //level Order traversal {_LevelOr der(_root); cout << endl;} size_t Size() {return _Size(_root);} size_t Depth() {return _Depth(_root);} size_t LeafSize() {return _LeafSize(_root);} size_t GetKLevel( size_t k) //Number of nodes in layer K {}protected: Node* _Distory(Node* root) {if (root) {_Distory(root->_left); _Distory(root->_right); Node* del = root; delete del;} return root;} Node* _CreatTree( T*a, size_t size,size_t& index,const T& invalid) {Node* root = NULL; if ((index _left = _CreatTree(a, size, ++index, invalid); root->_right = _CreatTree(a, size, ++index, invalid) ;} return root;} Node* _Copy(Node* copyroot) {Node* root = NULL; if (copyroot!=NULL) {root = new Node(copyroot->_value); root->_left = _Copy(copyroot-> _left); root->_right = _Copy(copyroot->_right);} return root;} Node* _PrevOrder(Node* root) {if (root) {cout << root->_value << ""; _PrevOrder(root ->_left); _PrevOrder(root->_right);} return root;} Node* _InOrder(Node* root) {if (root) {_InOrder(root->_left); cout << root->_value<<" "; _InOrder(root->_right);} return root; } Node* _PostOrder(Node* root) {if (root) {_PostOrder(root->_left); _PostOrder(root->_right); cout << root->_value << "";} return root;} void _LevelOrder (Node* root) {queue q; q.push(root); while (!q.empty()) {Node* tmp = q.front(); cout << tmp->_value<<" "; if (tmp->_left) q.push(tmp->_left); if (tmp->_right) q.push(tmp->_right); q.pop();}} size_t _Size(Node* root ) {size_t size = 0; if (root) {size = _Size(root->_left) + _Size(root->_right)+1;} return size;} size_t _Depth(Node* root) {size_t depth1 = 0; size_t depth2 = 0; if (root) {depth1 = _Depth(root->_left) + 1; depth2 = _Depth(root->_right) + 1;} return depth1> depth2? depth1: depth2;} size_t _LeafSize(Node* root) {if (root == NULL) return 0; else if (root->_left == NULL&&root->_right == NULL) return 1; return _LeafSize(root->_left) + _LeafSize(root->_right); }private: Node* _root;};void test(){ int array[10] = {1, 2, 3,'#' ,'#', 4,'#','#', 5, 6 }; int array1[15] = {1, 2,'#', 3,'#','#', 4, 5, ' #', 6,'#', 7,'#','#', 8 }; BinaryTree bt(array, 10,'#'); bt.PrevOrder(); bt.InOrder(); bt .PostOrder(); cout << bt.Size() << endl; cout << bt.Depth() << endl; cout << bt.LeafSize() << endl; BinaryTree bt2(array1, 15 ,'#'); cout << bt2.Depth() << endl; cout << bt2.LeafSize() << endl; BinaryTree bt3(bt); bt3.PrevOrder(); BinaryTree bt4 =bt3; bt4.PrevOrder(); bt4.LevelOrder();}

The advantage of recursion lies in the simplicity of the code. But recursion is not easy to understand.

Non-recursive binary tree (often tested in interviews):

#pragma once#include#include#include#includeusing namespace std;templatestruct BinaryTreeNode{ BinaryTreeNode(T value = 0) :_value(value), _left(NULL), _right(NULL) {} T _value; BinaryTreeNode* _left; BinaryTreeNode* _right;};templateclass BinaryTree{public: typedef BinaryTreeNode Node; BinaryTree() {} explicit BinaryTree(T* a, size_t size, const T& invalid) //Constructor to create a tree. {stack s; size_t index = 0; Node* cur = NULL; while (index _left = new Node(a[index++]); cur = cur->_left;} s.push(cur); } index++; Node* top = s.top(); s.pop(); if ((index _right = new Node( a[index++]); cur = cur->_right; s.push(cur);}}} BinaryTree(const BinaryTree& bt) //copy structure {Node* cur = bt._root; Node* root = NULL; stacks; stacks1; while (cur || !s.empty()) {while (cur) {s.push(cur); if (root == NULL) {root = new Node(cur->_value); _root = root;} else {root->_left = new Node(cur->_value); root = root->_left;} cur = cur->_left; s1.push( root);} Node* top = s.top(); Node* top1 = s1.top(); s.pop(); s1.pop(); cur = top->_right; if (cur) {root = top1; root->_right = new Node(cur->_value); root = root->_right; cur = cur->_left;}}} BinaryTree& operator=(BinaryTree< T> bt) {swap(_root, bt._root); return *this;} void PrevOrderNoR() {Node* cur = _root; stack s; while (cur || !s.empty()) { while (cur) {cout << cur->_value << ""; s.push(cur); cur = cur->_left;} Node* top = s.top(); s.pop(); cur = top->_right;} cout << endl;} void InOrderNoR() {Node* cur = _root; stack s; while (cur || !s.empty()) {while (cur) {s. push(cur); cur = cur->_left;} Node* top = s.top(); s.pop(); cout << top->_value << ""; cur = top->_right;} cout << endl;} void PostOrderNoR() {Node* cur = _root; Node* prev = NULL; stack s; while (cur || !s.empty()) {while (cur) {s.push (cur); cur = cur->_left;} Node* top = s.top(); if ((top->_right == NULL) || (prev == top->_right)) {prev = top; cout << top->_v alue << ""; s.pop(); //cur = top->_right;} else cur = top->_right;} cout << endl;} size_t SizeNoR() {size_t size = 0; Node* cur = _root; stack s; while (cur || !s.empty()) {while (cur) {s.push(cur); size++; cur = cur->_left;} Node* top = s .top(); s.pop(); cur = top->_right;} return size;} size_t DepthNoR() {if (_root == NULL) return 0; size_t depth = 0; Node* cur = NULL; queue  q; size_t VisitNum = 0; //How much data is popped out of the stack size_t NodeNum = 1; size_t LeveNum = 1; //The serial number of the last data in each layer q.push(_root); while (!q. empty()) {cur = q.front(); q.pop(); VisitNum++; if (cur->_left) {NodeNum++; q.push(cur->_left);} if (cur->_right) { NodeNum++; q.push(cur->_right);} if (LeveNum == VisitNum) {depth++; LeveNum = NodeNum;}} return depth;} size_t LeveNum() //Number of leaf nodes {size_t count = 0; Node * cur = _root; stack s; while (cur || !s.empty()) {while (cur) {s.push(cur); if ((cur->_left == NULL) && (cur->_right == NULL)) count++; cur = cur->_left;} Node* top = s.top(); s.pop(); cur = top->_right;} return count;} size_t GetKLeve(size_t k) //Get the number of k-th layer nodes. {assert(k <= DepthNoR()); if (k == 1) return 1; queueq; size_t NodeNum = 1; size_t LeveNum = 1; size_t VisitNum = 0; size_t leve = 1; q. push(_root); while (!q.empty()) {Node* cur = q.front(); q.pop(); VisitNum++; if (cur->_left) {q.push(cur->_left) ; NodeNum++;} if (cur->_right) {q.push(cur->_right); NodeNum++;} if (LeveNum == VisitNum) {leve++; if (leve == k) break; LeveNum = NodeNum;}} return NodeNum-VisitNum; }private: Node* _root;};void test(){ int array[10] = {1, 2, 3,'#','#', 4,'#','#', 5, 6 }; BinaryTree bt(array, 10,'#'); bt.PrevOrderNoR(); bt.InOrderNoR(); bt.PostOrderNoR(); BinaryTree bt1(bt); bt1.PrevOrderNoR (); BinaryTree bt2 = bt1; bt2.PrevOrderNoR(); cout << bt.SizeNoR() << endl; cout << bt.DepthNoR() << endl; cout << bt.LeveNum() < 
 As you can see, non-recursively speaking, the amount of code can be more, but it is easier to understand, and several traversal process codes are very similar. Understand one of them, and the next few are similar.