두 갈래 나무의 기본 조작 (귀속과 비귀속)

4409 단어 나무.

반복:

#include
#include
#include 
using namespace std;
#define MAX 20
int g_num;
typedef struct BTNode{       /* */
	char data ;               /* */
	struct BTNode *lchild;
	struct BTNode *rchild ;  /* */
}BTNode,*BiTree;

void createBiTree(BiTree *t){ /*  */
	char s;
	BiTree q;
	s=getchar();
	if(s=='#'){*t=NULL; return;}
	q=(BiTree)malloc(sizeof(struct BTNode));
	if(q==NULL){printf("Memory alloc failure!"); exit(0);}
	q->data=s;
	*t=q;
	createBiTree(&q->lchild); /* */
	createBiTree(&q->rchild); /* */
}

void PreOrder(BiTree p){  /*  */
    if ( p!= NULL ) {
       	printf("%c", p->data);
       	PreOrder( p->lchild ) ;
       	PreOrder( p->rchild) ;
    }
}
void InOrder(BiTree p){  /*  */
    if( p!= NULL ) {
 	 InOrder( p->lchild ) ;
   	 printf("%c", p->data);
   	 InOrder( p->rchild) ;
    }
}
void PostOrder(BiTree p){  /*  */
   if ( p!= NULL ) {
    	PostOrder( p->lchild ) ;
       	PostOrder( p->rchild) ;
       	printf("%c", p->data);
    }
}

void Preorder_n(BiTree p){ /* */
    BiTree stack[MAX],q;
    int top=0,i;
    for(i=0;idata);
        if(q->rchild!=NULL) stack[top++]=q->rchild;
        if(q->lchild!=NULL) q=q->lchild;
        else
            if(top>0) q=stack[--top];
            else q=NULL;
    }
}

void release(BiTree t){ /* */
  	if(t!=NULL){
    	release(t->lchild);
    	release(t->rchild);
    	free(t);
  	}
}
//deepth
int Depth(BiTree p)
{
    int m,n;
    if(p==NULL)
    {
        return 0;
    }
    else
    {
         m = Depth(p->lchild);
         n = Depth(p->rchild);
        return (m>n) ? m+1 : n+1;
     }
}
//sum of node
int Nodecount(BiTree p)
{
    if(p==NULL)
    {
        return 0;
    }
    else
        return Nodecount(p->lchild) + Nodecount(p->rchild) + 1;
}
//leaf
void countleaf(BiTree p)
{
    if(p){
        if(p->lchild==NULL&&p->rchild==NULL)
        {
            g_num++;
        }
        else{
            countleaf(p->lchild);
            countleaf(p->rchild);
        }
    }
}
BTNode* copyBiTree(BiTree T)
{
    BiTree NLT = NULL;
    BiTree NRT = NULL;
    BiTree newNode = new BTNode;
    if(T->lchild)
    {
        NLT = copyBiTree(T->lchild);
    }
    else
    {
        NLT = NULL;
    }
    if(T->rchild)
    {
        NRT = copyBiTree(T->rchild);
    }
    else
    {
        NRT = NULL;
    }
    if(newNode == NULL)
    {
        return 0;
    }
    newNode->lchild = NLT;
    newNode->rchild = NRT;
    newNode->data = T->data;
    return newNode;

}
int main(){
    BiTree t=NULL;
    printf("
please input data:(exit for #)"); createBiTree(&t); BiTree newT = NULL; newT = copyBiTree(t); g_num = 0; cout<

비반복:

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct BiTreeNode
{
    struct BiTreeNode * lchild;
    struct BiTreeNode * rchild;
    char data;
}BiTreeNode,*BiTree;

void createBiTree(BiTree *t){ /*  */
	char s;
	BiTree q;
	s=getchar();
	if(s=='#'){*t=NULL; return;}
	q=(BiTree)malloc(sizeof(struct BiTreeNode));
	if(q==NULL){printf("Memory alloc failure!"); exit(0);}
	q->data=s;
	*t=q;
	createBiTree(&q->lchild); /* */
	createBiTree(&q->rchild); /* */
}

BiTreeNode *GoFarLeft(BiTreeNode *T,stack &s)
{
    if(T==NULL)
    {
        return NULL;
    }
    while(T->lchild)
    {
        s.push(T);
        T = T->lchild;
    }
    return T;
}

void InOrder(BiTree T)
{
    stack s;
    //step 1: , 
    BiTree t = GoFarLeft(T,s);
    while(t)
    {
        cout<data<rchild!=NULL)
        {
            t = GoFarLeft(t->rchild,s);
        }
        //visit the stack top element
        else if(!s.empty())
        {
            t = s.top();
            s.pop();
        }
        //if rchild is null&&stack is empty
        else
        {
            t = NULL;
        }
    }
}

int main()
{
    BiTree T;
    cout<

주: 비귀속은 c++ 창고 용기에 사용되며, 배우지 못하면 창고 프로그램을 직접 작성할 수도 있습니다.

좋은 웹페이지 즐겨찾기