二叉树的构造及求解二叉树高度

二叉树的构造及求解二叉树高度 二叉树的构造及求解二叉树高度

// 
题目描述
1、参考题目解释构造一棵二叉树；
2、求解二叉树的高度

输入
A(B(D,E),C(,F))
输出
二叉树高度为: 3

样例输入 Copy
A(B(E,C(D(F(,G),,),)
样例输出 Copy
二叉树高度为: 6

C++代码：

//
#include 
#include 
#define MaxSize 100
using namespace std;

typedef char ElemType;
typedef struct node{
    ElemType data;
    struct node *lchild;
    struct node *rchild;
}BTNode;

//创建二叉树
void CreateBTree(BTNode *&b, char *str){
    BTNode *St[MaxSize], *p;
    int top = -1, k, j=0;
    char ch;
    b = NULL;
    ch = str[j];
    while(ch != ''){
        switch(ch){
        case '(' :
            top++;
            St[top] = p;
            k = 1;
            break;
        case ')':
            top--;
            break;
        case ',':
            k = 2;
            break;
        default:
            p = (BTNode *)malloc(sizeof(BTNode));
            p->data = ch;
            p->lchild = p->rchild = NULL;

            if(b == NULL){
                b = p;
            }
            else{
                switch(k){
                    case 1:St[top]->lchild = p;
                    break;
                    case 2:St[top]->rchild = p;
                    break;
                }
            }
        }
        j++;
        ch = str[j];
    }
}

//求二叉树的高度
int BTHeight(BTNode *b){
    int lchild, rchild;
    if(b == NULL){
        return(0);
    }
    else{
        lchild = BTHeight(b->lchild);
        rchild = BTHeight(b->rchild);
        return (lchild > rchild)? (lchild + 1):(rchild + 1); 
    }
}

int main(){
    BTNode *b;
    char *p;
    p = (char *)malloc(20*sizeof(char));
    cin>>p;
    CreateBTree(b, p);
    cout<<"二叉树高度为: "<
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/4994054.html