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

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

实例代码:

#include <iostream>

#include <queue>

#include <stack>

#include <assert.h>

using namespace std;

template<class T>

struct BinaryTreeNode

{

BinaryTreeNode<T>* _left;

BinaryTreeNode<T>* _right;

T _data;

BinaryTreeNode(const T& x)

:_left(NULL)

, _right(NULL)

, _data(x)

{}

};

template <class T>

class BinaryTree

{

typedef BinaryTreeNode<T> 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 BinaryTree<T>& t)

{

_root = _Copy(t._root);

}

BinaryTree<T>& operator=( BinaryTree<T>& 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()

{

queue<Node*> 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(BinaryTreeNode<T>* root)

{

if (root)

{

cout << root->_data << " ";

_PrevOrder(root->_left);

_PrevOrder(root->_right);

}

}

void _PostOrder(BinaryTreeNode<T>* root)

{

if (root)

{

_PostOrder(root->_left);

_PostOrder(root->_right);

cout << root->_data << " ";

}

}

void _InOrder(BinaryTreeNode<T>* root)

{

if (root)

{

_InOrder(root->_left);

cout << root->_data << " ";

_InOrder(root->_right);

}

}

int _Size(BinaryTreeNode<T>* root)

{

if (root==0)

{

return 0;

}

return _Size(root->_left) + _Size(root->_right) + 1;

}

int _LeafSize(BinaryTreeNode<T>* root)

{

if (root==NULL)

{

return 0;

}

else if (root->_left == NULL&&root->_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:

BinaryTreeNode<T>* _root;

};

void TestBinaryTree()

{

int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };

BinaryTree<int> t1(array,sizeof(array)/sizeof(array[0]),'#');

BinaryTree<int>t2(t1);

BinaryTree<int> 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;

}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

以上是 数据结构 二叉树的递归与非递归 的全部内容, 来源链接: www.h5w3.com/256117.html

回到顶部