题目描述

1、参考题目解释构造一棵二叉树；
2、求解二叉树的高度
3、有余力同学尝试打印这棵二叉树（以树的形态，非必须）

输入

A(B(E,C(D(F(,G),),)

输出

二叉树高度为: 6

代码实现

#include <iostream>
//#include <malloc.h>
#include <stdlib.h>
#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 != '\0') //str未扫描时完循环{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置位二叉树的根节点{b = p;}else                //已建立二叉树的根节点{switch(k){case 1:St[top]->lchild = p;break;case 2:St[top]->rchild = p;break;}}}j++;ch = str[j];}}//销毁二叉树
void DestroyBTree(BTNode *&b)
{if(b != NULL){DestroyBTree(b->lchild);DestroyBTree(b->rchild);free(b);}}//查找值为x的结点
BTNode *FindNode(BTNode *b, ElemType x)
{BTNode *p;if(b == NULL){return NULL;}else if(b->data == x){return b;}else{p = FindNode(b->lchild, x);if(p != NULL)return p;elsereturn FindNode(b->rchild, x);}
}//返回p结点的左孩子结点指针
BTNode *LchildNode(BTNode *p)
{return p->lchild;
}//返回p结点的右孩子结点指针
BTNode *RchildNode(BTNode *p)
{return p->rchild;
}//求二叉树的高度
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);}
}//以括号表示法输出二叉树
void DispBTree(BTNode *b)
{if(b != NULL){cout<<b->data;if(b->lchild != NULL || b->rchild != NULL){cout<<"(";          //有孩子节点时才输出（DispBTree(b->lchild);   //递归处理左子树if(b->rchild != NULL){cout<<",";             //有右孩子结点时才输出，}DispBTree(b->rchild);    //递归处理右子树cout<<")";                //有孩子结点时才输出}}
}int main()
{BTNode *b, *p, *lp, *rp;//从控制台输入二叉树char *str;str = (char *)malloc(20*sizeof(char));cin>>str;CreateBTree(b, str);cout<<"输出二叉树";DispBTree(b);cout<<endl;cout<<"二叉树高度为: "<<BTHeight(b);free(p);DestroyBTree(b);return 0;
}

#include <iostream>
//#include <malloc.h>
//#include <stdlib.h>
#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 != '\0') //str未扫描时完循环{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置位二叉树的根节点{b = p;}else                //已建立二叉树的根节点{switch(k){case 1:St[top]->lchild = p;break;case 2:St[top]->rchild = p;break;}}}j++;ch = str[j];}}//销毁二叉树
void DestroyBTree(BTNode *&b)
{if(b != NULL){DestroyBTree(b->lchild);DestroyBTree(b->rchild);free(b);}}BTNode *FindNode(BTNode *b, ElemType x)
{}//求二叉树的高度
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);}
}//以括号表示法输出二叉树
void DispBTree(BTNode *b)
{if(b != NULL){cout<<b->data;if(b->lchild != NULL || b->rchild != NULL){cout<<"(";          //有孩子节点时才输出（DispBTree(b->lchild);   //递归处理左子树if(b->rchild != NULL){cout<<",";             //有右孩子结点时才输出，}DispBTree(b->rchild);    //递归处理右子树cout<<")";                //有孩子结点时才输出}}
}int main()
{BTNode *b;//从控制台输入二叉树char *p;p = (char *)malloc(20*sizeof(char));cin>>p;CreateBTree(b, p);cout<<"输出二叉树";DispBTree(b);cout<<endl;cout<<"二叉树高度为: "<<BTHeight(b);free(p);DestroyBTree(b);return 0;
}

运行结果