溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
二叉樹：二叉樹是一棵特殊的樹，二叉樹每個節點最多有兩個孩子結點，分別稱為左孩子和右孩子。
二叉樹節點結構：
struct BinaryTreeNode
{
T _data; //數據
BinaryTreeNode<T>* _left; //指向左子樹
BinaryTreeNode<T>* _right; //指向右子樹
BinaryTreeNode(const T& d)
:_data(d)
,_left(NULL)
,_right(NULL)
{}
};二叉樹的創建：
Node* _CreateTree(const T* a, size_t size, size_t& index, const T& invilid)
{
Node* root = NULL;
if(index<size && a[index] != invilid)
{
root = new Node(a[index]); //創建根節點
root->_left = _CreateTree(a, size, ++index, invilid); //遞歸實現左子樹
root->_right = _CreateTree(a, size, ++index, invilid); //遞歸實現右子樹
}
return root; //返回根節點
}前序遍歷：
/* 前序遍歷：根->左子樹->右子樹 */
void _PrevOrder(Node* root)
{
if(root == NULL)
{
return;
}
cout<<root->_data<<" "; //打印根節點數據
_PrevOrder(root->_left); //遞歸遍歷左子樹
_PrevOrder(root->_right); //遞歸遍歷右子樹
}中序遍歷：
/* 中序遍歷：左子樹->根->右子樹 */
void _InOrder(Node* root)
{
if(root == NULL)
{
return;
}
_InOrder(root->_left); //遞歸遍歷左子樹
cout<<root->_data<<" "; //打印根節點數據
_InOrder(root->_right); //遞歸遍歷右子樹
}后序遍歷：
/* 后序遍歷：左子樹->右子樹->根 */
void _PostOrder(Node* root)
{
if(root == NULL)
{
return;
}
_PostOrder(root->_left); //遞歸遍歷左子樹
_PostOrder(root->_right); //遞歸遍歷右子樹
cout<<root->_data<<" "; //打印根節點數據
}層次遍歷：
/* 層次遍歷：第一層->最后一層 */
void _LevelOrder(Node* root)
{
queue<Node*> qt;
if(root == NULL)
{
return;
}
qt.push(root); //將根節點壓到隊列中
while(!qt.empty())
{
/* 當根節點的左孩子不為空，就說明這一層還沒有完全壓入隊列中 */
if(qt.front()->_left != NULL)
{
qt.push(qt.front()->_left); //將根節點左子樹壓到隊列中
}
/* 當根節點的右孩子不為空，就說明這一層還沒有完全壓入隊列中 */
if(qt.front()->_right != NULL)
{
qt.push(qt.front()->_right); //將根節點右子樹壓到隊列中
}
cout<<qt.front()->_data<<" "; //依次打印節點
qt.pop(); //將打印的節點出隊列
}
}二叉樹節點的個數 = 就是左子樹節點個數加上右子樹節點的個數再加上根節點
size_t _Size(Node* root)
{
if(root == NULL)
{
return 0;
}
return _Size(root->_left)+_Size(root->_right)+1;//左子樹節點+右子樹節點+根節點
}二叉樹的深度 = 左子樹 >= 右子樹 ? 左子樹+1， 右子樹+1；
size_t _Depth(Node* root)
{
if(root == NULL)
{
return 0;
}
size_t LeftDepth = _Depth(root->_left);
size_t RightDepth = _Depth(root->_right);
if(LeftDepth >= RightDepth)
{
return LeftDepth+1;
}
else
{
return RightDepth+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);
}整體代碼：
#include <iostream>
#include <queue>
using namespace std;
template <class T>
struct BinaryTreeNode
{
T _data; //數據域
BinaryTreeNode<T>* _left; //指向左子樹
BinaryTreeNode<T>* _right; //指向右子樹
BinaryTreeNode(const T& d)
:_data(d)
,_left(NULL)
,_right(NULL)
{}
};
template<class T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node; //類型重命名，方便后面使用
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(const T* a, size_t size, const T& invilid)
:_root(NULL)
{
size_t index = 0;
_root = _CreateTree(a, size, index, invilid);
}
BinaryTree<T>(const BinaryTree& tree)
{
_root = _Copy(tree._root);
}
BinaryTree& operator= (BinaryTree tree) //現代式寫法
{
swap(_root, tree._root);
return *this;
}
~BinaryTree()
{
if(_root != NULL)
{
_Destroy(_root);
}
}
public:
void PrevOrder()
{
_PrevOrder(_root);
cout<<endl;
}
void InOrder()
{
_InOrder(_root);
cout<<endl;
}
void PostOrder()
{
_PostOrder(_root);
cout<<endl;
}
void LevelOrder()
{
_LevelOrder(_root);
cout<<endl;
}
size_t Size()
{
return _Size(_root);
}
size_t Depth()
{
return _Depth(_root);
}
size_t LeafSize()
{
return _LeafSize(_root);
}
protected:
size_t _Size(Node* root)
{
if(root == NULL)
{
return 0;
}
/* 左子樹節點+右子樹節點+根節點 */
return _Size(root->_left)+_Size(root->_right)+1;
}
size_t _Depth(Node* root)
{
if(root == NULL)
{
return 0;
}
size_t LeftDepth = _Depth(root->_left);
size_t RightDepth = _Depth(root->_right);
if(LeftDepth >= RightDepth)
{
return LeftDepth+1;
}
else
{
return RightDepth+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);
}
protected:
/* 前序遍歷：根->左子樹->右子樹 */
void _PrevOrder(Node* root)
{
if(root == NULL)
{
return;
}
cout<<root->_data<<" "; //打印根節點數據
_PrevOrder(root->_left); //遞歸遍歷左子樹
_PrevOrder(root->_right); //遞歸遍歷右子樹
}
/* 中序遍歷：左子樹->根->右子樹 */
void _InOrder(Node* root)
{
if(root == NULL)
{
return;
}
_InOrder(root->_left); //遞歸遍歷左子樹
cout<<root->_data<<" "; //打印根節點數據
_InOrder(root->_right); //遞歸遍歷右子樹
}
/* 后序遍歷：左子樹->右子樹->根 */
void _PostOrder(Node* root)
{
if(root == NULL)
{
return;
}
_PostOrder(root->_left); //遞歸遍歷左子樹
_PostOrder(root->_right); //遞歸遍歷右子樹
cout<<root->_data<<" "; //打印根節點數據
}
/* 層次遍歷：第一層->最后一層 */
void _LevelOrder(Node* root)
{
queue<Node*> qt;
if(root == NULL)
{
return;
}
qt.push(root);
while(!qt.empty())
{
if(qt.front()->_left != NULL)
{
qt.push(qt.front()->_left);
}
if(qt.front()->_right != NULL)
{
qt.push(qt.front()->_right);
}
cout<<qt.front()->_data<<" ";
qt.pop();
}
}
protected:
Node* _Copy(Node* root)
{
if(root == NULL)
{
return NULL;
}
Node* NewRoot = new Node(root->_data); //創建新的根節點
Node* NewCur = NewRoot;
NewCur->_left = _Copy(root->_left);
NewCur->_right = _Copy(root->_right);
return NewRoot;
}
void _Destroy(Node* root)
{
if(root == NULL)
{
return;
}
if(root->_left == NULL && root->_right == NULL)
{
delete root;
root = NULL;
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
}
Node* _CreateTree(const T* a, size_t size, size_t& index, const T& invilid)
{
Node* root = NULL;
if(index<size && a[index] != invilid)
{
root = new Node(a[index]); //創建根節點
root->_left = _CreateTree(a, size, ++index, invilid);//遞歸實現左子樹
root->_right = _CreateTree(a, size, ++index, invilid);//遞歸實現右子樹
}
return root; //返回根節點
}
protected:
Node* _root; //根節點
};
int main()
{
Test();
system("pause");
return 0;
}測試結構：
測試代碼：
void Test()
{
int array[10] = {1, 2, 3, '#', '#', 4, '#' , '#', 5, 6};
BinaryTree<int> tree(array, 10, '#');
tree.PrevOrder();
tree.InOrder();
tree.PostOrder();
tree.LevelOrder();
BinaryTree<int> tree2(tree);
tree2.PrevOrder();
BinaryTree<int> tree3 = tree2;
tree3.PrevOrder();
}測試結果：
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
