数据结构二叉树的递归与非递归

2024-02-22 19:49:03 243

数据结构二叉树的递归与非递归

实例代码：

#include
#include
#include
#include
usingnamespacestd;
template
structBinaryTreeNode
{
BinaryTreeNode*_left;
BinaryTreeNode*_right;
T_data;
BinaryTreeNode(constT&x)
:_left(NULL)
,_right(NULL)
,_data(x)
{}
};
template
classBinaryTree
{
typedefBinaryTreeNodeNode;
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(T*a,size_tn,constT&invalid)
{
size_tindex=0;
_root=CreateTree(a,n,invalid,index);
}
BinaryTree(constBinaryTree&t)
{
_root=_Copy(t._root);
}
BinaryTree&operator=(BinaryTree&t)
{
swap(_root,t._root);
return*this;
}
~BinaryTree()
{
_DestroyTree(_root);
}
Node*CreateTree(constT*a,size_tn,constT&invalid,size_t&index)
{
assert(a);
Node*root=NULL;
if(index_left=CreateTree(a,n,invalid,++index);
root->_right=CreateTree(a,n,invalid,++index);
}
returnroot;
}

先序遍历(递归法)

voidPrevOrder()
{
_PrevOrder(_root);
cout<s;
while(cur||!s.empty())
{
while(cur)
{
cout<_data<<"";
s.push(cur);
cur=cur->_left;
}
Node*top=s.top();
s.pop();
cur=top->_right;
}
cout<
后序遍历     
voidPostOrder()
{
_PostOrder(_root);
cout<s;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->_left;
}
Node*top=s.top();
if(NULL==top->_right&&prev==top->_right)
{
cout<_data<<"";
s.pop();
prev=top;
}
cur=top->_right;
}
cout<s;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->_left;
}
Node*top=s.top();
s.pop();
cout<_data<<"";
cur=top->_right;
}
cout<q;
if(_root)
{
q.push(_root);
}
while(!q.empty())
{
Node*front=q.front();
cout<_data<<"";
q.pop();
if(front->_left)
{
q.push(front->_left);
}
if(front->_right)
{
q.push(front->_right);
}
}
cout<_data);
NewRoot->_left=_Copy(root->_left);
NewRoot->_right=_Copy(root->_right);
returnNewRoot;
}
void_DestroyTree(Node*root)
{
if(NULL==root)
{
return;
}
_DestroyTree(root->_left);
_DestroyTree(root->_right);
deleteroot;
}
void_PrevOrder(BinaryTreeNode*root)
{
if(root)
{
cout<_data<<"";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
}
void_PostOrder(BinaryTreeNode*root)
{
if(root)
{
_PostOrder(root->_left);
_PostOrder(root->_right);
cout<_data<<"";
}
}
void_InOrder(BinaryTreeNode*root)
{
if(root)
{
_InOrder(root->_left);
cout<_data<<"";
_InOrder(root->_right);

}
}
int_Size(BinaryTreeNode*root)
{
if(root==0)
{
return0;
}
return_Size(root->_left)+_Size(root->_right)+1;
}
int_LeafSize(BinaryTreeNode*root)
{
if(root==NULL)
{
return0;
}
elseif(root->_left==NULL&&root->_right==NULL)
{
return1;
}
return_LeafSize(root->_left)+_LeafSize(root->_right);
}
int_Depth(Node*root)
{
if(root==NULL)
{
return0;
}
intleft=_Depth(root->_left);
intright=_Depth(root->_right);
returnleft>right?left+1:right+1;
}


int_GetKLevel(Node*root,size_tk)
{
assert(k>0);
if(root==NULL)
{
return0;
}
elseif(k==1)
{
return1;
}
return_GetKLevel(root->_left,k-1)+_GetKLevel(root->_right,k-1);
}
Node*_Find(Node*root,constT&x)
{
if(root==NULL)
{
returnNULL;
}
if(root->_data==x)
{
returnroot;
}
Node*ret=_Find(root->_left,x);
if(ret!=NULL)
returnret;
return_Find(root->_right,x);
}

private:
BinaryTreeNode*_root;
};




voidTestBinaryTree()
{
intarray[10]={1,2,3,'#','#',4,'#','#',5,6};
BinaryTreet1(array,sizeof(array)/sizeof(array[0]),'#');
BinaryTreet2(t1);
BinaryTreet3;
t3=t2;
t2.LevelOrder();
t3.LevelOrder();
t1.LevelOrder();
t1.PrevOrder();
t1.PrevOrderNorR();
t1.InOrder();
t1.InOrderNorR();
t1.PostOrder();
t1.PostOrderNorR();
cout<
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

数据结构 二叉树的递归与非递归

热门推荐

随机推荐

数据结构二叉树的递归与非递归