目录
1.二叉树的结构
2.创建一棵二叉树
3.二叉树的先序遍历
1.借助栈的先序遍历
2.利用递归的先序遍历
4.二叉树的中序遍历
5.二叉树的后序遍历
1.借助栈的后序遍历
2.利用递归的后序遍历
6.二叉树的层序遍历
7.tree.h
8.tree.cpp
9.main.cpp
1.二叉树的结构
对于二叉树来说，它是由无数个结点形成的一棵树，结点的表示如下图：包含两个指针分别指向左右孩子节点，和一个表示本身的值的数。
所以我们可以给出结点的代码为：
struct Node {int val;Node* left;//指向左孩子节点的指针Node* right;//指向右孩子节点的指针Node(int val) {this->val = val;left = nullptr;right = nullptr;}
}; 2.创建一棵二叉树
思路：把数组中的第一个元素作为根节点，比它小的放在它的左子树上，比它大的放在右子树上面
tree::tree(vector<int>& vec) {if (vec.size() == 0) {root = nullptr;return;}root = new Node(vec[0]);for (int i = 1; i < vec.size(); i++) {//先创建结点Node* node = new Node(vec[i]);Node* p = root;while (1) {if (node->val > p->val){if (p->right == nullptr) {p->right = node;break;}p = p->right;}if (node->val < p->val) {if (p->left == nullptr) {p->left = node;break;}p = p->left;}if (p->val == node->val)break;}}
}首先把v[0]这个元素作为根节点，然后遍历后面的元素，先创建值为v[i]的节点，然后找它应该放的位置。如果这个节点 的值大于当前比较的那个节点，就往它的右子树找，如果它的右子树为空，直接放到这个位置上即可。如果它的右子树不为空，那么就将右子树上那个节点作为比较节点，然后又进行比较，重复此过程，直至找到这个节点的位置。
例如给定数组v[]={7,5,4,6,11,9,10}
它的构建过程如下：
1.先创建根节点
2.找5的位置，因为5与7进行比较，比它小，而且7的左孩子为空，直接将5放在7的左孩子上。
3.找4的位置，4比7小，而7的左孩子已经有了，所以往下找，4比5小，而且5的左孩子为空，所以4放到5的左孩子节点上。
4.找6的位置，6比7小，并且7的左孩子节点存在，所以往下找，6比5大，且5的右孩子节点不存在，所以6放到5的右孩子节点上。
5.找11的位置，11比7大，而且7的右孩子节点为空，所以直接放到7的右孩子节点上。
6.找9的位置，9比7大，往右找，比11小，而且11的左孩子节点为空，所以9放到11的左孩子节点上。
7.找10的位置，10比7大，往后找，比11小，往左找，比9大，而且9的右孩子节点为空，所以10放到9的右孩子节点上。
所以最终的二叉树如上图。
3.二叉树的先序遍历
1.借助栈的先序遍历
先序遍历是“根左右”，这里要借助栈来实现它的遍历操作，先将根节点压入到栈中，然后while循环，循环的条件是栈不为空，先弹出栈顶的元素，然后再将右孩子节点压入到栈中，再压左孩子节点。重复此操作。
//先序遍历
void tree::PreOrder(Node* root)
{if (!root)return;stack<Node*> stk;stk.push(root);while (!stk.empty()) {Node* top = stk.top();stk.pop();cout << top->val << " ";if (top->right)stk.push(top->right);if (top->left)stk.push(top->left);}
}2.利用递归的先序遍历
//先序遍历（递归）
void tree::_PreOrder(Node* root) {if (!root) return;cout << root->val<<" ";_PreOrder(root->left);_PreOrder(root->right);}4.二叉树的中序遍历
1.借助栈的中序遍历
中序遍历是“左根右”，同样需要借助栈，先从根节点出发，把所有的左孩子节点全部压入到栈中，然后打印栈顶元素的值，同时cur要指向这个元素的右子树，因为下一次要压入这个右子树，然后移除栈顶元素。
//中序遍历
void tree::InOrder(Node* root) {if (!root)return;stack<Node*> stk;Node* cur = root;while (cur || !stk.empty()) {while (cur) {stk.push(cur);cur = cur->left;}Node* top = stk.top();stk.pop();cout << top->val<<" ";cur = top->right;}}2.利用递归的中序遍历
//中序遍历（递归）
void tree::_InOrder(Node* root) {if (!root) return;_InOrder(root->left);cout << root->val << " ";_InOrder(root->right);
}5.二叉树的后序遍历
1.借助栈的后序遍历
后序遍历是“左右根”，这里需要用到两个栈，一个栈用作辅助，在栈s1中对遍历的节点的顺序进行调整，然后压入到栈s2中，遍历s2的顺序就是后序遍历的顺序。
//后序遍历
void tree::PostOrder(Node* root) {if (!root)return;stack<Node*> s1,s2;s1.push(root);while (!s1.empty()) {Node* top = s1.top();s1.pop();s2.push(top);if (top->left)s1.push(top->left);if (top->right)s1.push(top->right);}while (!s2.empty()) {cout << s2.top()->val << " ";s2.pop();}
}2.利用递归的后序遍历
//后序遍历（递归）
void tree::_PostOrder(Node * root) {if (!root) return;_PostOrder(root->left);_PostOrder(root->right);cout << root->val << " ";
}6.二叉树的层序遍历
利用队列先进先出的特点，先将根节点加入到队列中，然后循环，循环的条件是队列不为空，每次取出队首的元素，同时判断是否有左右孩子，有的话就将其加入到队列尾部。
//层序遍历
void tree::levelOrder(Node* root) {if (root == nullptr)return ;queue<Node*> q;q.push(root);Node* node; while (!q.empty()) { node = q.front();q.pop();cout << node->val<<" ";if (node->left)q.push(node->left);if (node->right)q.push(node->right); }
}我们可以将二叉树形成一个类，在tree.h中对其结构进行声明以及函数的声明，在tree.cpp中对它的函数进行实现，在主函数中对其进行测试，以实现“低耦合高类聚”的特点。下面给出这几个文件的代码。
7.tree.h
#pragma once
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
struct Node {int val;Node* left;Node* right;Node(int val) {this->val = val;left = nullptr;right = nullptr;}
};
class tree
{Node* root;
public:tree():root(nullptr){}//无参构造函数tree(vector<int>& vec); //有参构造函数Node* getroot()const {return root;}void PreOrder(Node* root); //先序遍历void PostOrder(Node* root);//后序遍历void InOrder(Node* root);//中序遍历void _PreOrder(Node* root);//先序遍历（递归）void _PostOrder(Node* root);//后序遍历（递归）void _InOrder(Node* root);//中序遍历（递归）void levelOrder(Node* root);//层序遍历};8.tree.cpp
#include "tree.h"
tree::tree(vector<int>& vec) {if (vec.size() == 0) {root = nullptr;return;}root = new Node(vec[0]);for (int i = 1; i < vec.size(); i++) {//先创建结点Node* node = new Node(vec[i]);Node* p = root;while (1) {if (node->val > p->val){if (p->right == nullptr) {p->right = node;break;}p = p->right;}if (node->val < p->val) {if (p->left == nullptr) {p->left = node;break;}p = p->left;}if (p->val == node->val)break;}}
}//先序遍历
void tree::PreOrder(Node* root)
{if (!root)return;stack<Node*> stk;stk.push(root);while (!stk.empty()) {Node* top = stk.top();stk.pop();cout << top->val << " ";if (top->right)stk.push(top->right);if (top->left)stk.push(top->left);}
}
//后序遍历
void tree::PostOrder(Node* root) {if (!root)return;stack<Node*> s1,s2;s1.push(root);while (!s1.empty()) {Node* top = s1.top();s1.pop();s2.push(top);if (top->left)s1.push(top->left);if (top->right)s1.push(top->right);}while (!s2.empty()) {cout << s2.top()->val << " ";s2.pop();}
}
//中序遍历
void tree::InOrder(Node* root) {if (!root)return;stack<Node*> stk;Node* cur = root;while (cur || !stk.empty()) {while (cur) {stk.push(cur);cur = cur->left;}Node* top = stk.top();stk.pop();cout << top->val<<" ";cur = top->right;}}
//先序遍历（递归）
void tree::_PreOrder(Node* root) {if (!root) return;cout << root->val<<" ";_PreOrder(root->left);_PreOrder(root->right);}
//后序遍历（递归）
void tree::_PostOrder(Node * root) {if (!root) return;_PostOrder(root->left);_PostOrder(root->right);cout << root->val << " ";
}
//中序遍历（递归）
void tree::_InOrder(Node* root) {if (!root) return;_InOrder(root->left);cout << root->val << " ";_InOrder(root->right);
}
//层序遍历
void tree::levelOrder(Node* root) {if (root == nullptr)return ;queue<Node*> q;q.push(root);Node* node; while (!q.empty()) { node = q.front();q.pop();cout << node->val<<" ";if (node->left)q.push(node->left);if (node->right)q.push(node->right); }
}9.main.cpp
#include"tree.h"
int main() { vector<int> vec = { 7,5,4,6,11,9,10 };tree t(vec);cout << "先序遍历的结果：" << endl;t.PreOrder(t.getroot());cout << endl;cout << "先序遍历的结果：（递归）" << endl;t._PreOrder(t.getroot());cout << endl;cout << "中序遍历的结果：" << endl;t.InOrder(t.getroot());cout << endl;cout << "中序遍历的结果：（递归）" << endl;t._InOrder(t.getroot());cout << endl;cout << "后序遍历的结果：" << endl;t.PostOrder(t.getroot());cout << endl;cout << "后序遍历的结果：（递归）" << endl;t._PostOrder(t.getroot());cout << endl;cout << "层序遍历的结果：" << endl;t.levelOrder(t.getroot()); return 0;
}
