欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}