描述
创建二叉树类。二叉树的存储结构使用链表。提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。
格式
输入格式
第一行为一个数字n (10<=n<=100000)，表示有这棵树有n个节点，编号为1~n。
之后n行每行两个数字，第 i 行的两个数字a、b表示编号为 i 的节点的左孩子节点为 a，右孩子节点为 b，-1表示该位置没有节点。
保证数据有效，根节点为1。
输出格式
第一行，n个数字，表示该树的层次遍历。
第二行，n个数字，第i个数字表示以 i 节点为根的子树的节点数目。
第三行，n个数字，第i个数字表示以 i 节点为根的子树的高度。
样例1
输入
5
2 3
4 5
-1 -1
-1 -1
-1 -1
输出
1 2 3 4 5
5 3 1 1 1
3 2 1 1 1
样例2
输入
5
3 2
-1 -1
4 5
-1 -1
-1 -1
输出
1 3 2 4 5
5 1 3 1 1
3 1 2 1 1
样例3
输入
10
2 -1
4 3
6 -1
5 8
9 7
-1 -1
-1 -1
-1 -1
10 -1
-1 -1
输出
1 2 4 3 5 8 6 9 7 10
10 9 2 6 4 1 1 1 2 1
6 5 2 4 3 1 1 1 2 1
Hint
请仔细读题，注意建树过程。
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
const int N = 1e5 + 10;
template<class T>
struct binaryTreeNode {
T element;
binaryTreeNode<T> *leftChild, *rightChild; //指向右孩子节点的指针
// 3 个构造函数
binaryTreeNode() // 没有参数
{ leftChild = rightChild = NULL; }
binaryTreeNode(const T &theElement) //只有数据参数
{
element = theElement;
leftChild = rightChild = NULL;
}
binaryTreeNode(const T &theElement, // 数据 + 指针参数
binaryTreeNode *theLeftChild,
binaryTreeNode *theRightChild) {
element = theElement;
leftChild = theLeftChild;
rightChild = theRightChild;
}
};
template<class T>
class linkedBinaryTree {
public:
linkedBinaryTree() {
root = NULL;
treeSize = 0;
}// 构造函数
// ~linkedBinaryTree(){erase();}; // 析构函数
bool empty() const { return treeSize == 0; } // 判断是否为空
int size() const { return treeSize; } // 返回节点的数量
void levelOrder(binaryTreeNode<T> *t); // 层次遍历
void preOrder(binaryTreeNode<T> *t); // 前序遍历
void inOrder(binaryTreeNode<T> *t); // 中序遍历
void postOrder(binaryTreeNode<T> *t); // 后序遍历
int height(binaryTreeNode<T> *t);
int number(binaryTreeNode<T> *t) {
int x = 0;
if (t != NULL) {
x = number(t->leftChild) + number(t->rightChild) + 1;
}
return x;
}
private:
binaryTreeNode<T> *root; // 指向根的指针
int treeSize; // 树的节点个数
};
template<class T>
void linkedBinaryTree<T>::inOrder(binaryTreeNode<T> *t) {
if (t == NULL)return;
inOrder(t->leftChild);
cout << t->element << endl;
inOrder(t->rightChild);
}
template<class T>
void linkedBinaryTree<T>::preOrder(binaryTreeNode<T> *t) {
if (t == NULL)return;
cout << t->element << endl;
preOrder(t->leftChild);
preOrder(t->rightChild);
}
template<class T>
void linkedBinaryTree<T>::postOrder(binaryTreeNode<T> *t) {
if (t == NULL)return;
postOrder(t->leftChild);
postOrder(t->rightChild);
cout << t->element << endl;
}
template<class T>
int linkedBinaryTree<T>::height(binaryTreeNode<T> *t) {
if (t == NULL)return 0;
return max(height(t->rightChild), height(t->leftChild)) + 1;
}
template<class T>
void linkedBinaryTree<T>::levelOrder(binaryTreeNode<T> *t) {
queue<binaryTreeNode<T> *> q;
while (t != NULL) {
cout << t->element << " ";
if (t->leftChild != NULL)
q.push(t->leftChild);
if (t->rightChild != NULL)
q.push(t->rightChild);
if (q.empty()) { break; }
t = q.front();
q.pop();
}
cout << endl;
}
binaryTreeNode<int>* b[N];
int main() {
int n;cin>>n;
for (int i = 1; i <= n; i++) { b[i] = new binaryTreeNode<int>(i); }
for (int i = 1; i <= n; i++) {
int x, y = 0;
cin >> x >> y;
if (x != -1)b[i]->leftChild = b[x];
else b[i]->leftChild = NULL;
if (y != -1)b[i]->rightChild = b[y];
else b[i]->rightChild = NULL;
}
linkedBinaryTree<int> a;
a.levelOrder(b[1]);
for (int i = 1; i <= n; i++) {
cout << a.number(b[i]) << " ";
}
cout << endl;
for (int i = 1; i <= n; i++) {
cout << a.height(b[i]) << " ";
}
return 0;
}
描述
接收二叉树前序序列和中序序列(各元素各不相同)，输出该二叉树的后序序列。
格式
输入格式
输入有三行：
第一行为数字n。
第二行有n个数字，表示二叉树的前序遍历。
第三行有n个数字，表示二叉树的中序遍历。
输出格式
输出一行，表示该二叉树的后序遍历序列。
样例
输入
5
1 2 4 5 3
4 2 5 1 3
输出
4 5 2 3 1
```cpp
#include <iostream>
using namespace std;
template<class T>
// 链表二叉树的节点结构
struct binaryTreeNode {
T element;
binaryTreeNode<T> *leftChild; // 左子树
binaryTreeNode<T> *rightChild; // 右子树
binaryTreeNode() { leftChild = rightChild = NULL; }// 初始化
binaryTreeNode(const T &theElement) {
element = theElement;
leftChild = rightChild = NULL;
}
binaryTreeNode(const T &theElement, binaryTreeNode *theLeftChild, binaryTreeNode *theRightChild) {
element = theElement;
leftChild = theLeftChild;
rightChild = theRightChild;
}
};
template<class T>
void postOrder(binaryTreeNode<T>*t){
if(t != NULL){
postOrder(t->leftChild);
postOrder(t->rightChild);
cout<<t->element<<" ";
}
}
binaryTreeNode<int> *f(int pre[], int L1, int R1, int in[], int L2, int R2) {
if (L1 > R1)return NULL;
binaryTreeNode<int> *root = new binaryTreeNode<int>(pre[L1]);
if (L1 == R1) { return root; }
int find = L2;
while (in[find] != pre[L1])find++;
root->leftChild = f(pre, L1 + 1, L1 + find - L2, in, L2, find - 1);
root->rightChild = f(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);
return root;
}
binaryTreeNode<int> *buildNewTree(int a[], int b[],int c) {
return f(a,0,c-1,b,0,c-1);
}
int main() {
int n;
cin>>n;
int pre[n];
int in[n];
for(int i= 0;i<n;i++)
cin>>pre[i];
for(int i=0;i<n;i++)
cin>>in[i];
binaryTreeNode<int> *root = buildNewTree(pre,in,n);
postOrder(root);
return 0;
}