C++关于二叉树的具体实现

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);
}