这篇文章主要介绍了C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）的相关资料,这里提供实例代码来帮助大家理解掌握二叉树，需要的朋友可以参考下
C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）
二叉树的性质：
二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。
例：
实例代码：
#include #include #include using namespace std; template struct BinaryTreeNode { int _data; BinaryTreeNode* _left; //左孩子 BinaryTreeNode* _right; //右孩子 BinaryTreeNo<i style="color:transparent">来源gaodai$ma#com搞$$代**码网</i>de(const T& data) :_data(data) , _left(NULL) , _right(NULL) {} }; template class BinaryTree { typedef BinaryTreeNode Node; public: BinaryTree() :_root(NULL) {} BinaryTree(T* arr, size_t n, const T& invalid=T()) { size_t index = 0; _root = _CreatTree(arr, n, invalid, index); } void PreOrderR() //前序遍历 递归 { _PreOrderR(_root); } void PreOrder() //前序遍历 非递归 { _PreOrder(_root); } void InOrderR() //中序遍历 递归 { _InOrderR(_root); } void InOrder() //中序遍历 非递归 { _InOrder(_root); } void PostOrderR() //后序遍历 左 右 根 递归 { _PostOrderR(_root); } void PostOrder() //后序遍历 左 右 根 非递归 { _PostOrder(_root); } ~BinaryTree() {} protected: //建树 arr:建树使用的数组 n：数组大小 invalid:非法值 index:当前下标 Node* _CreatTree(T* arr, size_t n, const T& invalid, size_t& index) { Node* root = NULL; if (index _left = _CreatTree(arr, n, invalid, ++index); root->_right = _CreatTree(arr, n, invalid, ++index); } return root; } void _PreOrderR(Node* root) //前序遍历 递归 { if (root == NULL) { return; } cout <_data <_left); _PreOrderR(root->_right); } void _PreOrder(Node* root) //前序遍历 非递归 { stack tty; while (root != NULL || !tty.empty()) { if (root) { cout <_data <_left; } else { Node* temp = tty.top(); tty.pop(); root = temp->_right; } } } void _InOrderR(Node* root) //中序遍历 递归 { if (root == NULL) { return; } _InOrderR(root->_left); cout <_data <_right); } void _InOrder(Node* root) //中序遍历 非递归 { if (root == NULL) { return; } stack tty; while (root != NULL || !tty.empty()) { while (root) { tty.push(root); root = root->_left; } //此时出了循环走到了最左叶子节点 Node* temp = tty.top(); tty.pop(); cout <_data <_right; } } void _PostOrderR(Node* root) //后序遍历 左 右 根 递归 { if (root == NULL) { return; } _PostOrderR(root->_left); _PostOrderR(root->_right); cout <_data << " "; } void _PostOrder(Node* root) //后序遍历 左 右 根 非递归 { if (root == NULL) { return; } stack tty; Node* PreNode = NULL; //上一个访问的结点 tty.push(root); while (!tty.empty()) { Node* cur = tty.top(); //访问的当前节点左右孩子均为空或者当前节点左右子树均已经访问过 if ((cur->_left == NULL && cur->_right == NULL) || ((PreNode != NULL) && (PreNode == cur->_left || PreNode == cur->_right))) { cout <_data <_right != NULL) { tty.push(cur->_right); } if (cur->_left != NULL) { tty.push(cur->_left); } } } } protected: Node* _root; };
#include "源.h" void Test() { int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }; BinaryTree p(array, sizeof(array) / sizeof(array[0]), '#'); cout << "前序递归遍历： " << ""; p.PreOrderR(); cout << endl; cout << "前序非递归遍历： " << ""; p.PreOrder(); cout << endl; cout << "中序递归遍历： " << ""; p.InOrderR(); cout << endl; cout << "中序非递归遍历： " << ""; p.InOrder(); cout << endl; cout << "后序递归遍历： " << ""; p.PostOrderR(); cout << endl; cout << "后序非递归遍历： " << ""; p.PostOrder(); cout << endl; } int main() { Test(); system("pause"); return 0; }
实现
以上就是数据结构二叉树的详解，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
以上就是C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）
转载请注明原文链接：C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）
