二叉树简介
二叉树是一种非线性结构, 二叉树的遍历方式有三种: 前序, 中序和后序. 在学习二叉树的时候, 把二叉树分为三部分: 根结点, 左子树和右子树, 所谓遍历方式即访问这三部分的先后顺序.
我对于二叉树遍历的方式的理解是這样的:
前序遍历: 先访问根结点, 再访问左子树, 最后访问右子树.
中序遍历: 先访问左子树, 再访问根节点, 最后访问右子树.
后序遍历: 先访问左子树, 再访问右子树, 最后访问根结点.
1. 二叉树的建立
- #define _CRT_SECURE_NO_WARNINGS 1
- #include<iostream>
- #include<string>
- #include<assert.h>
- #include<stack>
- #include<queue>
- using namespace std;
- template<class T>
- struct BinaryTreeNode
- {
- T _data;
- BinaryTreeNode<T>* _left;
- BinaryTreeNode<T>* _right;
- BinaryTreeNode(const T& d)
- :_data(d)
- ,_left(NULL)
- , _right(NULL)
- {
- cout <<"构造二叉树结点" << endl;
- }
- };
- template<class T>
- class BinaryTree
- {
- typedef BinaryTreeNode<T> Node;
- private:
- Node* _root;
- protected:
- Node* _CreateTree(T* a, size_t n, const T& invalid, size_t& index)
- {
- //index = 0; Node* root = NULL;
- if (index <n && a[index] != invalid)
- {
- root = new Node(a[index]);
- root->_left = _CreateTree(a, n, invalid, ++index);
- root->_right = _CreateTree(a, n, invalid, ++index);
- }
- return root;
- }
2. 前中后序遍历
- void _PrevOrder(Node* root) // 前序遍历
- {
- if (root == NULL) // 返回条件
- return;
- cout <<root->_data <<" ";
- _PrevOrder(root->_left);
- _PrevOrder(root->_right);
- }
- void _InOrder(Node* root) // 中序遍历
- {
- if (root == NULL) // 返回条件
- return;
- _InOrder(root->_left);
- cout <<root->_data <<" ";
- _InOrder(root->_right);
- }
- void _PostOrder(Node* root) // 后序遍历
- {
- if (root == NULL) // 返回条件
- return;
- _PostOrder(root->_left);
- _PostOrder(root->_right);
- cout <<root->_data << " ";
- }
来源: http://www.bubuko.com/infodetail-3038707.html