一、問題概述

?????? 樹是n個有限個數據的集合，形如：

?????? 它像不像倒著的樹呢？我們把它看成是一種數據結構----樹。它的第一個節點稱作樹的根，最底下的那些節點稱作樹的葉子。

?????? 我們今天所要研究的是二叉樹，即父節點最多只有兩個孩子（左孩子和右孩子）。

二叉樹還有兩種特殊的結構，分為完全二叉樹和滿二叉樹。

如：

滿二叉樹：高度為N的滿二叉樹有2^N-1個節點。

完全二叉樹：高度為N，前N-1層為滿二叉樹，第N層為連續的葉子節點。

二叉樹有四種遍歷方式：

前序遍歷（根左右），中序遍歷（左根右），后序遍歷（左右根），層序遍歷（從上往下，從左往右）。

那么，如何實現一個二叉樹的數據結構呢？

二、數據結構的設計

???????在這里，我們采取鏈表的方式，即創建節點，將節點與節點鏈接起來的方式實現二叉樹。

節點的結構：

（1）將要創建的節點的數據部分存儲到數組里，然后創建節點。讀取數組，我們將指針指向空的部分當作是非法字符，在這里非法字符是‘#’；

（2）如果不是非法字符，則創建節點并鏈接到二叉樹的根上，按照先序遍歷的方式先創建根，再創建根的左，最后創建根的右。

（3）創建完成后，對二叉樹進行相應的操作。如：求葉子節點數，第k層節點數，四種遍歷方式，遞歸和非遞歸實現等。

三、實現代碼

//BinaryTree.h

#pragma once
#include<assert.h>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;template<typename T>
struct BinaryTreeNode  //創建節點
{T _data;BinaryTreeNode<T> *_left;BinaryTreeNode<T> *_right;BinaryTreeNode(const T& data):_data(data), _left(NULL), _right(NULL){}
};template<typename T>
class BinaryTree
{typedef BinaryTreeNode<T> Node;
public:BinaryTree():_root(NULL){}BinaryTree(T* arr,size_t size,const T& invalid = T()){assert(arr);size_t index = 0;_root = CreateTree(arr,size,invalid,index);}BinaryTree(BinaryTree<T> &t){assert(t._root);_root = _Copy(t._root);}//傳統寫法/*BinaryTree<T>& operator=(BinaryTree<T>& t){if (this != &t){Node* tmp = _Copy(t._root);_root = _Destroy(_root);_root = tmp;}return *this;}*///現代寫法BinaryTree<T>& operator=(BinaryTree<T>& t){if (this != &t){BinaryTree<T> tmp(t);std::swap(tmp._root, _root);}return *this;}~BinaryTree(){if (_root){_root = _Destroy(_root);}}
public:size_t Size(){return _Size(_root);}size_t Depth(){return _Depth(_root);}void PreOrder(){_PreOrder(_root);cout << endl;}void InOrder(){_InOrder(_root);cout << endl;}void PostOrder(){_PostOrder(_root);cout << endl;}void LevelOrder(){_LevelOrder(_root);cout << endl;}Node* Find(const T& x){return _Find(_root,x);}public://創建二叉樹Node* CreateTree(T* arr, size_t size, const T& invalid,size_t& index){Node* root = NULL;if (index < size){if (arr[index] != invalid){root = new Node(arr[index]);root->_left = CreateTree(arr, size, invalid, ++index);root->_right = CreateTree(arr, size, invalid, ++index);}}return root;}//拷貝二叉樹Node* _Copy(Node* root){Node* cur = NULL;if (root){cur = new Node(root->_data);cur->_left = _Copy(root->_left);cur->_right = _Copy(root->_right);}return cur;}//釋放二叉樹節點Node* _Destroy(Node* root){if (root != NULL){root->_left = _Destroy(root->_left);root->_right = _Destroy(root->_right);delete root;root = NULL;}return root;}//遞歸求解二叉樹節點的個數size_t _Size(Node* root)     {if (root == NULL)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}//二叉樹的深度求解size_t _Depth(Node* root){size_t maxDepth = 1;if (root){size_t depth = 1;if (root->_left)             //左不為空則遍歷左樹的深度{depth += _Depth(root->_left);}if (depth > maxDepth){maxDepth = depth;}if (root->_right)          //右不為空則在左樹的深度基礎上+1{depth = _Depth(root->_right) + 1;}if (depth > maxDepth){maxDepth = depth;}}return maxDepth;}//二叉樹前序遍歷的遞歸實現void _PreOrder(Node* root){if (root){cout << root->_data << " ";_PreOrder(root->_left);_PreOrder(root->_right);}}//二叉樹中序遍歷的遞歸實現void _InOrder(Node* root){if (root){_InOrder(root->_left);cout << root->_data << " ";_InOrder(root->_right);}}//二叉樹后序遍歷的遞歸實現void _PostOrder(Node* root){if (root){_PostOrder(root->_left);_PostOrder(root->_right);cout << root->_data << " ";}}//二叉樹層序遍歷的實現void _LevelOrder(Node* root){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);}}}//二叉樹中查找某個值的節點Node* _Find(Node* root,const T& data){Node* cur = root;if(root == NULL)return NULL;if(root->_data == data)         //找到則返回節點return root;Node* ret = _Find(cur->_left,data);if(ret == NULL){ret = _Find(cur->_right,data);}return ret;}
public:void PreOrderNonR(){_PreOrderNonR(_root);cout<<endl;}void InOrderNonR(){_InOrderNonR(_root);cout<<endl;}void PostOrderNonR(){_PostOrderNonR(_root);cout<<endl;}
public://二叉樹前序遍歷的非遞歸實現void _PreOrderNonR(Node* root){Node* cur = root;stack<Node*> s;while(!s.empty() || cur){while(cur){cout<<cur->_data<<" ";s.push(cur);cur = cur->_left;}Node* top = s.top();s.pop();cur = top->_right;}}//二叉樹中序遍歷的非遞歸實現void _InOrderNonR(Node* root){Node* cur = root;stack<Node*> s;while(!s.empty() || cur){while(cur){s.push(cur);cur = cur->_left;}Node* top = s.top();cout<<top->_data<<" ";s.pop();cur = top->_right;}}//二叉樹后序遍歷的非遞歸實現void _PostOrderNonR(Node* root){Node* cur = root;stack<Node*> s;Node* prev = NULL;while(!s.empty() || cur){while(cur){s.push(cur);cur = cur->_left;}Node* top = s.top();if(top->_right == NULL || top->_right == prev){cout<<top->_data<<" ";prev = top;s.pop();}else{cur = top->_right;}}}
public:size_t GetKLevelSize(size_t k){assert(_root);size_t level = 1;size_t count = 0;_GetKLevelSize(_root,k,level,count);return count;}//獲取第k層節點的個數（當k等于層數level時，count++，否則分別遍歷左樹和右樹）void _GetKLevelSize(Node* root,size_t k,size_t level,size_t& count){if(root == NULL)return;if(k == level){count++;return;}_GetKLevelSize(root->_left,k,level+1,count);_GetKLevelSize(root->_right,k,level+1,count);}size_t GetLeafSize(){size_t count = 0;_GetLeafSize(_root,count);return count;}//獲取葉子節點（當節點的左樹為空且右樹為空時，即葉子數加1）void _GetLeafSize(Node* root,size_t& count){if(root == NULL)return;if(root->_left == NULL && root->_right == NULL){count++;return;}_GetLeafSize(root->_left,count);_GetLeafSize(root->_right,count);}size_t SizePrev(){size_t count = 0;_SizePrev(_root,count);return count;}//用引用的方法獲取二叉數節點的個數(需要入棧)void _SizePrev(Node* root,size_t& count){if(root == NULL)return;Node* cur = root;stack<Node*> s;while(!s.empty() || cur){while(cur){s.push(cur);count++;cur = cur->_left;}Node* top = s.top();s.pop();cur = top->_right;}}
private:Node* _root;
};void FunTest()
{int arr[] = {1,2,3,'#','#',4,'#','#',5,6};int arr1[] = { 1, 2,'#', 3, '#', '#', 4, 5,'#',6 ,'#', 7,'#','#',8};BinaryTree<int> b1(arr,sizeof(arr)/sizeof(arr[0]),'#');BinaryTree<int> b6(arr1, sizeof(arr1) / sizeof(arr1[0]), '#');BinaryTree<int> b2(b1);BinaryTree<int> b3;b3 = b2;cout << b1.Size() << endl;cout << b2.Size() << endl;cout << b3.Size() << endl;cout << b1.Depth() << endl;cout << b6.Depth() << endl;cout<<"b1：遞歸先序遍歷->";b1.PreOrder();cout<<"b1：遞歸中序遍歷->";b1.InOrder();cout<<"b1：遞歸后序遍歷->";b1.PostOrder();cout<<"b1：層序遍歷->";b1.LevelOrder();cout<<"b1：非遞歸先序遍歷->";b1.PreOrderNonR();cout<<"b1：非遞歸中序遍歷->";b1.InOrderNonR();cout<<"b1：非遞歸后序遍歷->";b1.PostOrderNonR();cout<<"Find(4)?"<<endl;cout<<b1.Find(4)->_data<<endl;cout<<"GetLeafSize:"<<b1.GetLeafSize()<<endl;cout<<"_SizePrev:"<<b1.SizePrev()<<endl;cout<<"b6：遞歸先序遍歷->";b6.PreOrder();cout<<"b6：遞歸中序遍歷->";b6.InOrder();cout<<"b6：遞歸后序遍歷->";b6.PostOrder();cout<<"b6：遞歸層序遍歷->";b6.LevelOrder();cout<<"第三層節點數:"<<b6.GetKLevelSize(3)<<endl;cout<<"第四層節點數:"<<b6.GetKLevelSize(4)<<endl;cout<<"第五層節點數:"<<b6.GetKLevelSize(5)<<endl;cout<<"GetLeafSize:"<<b6.GetLeafSize()<<endl;cout<<"_SizePrev:"<<b6.SizePrev()<<endl;
}

//BinaryTree.cpp

#include<iostream>
using namespace std;
#include"BinaryTree.h"
int main()
{FunTest();return 0;
}

四、運行結果

前一篇廣義表的數據結構和二叉樹的數據結構也有一些類似哦。大家可以看看噠^-^