递归实现二叉树

2019-11-08 03:20:24

字体：大中小

来源：转载

供稿：网友

二叉树：在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（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;}

上一篇：request对象和response对象

下一篇：synchronized关键字