二叉树的构建及其前中后序遍历（c++）

---

我们要解决的问题：

给定一个长度为len的int类型数组，构造一棵二叉树，并输出这棵树的前中后序遍历。

---

二叉树由一个个的节点构成，每个节点包含三个东西，分别是这个节点的数据，这个节点的左儿子的地址和右儿子的地址，所以这里使用结构体来表示一个节点。

---

所以，先写二叉树节点的代码

struct Binary_node { int data; //这个节点的数据 Binary_node *left; //左儿子的地址 Binary_node *right; //右儿子的地址 Binary_node(int x):left(0),right(0){data = x} //这个节点的构造函数，左右儿子的地址赋初值为0（也就是NULL），这个节点的数据为传过来的参数x };

---

然后写一个二叉树的类的声明

class Binary_tree { private: Binary_node *root;//树根 public: Binary_tree();//默认构造函数 Binary_tree(int *arr, int len);//传入数组及其长度的构造函数（这个函数是重点啊） void pre_order(const Binary_node *p);//前序遍历的递归函数 void pre_print();//前序遍历的方法 void in_order(const Binary_node *p);//中序遍历的递归函数 void in_print();//中序遍历的方法 void post_order(const Binary_node *p);//后序遍历的递归函数 void post_print();//后序遍历的方法 };

---

·数据结构的一个规定：能够在main程序里面被调用的一般叫做【方法】，其他的叫做【函数】。

---

接下来写Binary__tree类里面的函数和方法的实现

Binary_tree::Binary_tree()//这个构造函数，好像没什么用，留着吧，也不碍事 { root = NULL; } Binary_tree::Binary_tree(int *arr, int len)//这是一个重要的构造函数 { root = NULL; int index = 0; while (len--){//一共有len个元素，也就是最多有len个节点，循环次数为len次 if (root == NULL){//这个if用来构造根节点 root = new Binary_node(arr[index++]); continue; } Binary_node *p = root; int tmp = arr[index++]; /*下面的这个while有两个用处。 第一：判断条件，去掉重复，就是说这棵树不包含相同的元素。 第二：因为最新插入的元素只能是叶子节点，如果前面已经构造了一棵巨大的树， 那么我们就需要用一个循环来定位到叶子节点的父节点，也就是前几行的p。*/ while (p->data!=tmp){ if (tmp > p->data){//这个if的责任：将那个数值比节点p大的往p的右子树移动 if (p->right != NULL) p = p->right;//将p一层层往下挪 else { p->right = new Binary_node(tmp);//创建新的叶子节点，用来安放当前元素 break;//跳出循环，表示当前元素已经放到树里面了 } } else{//这个else的责任：将那个数值比节点p小的往p的左子树移动 if (p->left != NULL) p = p->left;//同理 else { p->left = new Binary_node(tmp);//同理 break; } } } } } void Binary_tree::pre_order(const Binary_node *p)//前序遍历函数 { //前序遍历的顺序是：先访问节点，再访问左子树，最后访问右子树 if (p == NULL)return;//递归终止条件 cout << p->data << ' ';//访问节点 pre_order(p->left);//访问左子树 pre_order(p->right);//访问右子树 } void Binary_tree::pre_print()//前序遍历方法（注意函数与方法的区别，前面讲了） { pre_order(root); cout << endl; } void Binary_tree::in_order(const Binary_node *p)//中序遍历，同理（只写了函数，没写方法，我偷懒啦） { //中序遍历的顺序：先访问节点的左子树，然后访问节点，最后访问右子树 if (p == NULL)return; in_order(p->left); cout << p->data << ' '; in_order(p->right); } void Binary_tree::post_order(const Binary_node *p)//后序遍历，同理（只写了函数，没写方法，我偷懒啦） { //后续遍历顺序：先访问节点的左子树，然后访问右子树，最后访问节点 if (p == NULL)return; post_order(p->left); post_order(p->right); cout << p->data << ' '; }

---

·【访问】的意思指的是打印出这个节点的数值

---

最后写一下main函数

#include <iostream> #include "头文件.h"//包含二叉树的实现的头文件 using namespace std; int main() { int num; cin >> num ; int *arr = new int[num] ; for(int i = 0; i < num; i++)cin >> arr[i]; Binary_tree apple_tree(arr,num); apple_tree.pre_print(); return 0; }

---

·*请仔细阅读代码的注释，我所有的想法都写在注释里面了。

---

欢迎交流，欢迎评论。