查找.c

编写程序

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef char DataType;
#include "BiTree.h"
#include "BiTreeTraverse.h"

typedef BiTreeNode SDataType;
#include "LinStack.h"

void PrintData(DataType item)
{   
    printf("%c ",item);
}

BiTreeNode *Search(BiTreeNode *bt,DataType x)
{
    BiTreeNode *p;

    if(bt==NULL) return NULL;
    if(bt->data==x) return bt;

    if(bt->leftChild!=NULL)
    {
        p=Search(bt->leftChild,x);
        if(p!=NULL) return p;
    }

    if(bt->rightChild!=NULL)
    {
        p=Search(bt->rightChild,x);
        if(p!=NULL) return p;
    }
}
//非递归先序遍历
void StackOrder(BiTreeNode *t,LSNode *s,void Visit(DataType item))
{   
    BiTreeNode ttemp;
    int count=0;
    
    StackPush(s,*t);
    count++;
    
    do
    {	
        StackPop(s,&ttemp);
        Visit(ttemp.data);
        count--;
    	
        if(ttemp.rightChild!=NULL)
    	{	
            StackPush(s,*ttemp.rightChild);
            count++;
    	}
        if(ttemp.leftChild!=NULL)
    	{	
            StackPush(s,*ttemp.leftChild);
            count++;
    	}
    } while(count>0);
}

void main(void)
{   
    BiTreeNode *tree,*p,*pp,*ppp;
    LSNode *stack;
    char a;
    
    StackInitiate(&stack);
    BiTreeInitiate(&tree);
    
    printf("本题算法结果\n ");

/*创建课本P165图7-10(b)结构的树*/
    p=InsertLeftNode(tree,'A');
    p=InsertLeftNode(p,'B');
    p=InsertLeftNode(p,'D');
    p=InsertRightNode(p,'G');
    p=InsertRightNode(tree->leftChild,'C');
    pp=p;
    InsertLeftNode(p,'E');
    InsertRightNode(pp,'F');

    PrintBiTree(tree,0);

    printf("非递归先序遍历结果\n ");
    StackOrder(tree->leftChild,stack,PrintData); //创建的树附带头节点
    
    printf("\n先序遍历结果 ");	
    PreOrder(tree->leftChild,PrintData);  //采用递归算法的先序遍历运算对比结果
    
    printf("\n中序遍历结果 ");	
    InOrder(tree->leftChild,PrintData);  //递归中序遍历
    
    printf("\n后序遍历结果 ");	
    PostOrder(tree->leftChild,PrintData);  //递归后序遍历
    
    printf("请输入要查找的元素\n");
    scanf("%c",&a);
    ppp=Search(tree,a);
    if(ppp==NULL) printf("查找不到\n");
    else printf("查找到元素%c\n",a);
    
    BiTreeDestroy(&tree);
    StackDestroy(&stack);
    getch();
}