基于二叉链表的二叉树高度的计算

#include<iostream>
#include<string>
using namespace std;
typedef char TElemType;
#define OK 1
typedef int Status;
typedef struct BiNode
{
    TElemType data;
    struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
int len;
string ch;
void CreateBiTree(BiTree &T)
{
    
    //if(a.length()==b)return;
    char c=ch.at(len++);
    if(c=='0')
    {
        T=NULL;
    } 
    else
    {
        T=new BiNode;
        T->data=c;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
Status PreOrderTraverse(BiTree T){
  if(T==NULL) return OK; 
  else{    
     cout<<T->data; 
     PreOrderTraverse(T->lchild); 
     PreOrderTraverse(T->rchild); 
    }
}
Status InOrderTraverse(BiTree T){
  if(T==NULL) return OK; 
  else{    
     InOrderTraverse(T->lchild); 
     cout<<T->data;
     InOrderTraverse(T->rchild); 
    }
}
Status PostOrderTraverse(BiTree T){
  if(T==NULL) return OK; 
  else{    
     PostOrderTraverse(T->lchild); 
     PostOrderTraverse(T->rchild); 
     cout<<T->data;
    }
}
int LeadCount(BiTree T){
    if(T==NULL)     //如果是空树返回0
        return 0;
    if (T->lchild == NULL && T->rchild == NULL)
        return 1; //如果是叶子结点返回1
    else return LeadCount(T->lchild) + LeadCount(T->rchild);
}
int doubleCount(BiTree T){
    //叶子节点n0=二度节点n2+1
    return LeadCount(T)-1;
}
int NodeCount(BiTree T){
  if(T == NULL ) return 0;                
  else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
} 
int oneCount(BiTree T){
    return NodeCount(T)-doubleCount(T)-LeadCount(T);
}

int deepth(BiTree t){
    int deep;
    int ldeepth,rdeepth;
    if(t==NULL) return 0;
    else{
        ldeepth=deepth(t->lchild);
        rdeepth=deepth(t->rchild);
        deep=ldeepth>=rdeepth?ldeepth+1:rdeepth+1;
    }
    return deep;
}
int main()
{
    int count=0;
    while(cin>>ch&&ch!="0")
    {
        BiTree T;
        len=0;
        CreateBiTree(T);
        cout<<deepth(T)<<endl;

    }

}

基于二叉链表的二叉树高度的计算
发布时间: 2017年9月18日 10:27 最后更新: 2017年9月18日 11:47 时间限制: 1000ms 内存限制: 128M

描述
设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，，编写递归算法计算二叉树的高度。

输入
多组数据。每组数据一行，为二叉树的前序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。

输出
每组数据分别输出一行，为二叉树的高度。

样例输入1
abcd00e00f00ig00h00
abd00e00cf00g00
0
样例输出1
4
3