[Data Structure] Simple traversal and basic operation of binary tree

1, construction

2, copy construction

3, destruction

4. depth

5, Number of leaves

6. Pre-order traversal recursive non-recursive

7, Middle-order traversal recursive non-recursive

8, Middle-order traversal recursive non-recursive

9, the k-th subtree

etc

Define the tree node structure

struct BinTreeNode{ BinTreeNode* left; BinTreeNode* right; T _date; BinTreeNode(const T& x) :left(NULL) ,right(NULL) ,_date(x) {}};

内部函数实现

 void _CreateTree(Node*& root,T a[],size_t size,int& index ,const T& invalid) {if(index< size&& a[index]!=invalid) {root =new Node(a[index]); _CreateTree(root->left,a,size,++index,invalid); _CreateTree(root->right,a,size,++index,invalid);}} Node* _CopyBinTree(Node* root) {Node* newNode=NULL; if(!root) {newNode=new Node(root->_date); newNode->left=_CopyBinTree(root->left); newNode->right=_CopyBinTree( root->right);} re turn newNode;} void _Destory(Node* root) {if(root==NULL) return; _Destory(root->left); _Destory(root->right); delete root;} void _PrevOrder(Node* root) {if (root==NULL) return; cout<_date<<" "; _PrevOrder(root->left); _PrevOrder(root->right);} void _InOrder(Node* root) {if(root== NULL) return; _InOrder(root->left); cout<_date<<" "; _InOrder(root->right);} void _PostOrder(Node* root) {if(!root) return; _PostOrder( root->left); _PostOrder(root->right); cout<_date<<" ";} int _Size(Node* root) {if (!root) return 0; return _Size(root->left )+_Size(root->right)+1;} int _Depth(Node* root) {if(!root) return 0; int leftchilddepth=_Depth(root->left)+1; int rightchilddepth=_Depth(root-> right)+1; if(leftchilddepth>=rightchilddepth) {return leftchilddepth;} else {return rightchilddepth;}} int _GetKLevel(Node* root,size_t k) {if(root==NULL) return 0;if(k== 1) return 1;else return _GetKLevel(root->left,k- 1)+_GetKLevel(root->right,k-1);} int _LeafSize(Node* root) {if(root==NULL) return 0; if(root->left==NULL&&root->right==NULL) return 1; return _LeafSize(root->left)+_LeafSize(root->right); }

External implementation calls internal functions

 BinTree(T* a,size_t size,const T& invalid)//Construction {int index=0; _CreateTree( _root,a,size,index,invalid );} BinTree(const BinTree& t)//Copy structure {_root=_CopyBinTree(t._root);} BinTree& operator=(const BinTree &t)//Operator overload {if( this!=&t) {swap(_root=t._root);} return *this;} void PrevOrder()//recursive preorder {_PrevOrder(_root); cout< q; Node* cur=_root; if(cur ) q.push(cur); while (!q.empty()) {cur=q.front(); cout<_date<<" "; if(cur->left) {q.push( cur->left);} if(cur->right) { q.push(cur->right);} q.pop();} cout< sn; if(_root) {sn.push (_root);} while (sn.empty()==NULL) {Node* root=sn.top(); cout<_date<<" "; sn.pop(); if (root-> left) {sn.push(root->left);} if (root->right) {sn.push(root->right);}} cout< sn; Node* cur=_root; while (cur||!sn.empty()) {while (cur) {sn.push(cur); cur=cur->left;} if (!sn.empty()) {Node* tmp=sn.top(); cout<_date<<" "; sn.pop(); cur=tmp->right;}} cout< s; Node *cur; Node *pre=NULL; s.push(_root); while(!s.empty()) {cur=s.top(); if((cur->left== NULL&&cur->right==NULL)|| (pre!=NULL&&(pre==cur->left||pre==cur->right))) {cout<_date<<" "; s. pop(); pre=cur;} else {if(cur->right!=NULL) s.push(cur->right); if(cur->left!=NULL) s.push(cur-> left);}} cout<
Test case

void test(){ int a1[10]={1,2,3,'#','#',4,'#',' #',5,6}; BinTree t1(a1,10,'#'); t1.PrevOrder(); t1.InOrder(); t1.PostOrder(); t1.PrevOrder_NonR(); t1.InOrder_NonR (); t1.PostOrder_NonR(); t1.LevelOrder(); cout<
Source code

#include #include #include #include #includeusing namespace std;templatestruct BinTreeNode{ BinTreeNode* left; BinTreeNode* right ; T _date; BinTreeNode(const T& x) :left(NULL) ,right(NULL) ,_date(x) {)};templateclass BinTree{ typedef BinTreeNode Node;public: BinTree() :_root( NULL) {} ~BinTree() {Destory();} BinTree(T* a,size_t size,const T& invalid) {int index=0; _CreateTree( _root,a,size,index,invalid);} BinTree(const BinTree& t) {_root=_CopyBinTree(t._root);} BinTree& operator=(const BinTree &t) {if(this!=&t) {swap(_root=t._root) ;} return *this;} void PrevOrder() {_PrevOrder(_root); cout< q; Node* cur=_root; if(cur) q.push(cur); while (!q.empty()) {cur=q.front( ); cout<_date<<" "; if(cur->left) {q.push(cur->left);} if(cur->right) {q.push(cur->right) ;} q.pop();} cout< sn; if(_root) {sn.push(_root);} while (sn.empty()==NULL ) { Node* root=sn.top(); cout<_date<<" "; sn.pop(); if (root->left) {sn.push(root->left);} if (root ->right) {sn.push(root->right);}} cout< sn; Node* cur=_root; while (cur||!sn.empty ()) {while (cur) {sn.push(cur); cur=cur->left;} if (!sn.empty()) {Node* tmp=sn.top(); cout< _date<<" "; sn.pop(); cur=tmp->right;}} cout< s; Node *cur; Node *pre=NULL; s .push(_root); while(!s.empty()) {cur=s.top(); if((cur->left==NULL&&cur->right==NULL)|| (pre!=NULL&&(pre ==cur->left||pre==cur->right))) {cout<_date<<" "; s.pop(); pre=cur;} else {if(cur->right !=NULL) s.push(cur->right); if(cur->left!=NULL) s.push(cur->left);}} cout<left,a,size,++index,invalid); _CreateTree(root-> right,a,size,++index,invalid);}} Node* _CopyBinTree(Node* root) {Node* newNode=NULL; if(!root) {newNode=new Node(root->_date); newNode-> left=_CopyBinTree(root->left); newNode->right=_CopyBinTree(root->right);} return newNode;} void _Destory(Node* root) {if(!root) return; _Destory(root->left) ; _Destory(root->right); delete root;} void _PrevOrder(Node* root) {if(root==NULL) return; cout<_date<<" "; _PrevOrder(root->left); _PrevOrder(root->right);} void _InOrder(Node* root) {if(root==NULL) return; _InOrder(root->left); cout<_date<<" "; _InOrder(root- >right);} void _PostOrder(Node* root) {if(!root ) return; _PostOrder(root->left); _PostOrder(root->right); cout<_date<<" ";} int _Size(Node* root) {if (!root) return 0; return _Size (root->left)+_Size(root->right)+1;} int _Depth(Node* root) {if(!root) return 0; int leftchilddepth=_Depth(root->left)+1; int rightchilddepth= _Depth(root->right)+1; if(leftchilddepth>=rightchilddepth) {return leftchilddepth;} else {return rightchilddepth;}} int _GetKLevel(Node* root,size_t k) {if(root==NULL) return 0; if(k==1) return 1;else return _GetKLevel(root->left,k-1)+_GetKLevel(root->right,k-1);} int _LeafSize(Node* root) {if(root== NULL) return 0; if(root->left==NULL&&root->right==NULL) return 1; return _LeafSize(root->left)+_LeafSize(root->right);} Node* _root;};void test (){ int a1[10]={1,2,3,'#','#',4,'#','#',5,6}; BinTree t1(a1,10,' #'); t1.PrevOrder(); t1.InOrder(); t1.PostOrder(); t1.PrevOrder_NonR(); t1.InOrder_NonR(); t1.PostOrder_NonR(); t1.LevelOrder(); cout<
void test2(){ int array1[10] = {1, 2, 3,'#','#', 4,'# ','#', 5, 6 }; BinTree tree(array1,10,'#'); BinTree tree1=tree;//copy tree1.PrevOrder(); }

 Main function

#include "BinTree.h"
int main()
{
 test();
 test2();
 system("pause");
 return 0;
}