1、构造
2、拷贝构造
3、析构
4.深度
5、叶子数
6.前序遍历递归非递归
7、中序遍历递归非递归
8、中序遍历递归非递归
9、第k层子树
等
定义树节点结构体
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,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==NULL)
return;
_Destory(root->left);
_Destory(root->right);
delete root;
}
void _PrevOrder(Node* root)
{
if(root==NULL)
return;
cout<<root->_date<<" ";
_PrevOrder(root->left);
_PrevOrder(root->right);
}
void _InOrder(Node* root)
{
if(root==NULL)
return;
_InOrder(root->left);
cout<<root->_date<<" ";
_InOrder(root->right);
}
void _PostOrder(Node* root)
{
if(!root)
return;
_PostOrder(root->left);
_PostOrder(root->right);
cout<<root->_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);
}外部实现调用内部函数
BinTree(T* a,const T& invalid)//构造
{
int index=0;
_CreateTree( _root,index,invalid);
}
BinTree(const BinTree<T>& t)//拷贝构造
{
_root=_CopyBinTree(t._root);
}
BinTree<T>& operator=(const BinTree<T> &t)//运算符重载
{
if(this!=&t)
{
swap(_root=t._root);
}
return *this;
}
void PrevOrder()//递归前序
{
_PrevOrder(_root);
cout<<endl;
}
void InOrder()
{
_InOrder(_root);
cout<<endl;
}
void PostOrder()
{
_PostOrder(_root);
cout<<endl;
}
void LevelOrder()///层序
{
queue<Node*> q;
Node* cur=_root;
if(cur)
q.push(cur);
while (!q.empty())
{
cur=q.front();
cout<<cur->_date<<" ";
if(cur->left)
{
q.push(cur->left);
}
if(cur->right)
{
q.push(cur->right);
}
q.pop();
}
cout<<endl;
}
void PrevOrder_NonR()//非递归前序
{
stack<Node*> sn;
if(_root)
{
sn.push(_root);
}
while (sn.empty()==NULL)
{
Node* root=sn.top();
cout<<root->_date<<" ";
sn.pop();
if (root->left)
{
sn.push(root->left);
}
if (root->right)
{
sn.push(root->right);
}
}
cout<<endl;
}
void InOrder_NonR()
{
stack<Node*> sn;
Node* cur=_root;
while (cur||!sn.empty())
{
while (cur)
{
sn.push(cur);
cur=cur->left;
}
if (!sn.empty())
{
Node* tmp=sn.top();
cout<<tmp->_date<<" ";
sn.pop();
cur=tmp->right;
}
}
cout<<endl;
}
void PostOrder_NonR()
{
stack<Node*> 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<<cur->_date<<" ";
s.pop();
pre=cur;
}
else
{
if(cur->right!=NULL)
s.push(cur->right);
if(cur->left!=NULL)
s.push(cur->left);
}
}
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)
{
return _GetKLevel(_root,k);
}
void Destory()
{
_Destory(_root);
}测试用例
void test()
{
int a1[10]={1,2,3,'#',4,5,6};
BinTree<int> t1(a1,10,'#');
t1.PrevOrder();
t1.InOrder();
t1.PostOrder();
t1.PrevOrder_NonR();
t1.InOrder_NonR();
t1.PostOrder_NonR();
t1.LevelOrder();
cout<<t1.Size()<<endl;
cout<<t1.Depth()<<endl;
cout<<t1.LeafSize()<<endl;
cout<<t1.GetKLevel(2);
}源码
#include <iostream>
#include <cstdlib>
#include <assert.h>
#include <stack>
#include<queue>
using namespace std;
template<typename T>
struct BinTreeNode
{
BinTreeNode* left;
BinTreeNode* right;
T _date;
BinTreeNode(const T& x)
:left(NULL),_date(x)
{}
};
template<typename T>
class BinTree
{
typedef BinTreeNode<T> Node;
public:
BinTree()
:_root(NULL)
{}
~BinTree()
{
Destory();
}
BinTree(T* a,const T& invalid)
{
int index=0;
_CreateTree( _root,invalid);
}
BinTree(const BinTree<T>& t)
{
_root=_CopyBinTree(t._root);
}
BinTree<T>& operator=(const BinTree<T> &t)
{
if(this!=&t)
{
swap(_root=t._root);
}
return *this;
}
void PrevOrder()
{
_PrevOrder(_root);
cout<<endl;
}
void InOrder()
{
_InOrder(_root);
cout<<endl;
}
void PostOrder()
{
_PostOrder(_root);
cout<<endl;
}
void LevelOrder()
{
queue<Node*> q;
Node* cur=_root;
if(cur)
q.push(cur);
while (!q.empty())
{
cur=q.front();
cout<<cur->_date<<" ";
if(cur->left)
{
q.push(cur->left);
}
if(cur->right)
{
q.push(cur->right);
}
q.pop();
}
cout<<endl;
}
void PrevOrder_NonR()
{
stack<Node*> sn;
if(_root)
{
sn.push(_root);
}
while (sn.empty()==NULL)
{
Node* root=sn.top();
cout<<root->_date<<" ";
sn.pop();
if (root->left)
{
sn.push(root->left);
}
if (root->right)
{
sn.push(root->right);
}
}
cout<<endl;
}
void InOrder_NonR()
{
stack<Node*> sn;
Node* cur=_root;
while (cur||!sn.empty())
{
while (cur)
{
sn.push(cur);
cur=cur->left;
}
if (!sn.empty())
{
Node* tmp=sn.top();
cout<<tmp->_date<<" ";
sn.pop();
cur=tmp->right;
}
}
cout<<endl;
}
void PostOrder_NonR()
{
stack<Node*> 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<<cur->_date<<" ";
s.pop();
pre=cur;
}
else
{
if(cur->right!=NULL)
s.push(cur->right);
if(cur->left!=NULL)
s.push(cur->left);
}
}
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)
{
return _GetKLevel(_root,k);
}
void Destory()
{
_Destory(_root);
}
protected:
void _CreateTree(Node*& root,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<<root->_date<<" ";
_PrevOrder(root->left);
_PrevOrder(root->right);
}
void _InOrder(Node* root)
{
if(root==NULL)
return;
_InOrder(root->left);
cout<<root->_date<<" ";
_InOrder(root->right);
}
void _PostOrder(Node* root)
{
if(!root)
return;
_PostOrder(root->left);
_PostOrder(root->right);
cout<<root->_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,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,'#');
t1.PrevOrder();
t1.InOrder();
t1.PostOrder();
t1.PrevOrder_NonR();
t1.InOrder_NonR();
t1.PostOrder_NonR();
t1.LevelOrder();
cout<<t1.Size()<<endl;
cout<<t1.Depth()<<endl;
cout<<t1.LeafSize()<<endl;
cout<<t1.GetKLevel(2);
}
<pre name="code" class="cpp">void test2()
{
int array1[10] = { 1,6 };
BinTree<int> tree(array1,'#');
BinTree<int> tree1=tree;//拷贝
tree1.PrevOrder();
}
主函数
#include "BinTree.h"
int main()
{
<span style="white-space:pre"> </span>test();
<span style="white-space:pre"> </span>test2();
<span style="white-space:pre"> </span>system("pause");
<span style="white-space:pre"> </span>return 0;
} 原文链接：https://www.f2er.com/datastructure/382446.html