DS树+图综合练习--二叉树高度
程序员文章站
2022-05-21 16:14:37
...
题目描述 给出一棵二叉树,求它的高度。二叉树的创建采用前面实验的方法。
注意,二叉树的层数是从1开始
输入
第一行输入一个整数t,表示有t个二叉树
第二行起输入每个二叉树的先序遍历结果,空树用字符‘0’表示,连续输入t行
输出 每行输出一个二叉树的高度
样例输入
1
AB0C00D00
样例输出
3
思路
#include<iostream>
#include<string>
#include<queue>
using namespace std;
class BiTreeNode{
public:
char data;
BiTreeNode *LeftChild;
BiTreeNode *RightChild;
BiTreeNode():LeftChild(NULL), RightChild(NULL){
}
~BiTreeNode(){
}
};
class BiTree{
private:
BiTreeNode *Root;
int pos;
string strTree;
BiTreeNode* CreateBiTree(){
BiTreeNode *T;
char ch;
ch= strTree[pos++];
if(ch== '0')
T= NULL;
else{
T= new BiTreeNode();
T->data= ch;
T->LeftChild= CreateBiTree();
T->RightChild= CreateBiTree();
}
return T;
}
void getLeaf(BiTreeNode* t, int deep){//传入父节点和父节点的高度
if(t){
deep++;
if(!t->LeftChild&&!t->RightChild){
//cout<<t->data<<' ';
if(maxx< deep)
maxx= deep;
}
getLeaf(t->LeftChild, deep);
getLeaf(t->RightChild, deep);
}
}
public:
int leaf;
queue<char> qu;
int maxx;
BiTree(){
}
~BiTree(){
}
void CreateTree(string TreeArray){
pos= 0;
leaf= 0;
maxx= 0;
strTree.assign(TreeArray);
Root= CreateBiTree();
}
void getLeaf(){
getLeaf(Root, 0);
}
};
int main(){
int t;
cin>>t;
while(t--){
string str;
BiTree tree;
cin>>str;
tree.CreateTree(str);
tree.getLeaf();
cout<<tree.maxx<<endl;;
}
return 0;
}
上一篇: 探讨python中的copy()方法
下一篇: 欧拉图总结