递归与非递归实现二叉树

2022-03-27 01:34| 来源: 网络整理| 查看: 265

递归与非递归实现二叉树发布时间：2020-06-29 17:30:29 来源：网络阅读：398 作者：威尼斯小艇栏目：编程语言

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^（i - 1）个结点；深度为k的二叉树至多有2^k - 1个结点。由于树的定义是递归实现的，所以在进行二叉树的前序、中序和后序遍历可通过递归实现，但也可通过非递归的栈来实现，二叉树的层次遍历可通过队列实现。

下面我对二叉树及前序、中序、后序遍历二叉树等方法进行实现

例如二叉树:

递归与非递归实现二叉树

测试用例：

int arrary[10] = {1,2,3,'$','$',4,'$','$',5,6};

arrary为上图所示二叉树，通过前序存储的，'$'表示非法值，即没有结点

二叉树的结构：

template struct BinaryTreeNode { BinaryTreeNode* _left; BinaryTreeNode* _right; T _data; BinaryTreeNode(); BinaryTreeNode(const T& x); }; template class BinaryTree { typedef BinaryTreeNode Node; public: BinaryTree(); BinaryTree(const T* a, size_t size, const T& invalid); BinaryTree(const BinaryTree& t); BinaryTree& operator=(BinaryTree t); ~BinaryTree(); void PrevOrder();//前序遍历-递归 void InOrder();//中序遍历-递归 void PostOrder();//后序遍历-递归 void PrevOrder_NonR();//前序遍历-非递归 void InOrder_NonR();//中序遍历-非递归 void PostOrder_NonR();//后序遍历-非递归 void LevelOrder();//层次遍历 size_t Size();//结点个数 size_t Depth();//树的深度 size_t LeafSize();//叶子结点个数 size_t GetkLevel();//第k层结点个数 protected: Node* _CreateTree(const T* a, size_t size, size_t& index, const T& invalid);//树的建立 Node* _CopyTree(Node* t);//复制树 void _Distory(Node* root);//清空结点，先释放子树，再释放根结点 void _PrevOrder(Node* root);//前序遍历 void _InOrder(Node* root);//中序遍历 void _PostOrder(Node* root);//后序遍历 size_t _Size(Node* root);//结点个数 size_t _Depth(Node* root);//树的深度 //size_t _LeafSize(Node* root);//叶子结点个数 size_t _LeafSize(Node* root,size_t& size);//叶子结点个数 //size_t _GetkLevel(int k, Node* root);//第k层结点个数 size_t _GetkLevel(int k, Node* root, int& size, int level);//第k层结点个数 private: Node* _root;// BinaryTreeNode* _root; };

二叉树的构造、拷贝构造、赋值运算和析构的实现，由于二叉树存在左子树和右子树，故用递归实现其功能，具体实现如下：

template BinaryTreeNode::BinaryTreeNode() :_left(NULL) , _right(NULL) , _data(0) {} template BinaryTreeNode::BinaryTreeNode(const T& x) : _left(NULL) , _right(NULL) , _data(x) {} template BinaryTree::BinaryTree() :_root(NULL) {} template BinaryTree::~BinaryTree() { _Distory(_root); } template void BinaryTree::_Distory(Node* root)//清空结点，先释放子树，再释放根结点 { if (root == NULL) { return; } if (root->_left)//递归释放子结点 { _Distory(root->_left); } if (root->_right) { _Distory(root->_right); } delete root; root = NULL; } template BinaryTree::BinaryTree(const T* a, size_t size, const T& invalid) { size_t index = 0;//标记数组下标 _root = _CreateTree(a, size, index, invalid); } template BinaryTreeNode* BinaryTree::_CreateTree(const T* a, size_t size, size_t& index, const T& invalid)//树的建立 { Node* root = NULL; if (index _right = _CreateTree(a, size, ++index, invalid);//右子树递归 } return root; } template BinaryTree::BinaryTree(const BinaryTree& t) { _root = _CopyTree(t._root); } template BinaryTreeNode* BinaryTree::_CopyTree(Node* t)//此处的返回类型不能用Node表示 { Node* root = NULL; if (t != NULL) { root = new Node(t->_data); root->_left = _CopyTree(t->_left); root->_right = _CopyTree(t->_right); } return root; } template BinaryTree& BinaryTree::operator=(BinaryTree t)//现代写法 { if (this != &t) { BinaryTree tmp = t; swap(_root, tmp._root); } return *this; }

前序遍历(先根遍历)：(1)先访问根节点；(2)前序访问左子树；(3)前序访问右子树.【1 2 3 4 5 6】

下面分别用递归和非递归两种方法实现。

二叉树的递归实现前序遍历

//递归实现 template void BinaryTree::PrevOrder()//前序遍历(先根结点) { _PrevOrder(_root); } template void BinaryTree::_PrevOrder(Node* root) { if (root == NULL) { return; } cout _left); } } cout _right); } //方法二:在LeafSize中定义_size表示叶子结点个数 template size_t BinaryTree::LeafSize()//叶子结点个数 { size_t _size = 0; return _LeafSize(_root, _size); } template size_t BinaryTree::_LeafSize(Node* root, size_t& size) { if (root == 0) { return 0; } if (root->_left == 0 && root->_right == 0) { ++size; return size; } _LeafSize(root->_left, size); _LeafSize(root->_right, size); return size; }

二叉树中第k层结点的个数，递归实现：

//方法一 template size_t BinaryTree::GetkLevel(int k) { assert(k>0); return _GetkLevel(k, _root); } template size_t BinaryTree::_GetkLevel(int k, Node* root)//第k层结点个数 { if (root == NULL) { return 0; } if (k == 1)//利用递归使k递减，k==1结束 { return 1; } size_t size1 = _GetkLevel(k - 1, root->_left); size_t size2 = _GetkLevel(k - 1, root->_right); return size1 + size2; } //方法二:在GetkLevel中定义size表示第k层结点个数 template size_t BinaryTree::GetkLevel(int k) { assert(k > 0); int size = 0;//size为二叉树第level层结点个数 int level = 1;//第level层 return _GetkLevel(k, _root, size, level); } template size_t BinaryTree::_GetkLevel(int k, Node* root, int& size, int level)//第k层结点个数 { if (root == NULL) { return 0; } if (level == k) { ++size; return size; } _GetkLevel(k, root->_left, size, level+1); _GetkLevel(k, root->_right, size, level+1); return size; }

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：[email protected]进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。

二叉树中序遍历先序遍历上一篇新闻：python中excel单元格换行的方法下一篇新闻：如何找到mongodb安装目录香港云服务器

10000元红包免费领

红包可用于（云服务器、高防服务器、裸金属服务器、高防IP、云数据库、CDN加速）购买和续费

猜你喜欢 python代码用cmd打开的步骤用notepad运行python的方法 python读入图像的方法 PHP中的PSR是什么 JAVA的知识点总结 PHP中的Session是什么 PHP中的Cookie怎么用 Java入门可以看什么书 java实现堆栈的方法 python转成exe文件的方法

【本文地址】

公司简介

联系我们