目录
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;
}