树

1.二叉树的基本操作

这是下面所有题目的基础，所有题目要用到的东西都可以从这里copy，这里用到的遍历算法是最基础的递归实现算法，循环算法可自行百度。

题目描述：

设计二叉树类，能够对二叉树进行先序、中序、后序和层序遍历，遍历的操作为输出结点的值，设计主函数，输入一棵二叉树，按先序、中序、后序、层序的遍历顺序输出结点的值。二叉树的结点数不超过20。

输入描述：

输入数据只有一组, 二叉树的结点均为一个数字， 数据为0代表当前结点为空。输入结点的值按照二叉树的先序遍历顺序, 比如输入:1 2 4 0 0 5 0 0 3 0 6 0 0,0表示空,输入的数字之间由空格分隔。

​ 1

​ / \

​ 2 3

/ \ \

4 5 6

输出描述：

输出先序、中序、后序和层序遍历二叉树得到的序列，各占一行，同一行的数字之间由空格分隔。

输入样例:

1 2 4 0 0 5 0 0 3 0 6 0 0

输出样例:

1 2 4 5 3 6

4 2 5 1 3 6

4 5 2 6 3 1

1 2 3 4 5 6

#include<iostream> using namespace std; struct BiNode { int data; BiNode* lchild, * rchild; }; class Bitree { public: Bitree() { root = creat(); } ~Bitree() { Release(root); } void PreOrder() { PreOrder(root); } void InOrder() { InOrder(root); } void PostOrder() { PostOrder(root); } void LeverOrder(); private: BiNode* root; BiNode* creat(); void Release(BiNode* bt); void PreOrder(BiNode* bt); void InOrder(BiNode* bt); void PostOrder(BiNode* bt); }; void Bitree::PreOrder(BiNode* bt) //前序遍历 { //TODO if (bt == NULL)return; else { cout << bt->data << " "; PreOrder(bt->lchild); PreOrder(bt->rchild); } } void Bitree::InOrder(BiNode* bt) //中序遍历 { //TODO if (bt == NULL)return; else { InOrder(bt->lchild); cout << bt->data << " "; InOrder(bt->rchild); } } void Bitree::PostOrder(BiNode* bt) //后序遍历 { if (bt == NULL)return; //TODO PostOrder(bt->lchild); PostOrder(bt->rchild); cout << bt->data << " "; } void Bitree::LeverOrder() //层次序遍历 { //TODO BiNode* Q[100], * q = NULL; int front = -1; int rear = -1; if (root == NULL)return; Q[++rear] = root; while (front != rear) { q = Q[++front]; cout << q->data << " "; if (q->lchild != NULL)Q[++rear] = q->lchild; if (q->rchild != NULL)Q[++rear] = q->rchild; } } BiNode* Bitree::creat() //建立二叉树 { //TODO BiNode* bt; int number; cin >> number; if (number == 0)bt = NULL; else { bt = new BiNode; bt->data = number; bt->lchild = creat(); bt->rchild = creat(); } return bt; } void Bitree::Release(BiNode* bt) //销毁二叉树 { //TODO if (bt == NULL)return; else { Release(bt->lchild); Release(bt->rchild); delete bt; } } int main() { Bitree b; b.PreOrder(); cout << endl; b.InOrder(); cout << endl; b.PostOrder(); cout << endl; b.LeverOrder(); return 0; }

2.求二叉树中结点个数

题目描述

建立一棵二叉树，用二叉链表存储二叉树，计算二叉树中包含的结点个数。

输入描述

输入的数据只有一组，是一棵二叉树的先序遍历序列，结点的值为一个小写字母，＃号表示空结点，如输入：a b d e # # f # # # c # #，数据之间空一个格，得到的二叉树如下。

输出描述

输出二叉树的结点个数，空树输出NULL。

输入样例1：

a b c # # # d e # # f # #

输出样例1：

6

思路

求节点数非常的简单，就是遍历一个个遍历一遍，然后count++就能得到节点数了。至于用什么去遍历，那就是你的事情了。这里我用的是循环算法，用的数据结构是栈来保存根节点 。

#include<iostream> using namespace std; struct Binode { char data; Binode* lchild, * rchild; }; class Bitree { public: Bitree() { root = Creat(root); } ~Bitree() { Release(root); } int Count() { return Count(root); } private: int n; Binode* root; Binode* Creat(Binode* bt); void Release(Binode* bt); int Count(Binode* bt); }; Binode* Bitree::Creat(Binode* bt) { char d; cin >> d; if (d == '#') bt = NULL; else { bt = new Binode; bt->data = d; bt->lchild = Creat(bt->lchild); bt->rchild = Creat(bt->rchild); } return bt; } void Bitree::Release(Binode* bt) { if (bt != NULL) { Release(bt->lchild); Release(bt->rchild); delete bt; } } //这里使用非递归算法实现 int Bitree::Count(Binode* bt) { //ToDo int count = 0; bt = root; Binode* s[100]; int top = -1; while (bt != NULL || top != -1) { while (bt!=NULL) { s[++top] = bt; bt = bt->lchild; count++;//只要不为空，count++ } if (top!=-1) { bt = s[top--]; bt = bt->rchild; } } return count; } int main() { //ToDo Bitree bt; cout << bt.Count(); return 0; }

3.求二叉树叶子结点数

题目描述:

二叉树结点的数据类型是字符型，按先序遍历建立二叉树，求叶子结点的个数。

输入描述:

输入扩展二叉树的先序遍历序列，其中空字符为“#”，以空格隔开.

输出描述:

输出叶子结点的个数.

输入样例:

A B D H # # # E # I # # C F J # # # G # #

输出样例:

4

思路

需要注意的地方有先序建立和遍历，输出的是叶子节点 。那么同样的也需要遍历一遍树，其实可以理解为上一题，区别在于上一题求的是所有节点，而本题是叶子节点。那么叶子节点的特点是什么呢？就是

bt->lchild==NULL&&bt->rchild==NULL

那么我只需要在遍历所有节点的时候加上这个条件判断是不是叶子节点即可。

#include<iostream> using namespace std; struct BiNode { char data; BiNode* lchild, * rchild; }; int j = 0;//一个统计叶子节点数的全局变量，其实这样不太好，不过题目是这样给的。 class BiTree { public: BiTree() { root = Creat(root); } ~BiTree() { Release(root); } void Preorder() { Preorder(root); } private: BiNode* root; BiNode* Creat(BiNode* bt); void Release(BiNode* bt); void Preorder(BiNode* bt); }; void BiTree::Preorder(BiNode* bt) //千序遍历求叶子结点数 { //TODO if (bt == NULL)return; else { if (bt->lchild==NULL&&bt->rchild==NULL){ j++; } Preorder(bt->lchild); Preorder(bt->rchild); } } BiNode* BiTree::Creat(BiNode* bt) //建立二叉树 { //TODO char d; cin >> d; if (d == '#') bt = NULL; else { bt = new BiNode; bt->data = d; bt->lchild = Creat(bt->lchild); bt->rchild = Creat(bt->rchild); } return bt; } void BiTree::Release(BiNode* bt) //销毁二叉树 { //TODO if (bt != NULL) { Release(bt->lchild); Release(bt->rchild); delete bt; } } int main() { BiTree B; B.Preorder(); cout << j; return 0; }

4.按中序输出二叉树中的分支结点

题目描述

二叉树的结点数据域是字符型 ，空用‘#’表示，按前序遍历建立二叉树，按中序输出二叉树中所有的分支结点，以空格隔开。

输入描述

输入二叉树的扩展二叉树的前序遍历序列

输出描述

按中序输出二叉树中所有的分支结点，以空格隔开，最后一个结点后面有空格，占一行。

输入样例

AB#C##D##

输出样例

B A

那么这一题也是缝合怪了，只需要在中序遍历时加一个判断就行了，那么判断条件是什么呢？

分支结点的特征是左右指针肯定有一个不是NULL，那么答案显而易见了。

判断条件是这个

if (bt->lchild != NULL || bt->rchild != NULL)

全部代码

#include<iostream> using namespace std; struct BiNode { char data; BiNode* lchild, * rchild; }; class BiTree { public: BiTree() { root = Creat(root); } void InOrder() { InOrder(root); } int Empty() { if (root == NULL) return 1; else return 0; } private: BiNode* root; BiNode* Creat(BiNode* bt); void InOrder(BiNode* bt); }; BiNode* BiTree::Creat(BiNode* bt) { char ch; cin >> ch; if (ch == '#') return NULL; else { bt = new BiNode; bt->data = ch; bt->lchild = Creat(bt->lchild); bt->rchild = Creat(bt->rchild); } return bt; } void BiTree::InOrder(BiNode* bt) { //ToDo if (bt == NULL)return; else { InOrder(bt->lchild); //关键是这个判断是不是分支节点 if (bt->lchild != NULL || bt->rchild != NULL){ cout << bt->data << " "; } InOrder(bt->rchild); } } int main() { BiTree btree; btree.InOrder(); return 0; }

5.输出二叉树后序遍历的逆序

题目描述

采用先序法建立一棵二叉树，设计输出二叉树后序遍历的逆序 ，二叉树的数据域类型为字符型，扩展二叉树的叶子结点用‘#’表示，要求可以输出多棵二叉树的后序遍历逆序 ，当二叉树为空时程序结束。

输入描述

循环输入多棵扩展二叉树的先序遍历序列，每棵树占一行，以回车结束，每棵二叉树中结点之间以空格隔开

输出描述

输出各二叉树后序遍历逆序，每次输出后面都换行，当二叉树为空时，输出“NULL”，程序结束

输入样例

A B # # C D # E # F # # G H # I K # # # #

A B D H # # I # # E J # # K # # C F L # # M # # G N # # O # #

#

输出样例

A C G H I K D E F B

A C G O N F M L B E K J D I H

NULL

这题属实有难度啊，后序输出在递归算法中和其他2个没有什么区别。但是在循环算法中后序输出是最难实现的，网上查阅了不少的资料，大家的想法都是要维护一个vision来标记节点的遍历次数，因为后序输出要在该节点被遍历3次后才会输出，这就是后序输出在循环算法的难点。而本题的难点在于需要保存后序输出序列然后以此为基础逆序输出。那么我们势必需要使用一些数据结构来保存后序输出序列。

当然在查阅二叉树后序遍历的非递归实现中有一个双栈算法让我眼前一亮，这个算法并不需要维护vision并且简单易懂。算法如下

void postOrderTraversalIterativeTwoStacks(BinaryTree *root) { if (!root) return; stack<BinaryTree*> s; stack<BinaryTree*> output; s.push(root); while (!s.empty()) { BinaryTree *curr= s.top(); output.push(curr); s.pop(); if (curr->left) s.push(curr->left); if (curr->right) s.push(curr->right); } while (!output.empty()) { cout << output.top()->data << " "; output.pop(); } }

C++ stack(STL stack)用法详解

堆栈操作

和其他序列容器相比，stack 是一类存储机制简单、所提供操作较少的容器。下面是 stack 容器可以提供的一套完整操作：

top()：返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。push(const T& obj)：可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。push(T&& obj)：以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。pop()：弹出栈顶元素。size()：返回栈中元素的个数。empty()：在栈中没有元素的情况下返回 true。emplace()：用传入的参数调用构造函数，在栈顶生成对象。swap(stack & other_stack)：将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。对于 stack 对象有一个特例化的全局函数 swap() 可以使用。

最后可以看到output栈里的顺序就是逆序的输出了，非常的神奇。那么接下来就需要的是逆序输出这个output栈了，但是stack并不能满足这个需求。同时通过观察算法发现output栈在输出之前只有一行涉及到，就是将curr入栈。

output.push(curr);

那么我们其实可以改变output的数据结构为queue。

C++ queue(STL queue)用法详解

queue 操作

queue 和 stack 有一些成员函数相似，但在一些情况下，工作方式有些不同：

front()：返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。back()：返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。push(const T& obj)：在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。push(T&& obj)：以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。pop()：删除 queue 中的第一个元素。size()：返回 queue 中元素的个数。empty()：如果 queue 中没有元素的话，返回 true。emplace()：用传给 emplace() 的参数调用 T 的构造函数，在 queue 的尾部生成对象。swap(queue &other_q)：将当前 queue 中的元素和参数 queue 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。

根据题意更改的算法如下

void BiTree::RePreOrder(BiNode* bt) { if (!root) return; stack<BiNode*> s; queue<BiNode*> output; s.push(root); while (!s.empty()) { BiNode* curr = s.top(); output.push(curr); s.pop(); if (curr->lchild) s.push(curr->lchild); if (curr->rchild) s.push(curr->rchild); } while (!output.empty()) { cout << output.front()->data << " "; output.pop(); } cout << endl; }

全部代码

#include<iostream> #include<string> #include<string.h> #include<stack> #include<queue> using namespace std; class BiNode { public: char data; BiNode* lchild, * rchild; }; class BiTree { public: BiTree() { root = Creat(root); } void RePreOrder() { RePreOrder(root); } int Empty() { return root ? 1 : 0; } private: BiNode* root; BiNode* Creat(BiNode* bt); void RePreOrder(BiNode* bt); }; BiNode* BiTree::Creat(BiNode* bt) { char ch; cin >> ch; if (ch == '#') bt = NULL; else { bt = new BiNode; bt->data = ch; bt->lchild = Creat(bt->lchild); bt->rchild = Creat(bt->rchild); } return bt; } void BiTree::RePreOrder(BiNode* bt) { //ToDo if (!root) return; stack<BiNode*> s; queue<BiNode*> output; s.push(root); while (!s.empty()) { BiNode* curr = s.top(); output.push(curr); s.pop(); if (curr->lchild) s.push(curr->lchild); if (curr->rchild) s.push(curr->rchild); } while (!output.empty()) { cout << output.front()->data << " "; output.pop(); } cout << endl; } int main() { while (1) { BiTree A; if (!A.Empty()) { cout << "NULL" << endl; break; } else { A.RePreOrder(); } } return 0; }

6.求二叉树的深度

题目描述

采用先序法建立一棵二叉树，设计求该二叉树的深度，二叉树的数据域类型为字符型，扩展二叉树的叶子结点用‘#’表示，要求可以求多棵二叉树的深度，当二叉树的深度为0时程序结束。

输入描述

循环输入多棵扩展二叉树的先序遍历序列，每棵树占一行，以回车结束，每棵二叉树中结点之间以空格隔开

输出描述

输出各二叉树的深度，每次输出后面都换行

输入样例

A B # # C D # E # F # # G H # I K # # # #

A B D H # # I # # E J # # K # # C F L # # M # # G N # # O # #

输出样例

6

4

0

思路

同样采用的是递归，核心是Depth函数

int BiTree::Depth(BiNode* bt) { if (bt == NULL) { return 0; } if (bt->lchild == NULL && bt->rchild == NULL) { return 1; } int lDepth = Depth(bt->lchild) + 1; int rDepth = Depth(bt->rchild) + 1; return lDepth > rDepth ? lDepth : rDepth; }

而Depth函数的核心就是

int lDepth = Depth(bt->lchild) + 1; int rDepth = Depth(bt->rchild) + 1;

通过这个递归来计算深度。然后root节点的左右子树的深度进行比较求出深度 。

全部代码

#include<iostream> using namespace std; class BiNode { public: char data; BiNode* lchild, * rchild; }; class BiTree { public: BiTree() { root = Creat(root); } int Depth() { return Depth(root); } private: BiNode* root; BiNode* Creat(BiNode* root); int Depth(BiNode* root); }; BiNode* BiTree::Creat(BiNode* bt) { char ch; cin >> ch; if (ch == '#') bt = NULL; else { bt = new BiNode; bt->data = ch; bt->lchild = Creat(bt->lchild); bt->rchild = Creat(bt->rchild); } return bt; } int BiTree::Depth(BiNode* bt) { if (bt == NULL) { return 0; } if (bt->lchild == NULL && bt->rchild == NULL) { return 1; } int lDepth = Depth(bt->lchild) + 1; int rDepth = Depth(bt->rchild) + 1; return lDepth > rDepth ? lDepth : rDepth; } int main() { while (1) { BiTree A; if (A.Depth() == 0) { cout << 0 << endl; break; } else { cout << A.Depth() << endl; } } return 0; }

7.中序遍历输出二叉树度为1的结点

二叉树的结点数据域是字符型，空用‘#’表示，按前序遍历建立二叉树，按中序输出二叉树中度为1的结点。

输入样例1:

A B H # # # D # I E # # #

输出样例1:

B D I

输入样例2:

A # B # #

输出样例2:

A

输入样例3:

A B C D # # # # #

输出样例3:

C B A

有没有觉得这题跟第4题很像呢？因为叶子节点的度一定是0，所以求的是分支节点，这题又是一个缝合怪 ，我们只需要在第4题的基础上再判断一下该结点是否度为1？

我们来看看第4题的判断条件和本题该怎么设计判断条件呢？

if (bt->lchild != NULL || bt->rchild != NULL)

可以看到这个判断条件得到的节点度为1和2，我们只要度为1的节点就行了

if ((!bt->lchild && bt->rchild) || (bt->lchild && !bt->rchild))

这样我们就只会拿到度为1的分支节点了。

全部代码

#include<iostream> using namespace std; struct BiNode { char data; BiNode* lchild, * rchild; }; class BiTree { public: BiTree() { root = Creat(root); } void InOrder() { InOrder(root); } int Empty() { if (root == NULL) return 1; else return 0; } private: BiNode* root; BiNode* Creat(BiNode* bt); void InOrder(BiNode* bt); }; BiNode* BiTree::Creat(BiNode* bt) { char ch; cin >> ch; if (ch == '#') return NULL; else { bt = new BiNode; bt->data = ch; bt->lchild = Creat(bt->lchild); bt->rchild = Creat(bt->rchild); } return bt; } void BiTree::InOrder(BiNode* bt) { // TODO 按中序输出二叉树中度为1的结点 if (bt == NULL)return; else { InOrder(bt->lchild); //关键在这个判断 if ((!bt->lchild && bt->rchild) || (bt->lchild && !bt->rchild)) { cout << bt->data << " "; } InOrder(bt->rchild); } } int main() { BiTree btree; if (btree.Empty()) return 0; btree.InOrder(); cout << endl; return 0; }

8.前序输出二叉树节点值与层次值

设二叉树采用二叉链表存放，该结点结构为[lchild,data,level,rchild], 将二叉树中每个结点所在的层次值置入相应的level域，并按前序序列顺序输出每个结点的值和level值。

输入样例1:

A B H # # # D # I E # # #

输出样例1:

A 1 B 2 H 3 D 2 I 3 E 4

输入样例2:

A B # # C # #

输出样例2:

A 1 B 2 C 2

区别在哪呢？可以看到本题的节点的结构只不过是多了一个level域而已，而level域就是该结点在树中的层次。

由于题目一开始给的代码是在递归遍历时才给节点赋值level域，我觉得有点奇怪，所以把赋值level域的操作放到Creat函数里了

BiNode* BiTree::Creat(BiNode* bt, int l) { char ch; cin >> ch; if (ch == '#') return NULL; else { bt = new BiNode; bt->data = ch; bt->level = l; bt->lchild = Creat(bt->lchild, l + 1); bt->rchild = Creat(bt->rchild, l + 1); } return bt; }

在这2行看起来是不是跟第6题的Depth函数的地方有点像呢？

//Creat bt->lchild = Creat(bt->lchild, l + 1); bt->rchild = Creat(bt->rchild, l + 1); //Depth int lDepth = Depth(bt->lchild) + 1; int rDepth = Depth(bt->rchild) + 1;

求深度和求层次从本质上来说其实是一件事，深度要求出最大的level ，层次是求出每个节点的level 。而不计算出所有所有的level ，你又如何获得深度呢？2个函数稍微的区别在于Depth是自下向上计算的，最底层是0，然后一层一层往上+1，Create是自上向下，一层一层+1

全部代码

#include<iostream> using namespace std; struct BiNode { char data; int level; BiNode* lchild, * rchild; }; class BiTree { public: BiTree() { root = Creat(root,1); } void PreOrder() { preOrder(root); } int Empty() { if (root == NULL) return 1; else return 0; } void Level() { level(root); }; private: BiNode* root; BiNode* Creat(BiNode* bt,int l); void preOrder(BiNode* bt); void level(BiNode* bt); }; BiNode* BiTree::Creat(BiNode* bt, int l) { char ch; cin >> ch; if (ch == '#') return NULL; else { bt = new BiNode; bt->data = ch; bt->level = l; bt->lchild = Creat(bt->lchild, l + 1); bt->rchild = Creat(bt->rchild, l + 1); } return bt; } void BiTree::level(BiNode* bt) { if (bt != NULL) { preOrder(bt); } } void BiTree::preOrder(BiNode* bt) { if (bt != NULL) { cout << bt->data << " " << bt->level << " "; preOrder(bt->lchild); preOrder(bt->rchild); } } int main() { BiTree btree; btree.Level(); cout << endl; return 0; }

9.二叉树交换左右子树

二叉树的结点数据域是字符型，空用‘#’表示，按前序遍历建立二叉树，交换二叉树中所有结点的左右子树 ，再前序遍历输出。

输入样例1:

A B # # C # #

输出样例1:

A C B

输入样例2:

A B H # # # D C # # I E # # #

输出样例2:

A D I E C B H

这一题的思路其实不难，然而我一开始想的居然是自下向上的交换左右子树 ，短暂的思考之后醒悟自上向下不是就顺便交换左右子树了吗？我果然太蔡了。这里使用的是循环算法 ，那么就不得不使用stack或者queue来完成。

关键在于

while (!s.empty()){ BiNode* curr = s.top(); s.pop(); BiNode* pTmp = curr->lchild; curr->lchild = curr->rchild; curr->rchild = pTmp; if (curr->rchild) s.push(curr->rchild); if (curr->lchild) s.push(curr->lchild); }

后面的2个if可以调换顺序，区别只是在于先从左子树交换还是先从右子树交换而已。

全部代码

#include<iostream> #include<stack> using namespace std; struct BiNode { char data; BiNode* lchild, * rchild; }; class BiTree { public: BiTree() { root = Creat(root); } void Change() { change(root); } void Print() { print(root); } int Empty() { if (root == NULL) return 1; else return 0; } private: BiNode* root; BiNode* Creat(BiNode* bt); void change(BiNode* bt); void print(BiNode* bt); }; BiNode* BiTree::Creat(BiNode* bt) { char ch; cin >> ch; if (ch == '#') return NULL; else { bt = new BiNode; bt->data = ch; bt->lchild = Creat(bt->lchild); bt->rchild = Creat(bt->rchild); } return bt; } void BiTree::change(BiNode* bt) { if (bt != NULL) { //TODO 交换左右子树 并将子树继续交换 BiNode* p = root; stack<BiNode*> s; if (root) s.push(root); while (!s.empty()) { BiNode* curr = s.top(); s.pop(); BiNode* pTmp = curr->lchild; curr->lchild = curr->rchild; curr->rchild = pTmp; if (curr->rchild) s.push(curr->rchild); if (curr->lchild) s.push(curr->lchild); } } } void BiTree::print(BiNode* bt) { cout << bt->data << " "; if (bt->lchild != NULL) print(bt->lchild); if (bt->rchild != NULL) print(bt->rchild); } int main() { BiTree btree; if (btree.Empty()) return 0; btree.Change(); btree.Print(); return 0; }