二叉树的基本操作

二叉树的创建构建二叉树的类对象创建二叉树 先序遍历递归非递归 中序遍历递归非递归 后序遍历递归非递归 层序遍历求解二叉树的高度最大高度最小高度

二叉树的创建

构建二叉树的类对象

在创建一棵二叉树之前，我们先创建一个二叉树的类对象Tree。类中包含的成员变量有：val、left、right，函数接口包括：先序遍历、中序遍历、后序遍历、层序遍历、二叉树高度

typedef int TreeElemt; class Tree{ public: enum Mode{NUM, CHAR}; private: TreeElemt val; Tree *left; Tree *right; Mode mode; public: Tree(); // 默认构造函数 Tree(TreeElemt ch); // 构造一个val为ch的结点 ~Tree(); // 前中后层序遍历 void PreOrder(); void InOrder(); void PostOrder(); // 前中后层序遍历——非递归 friend void PreOrder_(const Tree* t); friend void InOrder_(Tree* t); friend void PostOrder_(Tree* t); // 层序遍历 friend void LevelOrder_(Tree* t); // 二叉树的最大高度 int maxHeight(); // 二叉树的最小高度:根节点到叶子结点（注意是到叶子节点） int minHeight(); // 初始化二叉树 friend Tree* InitialTree(const std::vector<TreeElemt>& t, int i); };

由于有些函数用成员函数不好操作，所以我将函数设置为友元 下面我们将逐步实现上面类中的接口函数。

创建二叉树

// 创建二叉树 Tree* InitialTree(const std::vector<TreeElemt>& t, int i){ Tree* root = new Tree(t[i]); // 构建根节点 if (2 * i + 1 < t.size()) root->left = InitialTree(t, 2 * i + 1); // 构建左子树 if (2 * i + 2 < t.size()) root->right = InitialTree(t, 2 * i + 2); // 构建右子树 return root; }

先序遍历

先序遍历的顺序：中左右 如下图所示： 使用先序遍历的结果为：1,2,4,8,9,5,3,6,7

递归

使用递归的方法非常好理解：

先访问根节点；然后递归地访问左子树；再递归的访问右子树。

代码：

// 先序遍历 void Tree::PreOrder(){ if (this) { cout << this->val << " "; // 访问根节点； this->left->PreOrder(); // 递归地访问左子树； this->right->PreOrder(); // 递归的访问右子树。 } }

非递归

使用非递归需要用到栈来存储节点

将根节点先压入栈中取出栈顶结点由于栈的性质是“先进后出”，因此先将右子树压入栈中，然后再将左子树压入栈中，这样在处理时就是先处理左子树，再处理右子树了。

代码：

// 前 void PreOrder_(const Tree* t){ /// 使用非递归求解需要用到栈 /// 思路：将根节点入栈，当弹出一个结点的时候就将它的两个子节点入栈， /// 由于要先输出左子树，而栈是先进后出，所以应该先压入右子树 stack<const Tree*> s; // 将根节点压入栈中 s.push(t); while (!s.empty()) { const Tree* root = s.top(); cout << s.top()->val << " "; s.pop(); if (root->right) s.push(root->right); // 右子树存在，右子树入栈 if (root->left) s.push(root->left); // 左子树存在，左子树入栈 } }

中序遍历

中序遍历的顺序：左中右 那么上面的图使用中序遍历的结果为：8，4，9，2，5，1，6，3，7

递归

使用递归的方法相比于先序遍历只是换了一下处理节点的位置：

然后递归地访问左子树；先访问根节点；再递归的访问右子树。

代码：

// 中序遍历 void Tree::InOrder(){ if (this) { this->left->InOrder(); cout << this->val << " "; this->right->InOrder(); } }

非递归

由于中序遍历最先访问的是最左边的节点，因此我们需要将左结点全部压入栈中，然后弹出栈顶结点，判断栈顶结点有没有右子树，如果有的话就转而处理右子树，没有的话就继续弹出栈中的元素。 使用非递归进行中序遍历的步骤：

将左子树全部压入栈中弹出栈顶元素，判断该栈顶元素是否有右子树，如果有则处理右子树，即将右子树中的左右左节点压入栈中；如果没有右子树就继续处理栈顶结点。如此循环，

代码:

// 中 void InOrder_(Tree * t) { /// 思路：先将所有的左节点入栈，然后弹出一个结点，判断它有没有右节点，有则入栈 if (t == NULL) return; stack<Tree*> s; s.push(t); t = t->left; while (!s.empty() || t) { // 将所有左子树入栈 while (t) { s.push(t); t = t->left; } bool flag = true; // 通过一个flag来控制当前处理的是否为栈顶元素，如果是为true，不是为false while (!s.empty() && flag) { Tree* p = s.top(); cout << p->val << " "; s.pop(); if (p->right) { t = p->right; flag = false; } } } }

后序遍历

后序遍历的顺序：左右中 那么上面的图使用中序遍历的结果为：8，9，4，5，2，6，7，3，1

递归

同先序遍历，递归步骤：

然后递归地访问左子树；再递归的访问右子树；先访问根节点。

代码：

// 后序遍历 void Tree::PostOrder(){ if (this) { this->left->PostOrder(); this->right->PostOrder(); cout << this->val << " "; } }

非递归

后序遍历的非递归相对麻烦一点，需要设置两个控制量，一个用来保存上一次访问过的结点，一个用来控制当前访问的结点是否为栈顶结点，这个与中序遍历中的flag作用相同。 那么我们为什么要设置一个用来保存上次是否访问过的结点？**因为后序遍历中，我们必须先弹出右结点之后才能弹出根结点，那么在处理栈顶结点的时候我们先要判断该栈顶结点是否有右结点，如果有的话就要转去处理右节点，此时作为根结点的栈顶结点依旧在栈中，而处理完右结点后，这个根结点就不是栈顶结点了，那么这个根结点之后还有成为栈顶结点的一天，而当我们第二次访问它的时候肯定是它的右结点已经被弹出之后，那么它的上一次访问的结点肯定就是它的右子树。于是，我们需要将这个根节点弹出。 后序遍历的顺序：

将所有的左子树压入栈中；获取栈顶结点，判断栈顶结点的右子树是否等于上次访问的结点，如果等于则弹出该结点；否则就转而处理它的右节点。再循环1、2

代码：

// 后 void PostOrder_(Tree * t){ /// 思路：将所有的左子树压入栈中，获取栈顶元素（先不弹出），判断其右子树是不是刚刚访问过的结点 /// 如果是，那么就把这个结点弹出来，如果不是，那么久转而处理它的右子树。将它的右子树压入栈中。 if (t == NULL) return; Tree *r; // 保存上一个访问过的结点，对于还未有访问的时候它未null stack<Tree*> s; bool flag; // 用来判断当前处理的结点是栈顶结点还是右节点 s.push(t); t = t->left; while (!s.empty()){ while (t){ s.push(t); t = t->left; } r = NULL; flag = true; while (!s.empty() && flag) { t = s.top(); // 获取栈顶元素 // 如果栈顶元素 == 刚刚访问过的元素，那么就弹出栈顶元素 if (t->right == r) { cout << t->val << " "; s.pop(); r = t; // r就指向本次访问的结点，对于下次访问的结点而言，它是刚访问过的结点 } // 如果栈顶元素 != 刚访问过的元素，那么就处理栈顶元素的右节点 else{ t = t->right; flag = false; // 此时开始处理右节点，关闭处理栈顶结点的窗口 } } } }

层序遍历

层序遍历用的数据结构是队列，利用队列的“先进先出”性质

将根结点压入队列中弹出队列中的第一个结点，并将该结点的左子树压入队列，再将结点的右子树压入队列。循环2

代码：

// 层 void LevelOrder_(Tree * t){ /// 思路：使用队列，将根节点放入队列中，取出根节点，放入左子树，放入右子树 if(t==NULL) return; queue<Tree*> q; q.push(t); while (!q.empty()){ t = q.front(); cout << t->val << " "; q.pop(); if (t->left) q.push(t->left); if (t->right) q.push(t->right); } }

求解二叉树的高度

递归求解二叉树的高度 递归终止条件：root == NULL

最大高度

代码：

// 树的最大高度 int Tree::maxHeight(){ if(this == NULL) return 0; return max(left->maxHeight(), right->maxHeight()) + 1; }

最小高度

这里求的最小高度是从根节点到叶子节点的最小高度（来源leetcode），因此需要对root->left为空或者root->right为空的情况特别考虑。 如果没有强调说是到达叶子节点的最小高度那么就直接将最大高度中的max改为min

int Tree::minHeight(){ if (this == NULL) return 0; int h = INT_MAX; if (this->right == NULL) return this->left->minHeight() + 1; if (this->left == NULL) return this->right->minHeight() + 1; return min(this->left->minHeight(), this->right->minHeight()) + 1; }