二叉树中最大结点.cpp

二叉树是数据结构的重中之重

// 二叉树中最大结点.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;
}