// 二叉樹中最大結點.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include "iostream.h"
#include <malloc.h>
#define MaxSize 100
#define MaxWidth 40
typedef char ElemType;
typedef struct tnode
{
	ElemType data;
	struct tnode *lchild,*rchild;
} BTNode;
void CreateBTree(BTNode * &bt,char *str)	/*由str創建二叉鏈bt*/
{
	BTNode *St[MaxSize],*p=NULL;
	int top=-1,k,j=0;  
	char ch;
	bt=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 (bt==NULL)                   /**p為二叉樹的根結點*/
					bt=p;
				else  							/*已建立二叉樹根結點*/
				{	switch(k) 
					{
					case 1:St[top]->lchild=p;break;
					case 2:St[top]->rchild=p;break;
					}
				}
		}
		j++;
		ch=str[j];
	}
}
void DispBTree(BTNode *bt)	/*以括號表示法輸出二叉樹*/
{
	if (bt!=NULL)
	{	
		cout<<bt->data;
		if (bt->lchild!=NULL || bt->rchild!=NULL)
		{	
			cout<<"(";
			DispBTree(bt->lchild);		/*遞歸處理左子樹*/
			if (bt->rchild!=NULL) 
			cout<<",";
			DispBTree(bt->rchild);		/*遞歸處理右子樹*/
		cout<<")";
		}
	}
}
void MaxNode(BTNode* bt,char& max)
{
   //char &aa=max;
	if(bt!=NULL)
	{
		if(bt->data>max)
			max=bt->data;
		MaxNode(bt->lchild,max);
		MaxNode(bt->rchild,max);
	}
}


int main(int argc, char* argv[])
{   
	BTNode *bt;
	char Max=-32767;
    
CreateBTree(bt,"1(2(4,3(6,3)),29)");
MaxNode(bt,Max);
cout<<"二叉樹bt:";DispBTree(bt);cout<<endl;	
cout<<"最大結點值為:"<<Max;
	return 0;
}