二叉樹的相關操作

二叉樹:二叉樹是一棵特殊的樹，二叉樹每個節點最多有兩個孩子結點，分別稱為左孩子和右孩子。

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<assert.h>
#include<stack>
#include<queue>

using namespace std;
//節點結構
template<class T>
class BinaryTreeNode//節點
{
public:
BinaryTreeNode(const T& data)
:_data(data)
,_left(NULL)
,_right(NULL)
{}
T _data;//值
BinaryTreeNode* _left;//左子樹
BinaryTreeNode* _right;//右子樹
};
template<class T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node;
public:
BinaryTree()//無參構造函數
:_root(NULL)
{}
BinaryTree(const T* a, size_t size, const T& invalid)//構造函數
{
assert(a);
size_t index = 0;
_root = _CreateTree(a, size, invalid, index);
}
BinaryTree(const BinaryTree<T>& t)//拷貝構造
{
_root = _Copy(t._root);
}
BinaryTree<T>& operator=(const BinaryTree<T>& t)//賦值函數
{
if (this != &t)
{
BinaryTreeNode<T>* tmp = _Copy(t._root);
_Destroy(_root);
_root = temp;
}
return *this;
}
~BinaryTree()//析構
{
_Destroy(_root);
_root = NULL;
}
public:
void PrevOrder()//先根遍歷
{
cout << "先根遍歷:";
_PrevOrder(_root);
cout << endl;
}
void InOrder()//中根遍歷
{
cout << "中根遍歷:";
_InOrder(_root);
cout << endl;
}
void PostOrder()//后根遍歷
{
cout << "后根遍歷:";
_PostOrder(_root);
cout << endl;
}
void LevelOrder()//層次遍歷
{
cout << "層次遍歷:";
_LevelOrder(_root);
cout << endl;
}
size_t Size()//求二叉樹的節點的個數
{
return _Size(_root);
}
size_t Depth()//求二叉樹的深度
{
return _Depth(_root);
}
size_t LeafSize()//葉子節點個數
{
return _LeafSize(_root);
}
protected:
Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t&  index)
//index要傳引用，需要更改index的值
{
Node* root = NULL;
//判斷數組是否越界和輸入的值是否合法
if (index < size&&a[index] != invalid)
{
root = new Node(a[index]);//創建根節點
root->_left = _CreateTree(a, size, invalid, ++index);//遞歸創建左子樹
root->_right = _CreateTree(a, size, invalid, ++index);//遞歸創建右子樹
}
return root;//返回根節點
}
//void _PrevOrder(Node* root)
//{
////如果節點為空則直接返回
//if (root == NULL)
//{
//return;
//}
//cout << root->_data << " ";//訪問根節點
//_PrevOrder(root->_left);//遞歸訪問左子樹
//_PrevOrder(root->_right);//遞歸訪問右子樹
//}
void _PrevOrder(Node* root)
{
stack<Node*> s;
if (root==NULL)
{
return;
}
s.push(root);
while (!s.empty())
{
root = s.top();
cout << root->_data << " ";
s.pop();
if (root->_right)
{
s.push(root->_right);
}
if (root->_left)
{
s.push(root->_left);
}
}
}
//void _InOrder(Node* root)
//{
////如果節點為空則直接返回
//if (root == NULL)
//{
//return;
//}
//_InOrder(root->_left);//遞歸訪問左子樹
//cout << root->_data << " ";//遞歸訪問根節點
//_InOrder(root->_right);//遞歸訪問右子樹
//}
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
stack<Node*> s;
Node* cur = root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cur = s.top();//將棧頂元素保存，以便后面判斷它是否有有孩子
cout << s.top()->_data << " ";
s.pop();
if (cur->_right == NULL)
{
cur = NULL;
}
else
{
cur = cur->_right;
}
}
}
//void _PostOrder(Node* root)
//{
//if(root == NULL)
//{
//return;
//}
//_PostOrder(root->_left);//遞歸訪問左子樹
//_PostOrder(root->_right);//遞歸訪問右子樹
//cout << root->_data << " ";//遞歸訪問根節點
//}
void _PostOrder(Node* root)
{
if (root == NULL)
{
return;
}
Node* cur = root;
Node* prev = NULL;
stack<Node*> s;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cur = s.top();
if (cur->_right == NULL || cur->_right == prev)
{
cout << cur->_data << " ";
s.pop();
prev = cur;
cur = NULL;
}
else
{
cur = cur->_right;
}
}
}
void  _Destory(Node* root)//析構---相當于后序刪除
{
if (root == NULL)
{
return;
}
//刪除葉結點
if (root->_left== NULL&&root->_right == NULL)
{
delete root;
root = NULL;
return;
}
_Destory(root->_left);//遞歸刪除左子樹
_Destory(root->_right);//遞歸刪除右子樹
delete root;
}
size_t _Size(Node* root)//節點的個數
{
size_t count = 0;
if (root == NULL)
{
return count;//樹為空
}
count = _Size(root->_left) + _Size(root->_right);
return count + 1;
}
size_t _Depth(Node* root)//樹的深度
{
size_t left = 0;
size_t right = 0;
size_t max = 0;
if (root == 0)
{
return 0;
}
else
{
left = _Depth(root->_left);
right = _Depth(root->_right);
max = left > right ? left : right;
return max + 1;
}
}
size_t _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* _Copy(Node* root)
{
if (roo == NULL)
{
return;
}
Node* newroot = new Node(root->_data);
newroot->_left = Copy(root->_left);
newroot->_right = Copy(root->_right);
return newroot;
}
void _LevelOrder(Node* root)//層次遍歷
{
queue<Node*> q;
if (root == NULL)
{
return;
}
q.push(root);//根節點入隊
while (!q.empty())//當隊列不為空
{
if (q.front()->_left)
{
q.push(q.front()->_left);
}
if (q.front()->_right)
{
q.push(q.front()->_right);
}
cout << q.front()->_data << " ";
q.pop();
}
cout << endl;
}
private:
Node* _root;//根節點
};
void Test()
{
int a[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
BinaryTree<int> b(a, 10, '#');
b.PrevOrder();
b.InOrder();
b.PostOrder();
b.LevelOrder();
cout << "size:" << b.Size() << endl;
cout << "depth:" << b.Depth() << endl;
cout << "leafSize:" << b.LeafSize() << endl;
}
int main()
{
Test();
getchar();
return 0;
}