//树！
#include<bits/stdc++.h>
using namespace std;
typedef struct BinaryTree {//二叉树
BinaryTree* sLeftSubtree;//左子树
BinaryTree* sRightSubtree;//右子树
char cValue; //值
} BTree;
BinaryTree * CreateBinaryTree();//种树~！
void Recursive_PreOrderTraversal(BTree* node);//递归先序遍历
void Recursive_InOrderTraversal(BTree* node);//递归中序遍历
void Recursive_PostOrderTraversal(BTree* node);//递归后序遍历
void NonRecursive_InOrderTraversal(BTree* root);//非递归中序遍历
void NonRecursive_LevelOrderTraversal(BTree* root);//非递归层次遍历
int GetTreeDepth(BTree* root);//树的深度
int main () {
BTree* root;//根节点
vector<char> cValues;//vector成员转换为char
string temp;
cout << "请输入先序遍历的扩展序列：\n";
root = CreateBinaryTree();
cout << "正在按照该序列建立二叉树......\n";
cout << "递归先序遍历结果：\n";
Recursive_PreOrderTraversal(root);//进行递归先序遍历
cout << "\n递归中序遍历结果：\n";
Recursive_InOrderTraversal(root);//进行递归中序遍历
cout << "\n递归后序遍历结果：\n";
Recursive_PostOrderTraversal(root);//进行递归后序遍历
cout << "\n非递归中序遍历结果：\n";
NonRecursive_InOrderTraversal(root);//进行非递归中序遍历
cout << "\n非递归层次遍历结果：\n";
NonRecursive_LevelOrderTraversal(root);//进行非递归层次遍历
cout << "\n二叉树深度为:\n" << GetTreeDepth(root);//输出树的深度
return 0;
}
BTree * CreateBinaryTree() {//建树
BTree* node;//节点
char ch;//存值
scanf("%c", &ch);
if (ch == '#') {
node = nullptr;//空指针
} else {
node = new BTree ;
node->cValue = ch;
node->sLeftSubtree = CreateBinaryTree();//左子树
node->sRightSubtree = CreateBinaryTree();//右子树
}
return node;
}
void Recursive_PreOrderTraversal(BTree* node) {//递归先序遍历
if (node) {
cout << node->cValue;//自身
Recursive_PreOrderTraversal(node->sLeftSubtree);//访问左
Recursive_PreOrderTraversal(node->sRightSubtree);//访问右
}
}
void Recursive_InOrderTraversal(BTree* node) {//递归中序遍历
if (node) {
Recursive_InOrderTraversal(node->sLeftSubtree);//那个神奇的左节点！
cout << node->cValue;//自身值
Recursive_InOrderTraversal(node->sRightSubtree);//右
}
}
void Recursive_PostOrderTraversal(BTree* node) {//递归后序遍历
if (node) {
Recursive_PostOrderTraversal(node->sLeftSubtree);//左
Recursive_PostOrderTraversal(node->sRightSubtree);//右
cout << node->cValue;//输出
}
}
void NonRecursive_InOrderTraversal(BTree* root) {//非递归中序
stack<BTree *> stack;//栈！
BTree *T = root;//根
while (T || !stack.empty()) {
while (T) {
stack.push(T);//压入
T = T->sLeftSubtree;//取其左子树
}
if (!stack.empty()) {//若不空
T = stack.top();
stack.pop();//取出
cout << T->cValue;//输出
T = T->sRightSubtree;//往右子树方向走
}
}
}
void NonRecursive_LevelOrderTraversal(BTree* root) {//非递归层次遍历
queue<BTree *> queue;//排队排队
BTree * T;
queue.push(root);//根入队
bool flag = true;
while (queue.front() != queue.back() || flag) {
flag = false;
T = queue.front();//取队首
queue.pop();//出队
cout << T->cValue;//出队输出值
if (T->sLeftSubtree) {//左子不空
queue.push(T->sLeftSubtree);//左子入队
}
if (T->sRightSubtree) {//右子不空
queue.push(T->sRightSubtree);//右子入队
}
}
cout << queue.front()->cValue;
}
int GetTreeDepth(BTree* root) {
if (!root) {//树空
return 0;
} else {//树不空
return max(GetTreeDepth(root->sLeftSubtree), GetTreeDepth(root->sRightSubtree))+1;//向深处漫溯！
}
}
/*设计样例
请输入先序遍历的扩展序列：
abc###d##
正在按照该序列建立二叉树......
递归先序遍历结果：
abcd
递归中序遍历结果：
cbad
递归后序遍历结果：
cbda
非递归中序遍历结果：
cbad
非递归层次遍历结果：
abdc
二叉树深度为:
3
14：
请输入结点个数n；
5
接下来的 5 行，每行输入格式为结点内容+空格+双亲结点位置，根节点的双亲位置为-1；
a -1
b 0
c 0
d 1
e 2
该树的深度为：
3
*/
