二叉樹： 在計算機科學中，二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現二叉查找樹和二叉堆。 二叉樹的每個結點至多只有二棵子樹(不存在度大于2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個結點；深度為k的二叉樹至多有2^k-1個結點；對任何一棵二叉樹T，如果其終端結點數為n_0，度為2的結點數為n_2，則n_0=n_2+1。 一棵深度為k，且有2^k-1個節點稱之為滿二叉樹；深度為k，有n個節點的二叉樹，當且僅當其每一個節點都與深度為k的滿二叉樹中，序號為1至n的節點對應時，稱之為完全二叉樹。
運用遞歸思想簡單實現一顆二叉樹，這里得清楚二叉樹的儲存模式，以及重要的前序中序后序遞歸遍歷二叉樹
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>using namespace std;template<class T>struct BinTreeNode //節點定義{ BinTreeNode(const T& value) :_value(value) , _left(NULL) , _right(NULL) {} BinTreeNode* _left; BinTreeNode* _right; T _value;};template<class T>class BinTree{public: typedef BinTreeNode<T> Node; BinTree(T *a, size_t size, const T& invaild) //構造函數 { size_t index = 0; _root = _CreatBinTree(a, size, index, invaild); } BinTree(const BinTree<T> &b) //拷貝構造 { _root = _Copy(_root); } ~BinTree() //析構 { _root = _Destory(_root); } BinTree<T> Operator=(const BinTree<T> &b) { if (this != &b) { Node* newroot = NULL; newroot = _Copy(b->_root); _root = _Destory(_root); _root = newroot; } return *this; } void _PReOrderPrint() //前序遍歷 { _PreOrder(_root); cout << endl; } void _InfixPrint() //中序遍歷 { _InfixOrder(_root); cout << endl; } void _PostPrint() //后序遍歷 { _PostOrder(_root); cout << endl; } size_t Size() { return _size(_root); } size_t Depth() { return _Depth(_root); }protected: Node* _CreatBinTree(T* a, size_t size, size_t& index, const T& invaild) { Node* newnode = NULL; if (index < size&&a[index] != invaild) { newnode = new Node(a[index]); newnode->_left = _CreatBinTree(a, size, ++index, invaild); newnode->_right = _CreatBinTree(a, size, ++index, invaild); } return newnode; } Node* _Copy(Node* root) { Node* newnode = NULL; if (root != NULL) { newnode = new Node(root->_value); newnode->_left = _Copy(root->_left); newnode->_right = _Copy(root->_right); } return newnode; } Node* _Destory(Node* root) { if (root != NULL) { root->_left = _Destory(root->_left); root->_right = _Destory(root->_right); delete root; root = NULL; } return root; } void _PreOrder(Node* root) { if (root != NULL) { cout << root->_value << " "; _PreOrder(root->_left); _PreOrder(root->_right); } } void _InfixOrder(Node* root) { if (root != NULL) { _InfixOrder(root->_left); cout << root->_value << " "; _InfixOrder(root->_right); } } void _PostOrder(Node* root) { if (root != NULL) { _InfixOrder(root->_left); _InfixOrder(root->_right); cout << root->_value << " "; } } size_t _size(Node* root) { size_t size = 0; if (root != NULL) { ++size; size += _size(root->_left); size += _size(root->_right); } return size; } size_t _Depth(Node *root) { size_t maxdepth = 0; if (root != NULL) { size_t depth = 1; if (root->_left != NULL) { depth += _Depth(root->_left); } if (depth > maxdepth) { maxdepth = depth; } if (root->_right != NULL) { depth = _Depth(root->_right) + 1; } if (depth > maxdepth) { maxdepth = depth; } } return maxdepth; }protected: Node* _root;};int main(){ int a[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }; BinTree<int> b(a, 10, '#'); b._PreOrderPrint(); b._InfixPrint(); b._PostPrint(); cout << b.Size() << endl; cout << b.Depth() << endl; system("pause"); return 0;}新聞熱點
疑難解答
