非终端结点.cpp

求非终端结点的算法

//编写完整的程序求二叉树非终端结点的个数


typedef struct Bnode    //用二叉链表装此二叉树
{
  struct Bnode *lchild,*rchild;
  char data[20];
}TBinaryTree,*SBinaryTree;

typedef struct stack  //先序遍历此二叉树所要用的栈
{
  TBinaryTree *p;
}Stack;
typedef struct
{
  Stack *base;
  Stack *top;
}SqStack;

#include <stdio.h>
#include <process.h>
#include <malloc.h>
#include <iostream.h>
#include <string.h>

void Creat(TBinaryTree *);//创建二叉树
int PreOrder(TBinaryTree *);//先序遍历此二叉树求二叉树非终端结点的个数
int stringchange(char *a)//将一个字符串转化为数字     
{

  int i(0); 
  char *p;
  p=a;
  while(*p!='\0')
  {
    i=int(*p)+i*10;
	p++;
  }
  return i;

}

void main()
{
    int count;//用来装二叉树非终端结点的个数
    SBinaryTree BinaryTree;
    BinaryTree=(TBinaryTree *)malloc(sizeof(TBinaryTree));//申请二叉链表的一个结点
	if(!BinaryTree)
	{
	  printf("no memery!");
	  exit(0);
	}
    printf("现在以三元组(F  C  L/R)的形式创建一棵二叉树。\n");
	printf("(其中F表示双亲结点,C表示孩子结点,L/R表示C为F的左孩子或右孩子)，\n");
	printf("当F=NULL时C为根结点，若C=NULL，则结束输入。\n");
	printf("!!!注意输入的三元组形式务必能形成一棵二叉树并且NULL大写才有效。\n");
	printf("例如，有一棵二叉树，其输入序列为(NULL,A,L)，(A,B,L)，(A,C,R)，(B,D,L)，(C,E,L)，(C,F,R)，(D,G,R)，(F,H,L)，(NULL,NULL,L)。\n");
   	Creat(BinaryTree);
	printf("二叉树非终端结点的个数为：");
	count=PreOrder(BinaryTree);
	printf("%d\n",count);
	printf("\n");
}


void Creat(SBinaryTree T)//创建二叉树，无返回值，传递地址
{
    
	SBinaryTree m[112500];
    
	SBinaryTree p;
	char parent[10],child[10],inc[10];
    int i(0);
  
    
	p=T;
	p->lchild=NULL;
	p->rchild=NULL; 

	
    //以三元组的形式输入结点
    scanf("%s%s%s",parent,child,inc);  //输入一个头结点
	while((strcmp(inc,"L")!=0)&&(strcmp(inc,"l")!=0)&&(strcmp(inc,"R")!=0)&&(strcmp(inc,"r")!=0))
	{
	  printf("请重新输入一个结点!确保最后一个为(L、l、R、r)。\n");
      scanf("%s%s%s",parent,child,inc);
	}//如果最后一个字符非法就重新输入
    if(strcmp(child,"NULL")==0) exit(0) ; //如果C=NULL则结束输入
	while(strcmp(parent,"NULL")!=0)    //如果F不为NULL则重新输入
	{
	  printf("请输入一个根结点!\n");
      scanf("%s%s%s",parent,child,inc);
    }
	strcpy(p->data,child);
	m[stringchange(p->data)]=p;//把这个结点的指针放入一个数组中

	while(strcmp(child,"NULL")!=0)
    {
        scanf("%s%s%s",parent,child,inc);  //输入另一个三元组
        while((strcmp(inc,"L")!=0)&&(strcmp(inc,"l")!=0)&&(strcmp(inc,"R")!=0)&&(strcmp(inc,"r")!=0))
		{
	      printf("请重新输入一个结点!确保最后一个为(L、l、R、r)。\n");
          scanf("%s%s%s",parent,child,inc);
		}
        p=(TBinaryTree *)malloc(sizeof(TBinaryTree));//申请二叉链表的一个结点
    	if(!p)
		{
	     printf("no memery!");
	     exit(0);
		}
	    p->lchild=NULL;
    	p->rchild=NULL;
		strcpy(p->data,child);
        m[stringchange(p->data)]=p;
	    if((strcmp(inc,"L")==0)||((strcmp(inc,"l")==0))) m[stringchange(parent)]->lchild=p;
		else if((strcmp(inc,"R")==0)||((strcmp(inc,"r")==0))) m[stringchange(parent)]->rchild=p; 
		else exit(0);
	}
}


int PreOrder(SBinaryTree BT)  //先序遍历二叉树
{  
   TBinaryTree *p;
   SqStack M;
   int count(0);//用来计数
   M.base=(Stack *)malloc(30*sizeof(Stack));
   if (!M.base) {printf("no memery!");exit(0);}
   M.top =M.base;
   if (BT==NULL) return (0);
   p=BT;
   while((p!=NULL)||(M.top!=M.base))
   { 
     while(p!=NULL)    
	 { if((p->rchild!=NULL)||(p->lchild!=NULL)) count++;//如果没有孩子则为非终端结点，count加1.
	   M.top->p=p;     //结点指针进栈
	   M.top++;
	   p=p->lchild;    //找该结点的左孩子 
	 }
	 if(M.top!=M.base)//如果栈不为空
	 { 
	   M.top--;//则弹出一个结点
	   p=M.top->p;
	   p=p->rchild;    //找该结点的右孩子 
	 }
	 
   
   }
  return(count);//返回非终端结点的数目
}