1、前序，中序，后序
原理差不多，利用递归，只是各自的相对顺序不同而已
2、层序遍历
用了广度优先遍历
用队列去存储根节点
只要根节点的左孩子和右孩子不为空，继续入队
然后将根节点出队
直到队列中无元素为止
出队顺序即为层序遍历顺序
代码：
/** *作者：魏宝航 *2020年11月27日,下午15:08 */ #include<iostream> #include<vector> #include<queue> using namespace std; class Node { public: char ch; Node* left; Node* right; Node() { ch = '\0'; left = NULL; right = NULL; } Node(char ch, Node* left, Node* right) { this->ch = ch; this->left = left; this->right = right; } }; static int i = 0; //#号法创建二叉树 Node* CreateTree(vector<char> arr,Node* root) { if (i < arr.size()) { char temp = arr[i++]; if (temp == '#') { return NULL; } else { root = new Node(); root->ch = temp; root->left = CreateTree(arr, root->left); root->right = CreateTree(arr, root->right); } } return root; } //二叉树的前序遍历 void preOrder(Node* root) { if (root == NULL) { return; } cout << root->ch << " "; preOrder(root->left); preOrder(root->right); } //二叉树的中序遍历 void midOrder(Node* root) { if (root == NULL) { return; } midOrder(root->left); cout << root->ch << " "; midOrder(root->right); } //二叉树的后序遍历 void postOrder(Node* root) { if (root == NULL) { return; } postOrder(root->left); postOrder(root->right); cout << root->ch << " "; } //二叉树的层序遍历 void levelOrder(Node* root) { queue<Node*> q; q.push(root); while (!q.empty()) { Node* temp = q.front(); cout << temp->ch << " "; q.pop(); if (temp->left != NULL) { q.push(temp->left); } if (temp->right != NULL) { q.push(temp->right); } } } int main() { vector<char> v; char arr[] = { 'A','B','D','#','#','E','#','#','C','#','F','#','#' }; char arr1[] = { '#' }; for (int i = 0; i < 13; i++) { v.push_back(arr[i]); } Node* root=new Node(); root=CreateTree(v,root); preOrder(root); midOrder(root); postOrder(root); levelOrder(root); }
