數據結構 二叉樹的遞歸與非遞歸
實例代碼：
#include iostream>
#include queue>
#include stack>
#include assert.h>
using namespace std;
templateclass T>
struct BinaryTreeNode
{
BinaryTreeNodeT>* _left;
BinaryTreeNodeT>* _right;
T _data;
BinaryTreeNode(const T x)
:_left(NULL)
, _right(NULL)
, _data(x)
{}
};
template class T>
class BinaryTree
{
typedef BinaryTreeNodeT> Node;
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(T* a, size_t n, const T invalid)
{
size_t index = 0;
_root=CreateTree(a, n, invalid, index);
}
BinaryTree(const BinaryTreeT> t)
{
_root = _Copy(t._root);
}
BinaryTreeT> operator=( BinaryTreeT> t)
{
swap(_root,t._root);
return *this;
}
~BinaryTree()
{
_DestroyTree(_root);
}
Node* CreateTree(const T* a, size_t n, const T invalid, size_t index)
{
assert(a);
Node* root = NULL;
if (index n a[index] != invalid)
{
root = new Node(a[index]);
root->_left = CreateTree(a, n, invalid, ++index);
root->_right = CreateTree(a, n, invalid, ++index);
}
return root;
}
先序遍歷(遞歸法)
void PrevOrder()
{
_PrevOrder(_root);
cout endl;
}
//先序遍歷非遞歸
void PrevOrderNorR( )
{
Node* cur = _root;
stack Node* >s;
while (cur||!s.empty())
{
while (cur)
{
cout cur->_data " ";
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
s.pop();
cur = top->_right;
}
cout endl;
}
后序遍歷
void PostOrder()
{
_PostOrder(_root);
cout endl;
}
//后序遍歷非遞歸
void PostOrderNorR()
{
Node* cur = _root;
Node* prev = NULL;
stack Node* >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 top->_data " ";
s.pop();
prev = top;
}
cur = top->_right;
}
cout endl;
}
//中序遍歷
void InOrder()
{
_InOrder(_root);
cout endl;
}
//中序遍歷非遞歸
void InOrderNorR()
{
Node* cur = _root;
stack Node* >s;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
s.pop();
cout top->_data " ";
cur = top->_right;
}
cout endl;
}
//節點個數
size_t Size()
{
return _Size(_root);
}
//葉子節點個數
size_t LeafSize()
{
return _LeafSize(_root);
}
//樹的深度
size_t Depth()
{
return _Depth(_root);
}
size_t GetKLevel(size_t k)
{
return _GetKLevel(_root,k);
}
// 查找
Node* Find(size_t x)
{
return _Find(_root,x);
}
//層序遍歷
void LevelOrder()
{
queueNode*> q;
if (_root)
{
q.push(_root);
}
while (!q.empty())
{
Node* front = q.front();
cout front->_data " ";
q.pop();
if (front->_left)
{
q.push(front->_left);
}
if (front->_right)
{
q.push(front->_right);
}
}
cout endl;
}
protected:
Node* _Copy(Node* root)
{
if (root==NULL)
{
return NULL;
}
Node* NewRoot = new Node(root->_data);
NewRoot->_left = _Copy(root->_left);
NewRoot->_right = _Copy(root->_right);
return NewRoot;
}
void _DestroyTree(Node* root)
{
if (NULL==root)
{
return;
}
_DestroyTree(root->_left);
_DestroyTree(root->_right);
delete root;
}
void _PrevOrder(BinaryTreeNodeT>* root)
{
if (root)
{
cout root->_data " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
}
void _PostOrder(BinaryTreeNodeT>* root)
{
if (root)
{
_PostOrder(root->_left);
_PostOrder(root->_right);
cout root->_data " ";
}
}
void _InOrder(BinaryTreeNodeT>* root)
{
if (root)
{
_InOrder(root->_left);
cout root->_data " ";
_InOrder(root->_right);
}
}
int _Size(BinaryTreeNodeT>* root)
{
if (root==0)
{
return 0;
}
return _Size(root->_left) + _Size(root->_right) + 1;
}
int _LeafSize(BinaryTreeNodeT>* root)
{
if (root==NULL)
{
return 0;
}
else if (root->_left == NULLroot->_right == NULL)
{
return 1;
}
return _LeafSize(root->_left) + _LeafSize(root->_right);
}
int _Depth(Node* root)
{
if (root==NULL)
{
return 0;
}
int left = _Depth(root->_left);
int right = _Depth(root->_right);
return left > right ? left + 1 : right + 1;
}
int _GetKLevel(Node* root, size_t k)
{
assert(k>0);
if (root==NULL)
{
return 0;
}
else if (k==1)
{
return 1;
}
return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);
}
Node* _Find(Node* root, const T x)
{
if (root==NULL)
{
return NULL;
}
if (root->_data==x)
{
return root;
}
Node* ret = _Find(root->_left,x);
if (ret != NULL)
return ret;
return _Find(root->_right, x);
}
private:
BinaryTreeNodeT>* _root;
};
void TestBinaryTree()
{
int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
BinaryTreeint> t1(array,sizeof(array)/sizeof(array[0]),'#');
BinaryTreeint>t2(t1);
BinaryTreeint> t3;
t3 = t2;
t2.LevelOrder();
t3.LevelOrder();
t1.LevelOrder();
t1.PrevOrder();
t1.PrevOrderNorR();
t1.InOrder();
t1.InOrderNorR();
t1.PostOrder();
t1.PostOrderNorR();
cout endl;
cout t1.Size() endl;
cout t1.LeafSize() endl;
cout t1.Depth() endl;
cout t1.GetKLevel(2) endl;
cout t1.Find(2) endl;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
您可能感興趣的文章:- C++ 數據結構二叉樹（前序/中序/后序遞歸、非遞歸遍歷）
- C++使用遞歸和非遞歸算法實現的二叉樹葉子節點個數計算方法
- C++基于遞歸和非遞歸算法判定兩個二叉樹結構是否完全相同(結構和數據都相同)
- C++基于遞歸和非遞歸算法求二叉樹鏡像的方法
- C++非遞歸隊列實現二叉樹的廣度優先遍歷
- C++非遞歸建立二叉樹實例
- C語言數據結構之二叉樹的非遞歸后序遍歷算法
