概述
main
#include"BinTree.h"
//ABC##DE##F##G#H##
void main()
{
char *VLR = "ABCDEFGH";
char *LVR = "CBEDFAGH";
char *LRV = "CEFDBHGA";
int n = strlen(VLR);
BinTree mytree;
InitBinTree(&mytree,'#');
CreateBinTree_5(&mytree,VLR,LVR,n);
BinTree youtree;
InitBinTree(&youtree,'#');
CreateBinTree_6(&youtree,LVR,LRV,n);
}
/*
void main()
{
char *str = "ABC##DE##F##G#H##";
BinTree mytree;
InitBinTree(&mytree,'#');
CreateBinTree_4(&mytree,str);
PreOrder_1(&mytree);
printf("n");
InOrder_1(&mytree);
printf("n");
}
/*
void main()
{
char *str = "ABC##DE##F##G#H##";
//char *str = "ABC##D##G#H##";
BinTree mytree;
InitBinTree(&mytree,'#');
CreateBinTree_4(&mytree,str);
PreOrder(&mytree);
printf("n");
InOrder(&mytree);
printf("n");
PostOrder(&mytree);
printf("n");
LevelOrder(&mytree);
printf("n");
printf("Size = %dn",Size(&mytree));
printf("Height = %dn",Height(&mytree));
BinTreeNode *p = Search(&mytree,'E');
BinTreeNode *parent = Parent(&mytree,p);
BinTree youtree;
InitBinTree(&youtree,'#');
Copy(&youtree,&mytree);
BinTreeClear(&youtree);
}
*/
栈头文件
#ifndef __SEQSTACK_H__
#define __SEQSTACK_H__
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
struct BinTreeNode;
#define ET BinTreeNode*
#define STACK_INIT_SIZE
8
#define STACK_INC_SIZE
3
typedef struct SeqStack
{
ET *base;
int
capacity;
int
top;
}SeqStack;
bool Inc(SeqStack *s);
void InitStack(SeqStack *s);
bool IsFull(SeqStack *s);
bool IsEmpty(SeqStack *s);
void Push(SeqStack *s, ET x);
void Pop(SeqStack *s);
bool GetTop(SeqStack *s, ET *v);
void Show(SeqStack *s);
int Length(SeqStack *s);
void Clear(SeqStack *s);
void Destroy(SeqStack *s);
/
void InitStack(SeqStack *s)
{
s->base = (ET *)malloc(sizeof(ET)*STACK_INIT_SIZE);
assert(s->base != NULL);
s->capacity = STACK_INIT_SIZE;
s->top = 0;
}
bool Inc(SeqStack *s)
{
ET *newbase = (ET *)realloc(s->base,sizeof(ET)*(s->capacity+STACK_INC_SIZE));
if(newbase == NULL)
{
printf("�ڴ治��,������ռ�.n");
return false;
}
s->base = newbase;
s->capacity += STACK_INC_SIZE;
return true;
}
bool IsFull(SeqStack *s)
{
return s->top >= s->capacity;
}
bool IsEmpty(SeqStack *s)
{
return s->top == 0;
}
void Push(SeqStack *s, ET x)
{
if(IsFull(s) && !Inc(s))
{
printf("ջ�ռ�����,%d ������ջ.n",x);
return;
}
s->base[s->top++] = x;
//s->top++;
}
void Pop(SeqStack *s)
{
if(IsEmpty(s))
{
printf("ջ�ռ��ѿ�,���ܳ�ջ.n");
return;
}
s->top--;
}
bool GetTop(SeqStack *s, ET *v)
{
if(IsEmpty(s))
{
printf("ջ�ռ��ѿ�,����ȡջ��Ԫ��.n");
return false;
}
*v = s->base[s->top-1];
return true;
}
void Show(SeqStack *s)
{
for(int i=s->top-1; i>=0; --i)
{
printf("%dn",s->base[i]);
}
printf("n");
}
int Length(SeqStack *s)
{
return s->top;
}
void Clear(SeqStack *s)
{
s->top = 0;
}
void Destroy(SeqStack *s)
{
free(s->base);
s->base = NULL;
s->capacity = s->top = 0;
}
#endif //__SEQSTACK_H__
队列头文件
#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
struct BinTreeNode;
#define EType BinTreeNode*
typedef struct QueueNode
{
EType data;
struct QueueNode *next;
}QueueNode;
typedef struct LinkQueue
{
QueueNode *front;
QueueNode *tail;
}LinkQueue;
void InitQueue(LinkQueue *Q);
bool QueueIsEmpty(LinkQueue *Q);
void EnQueue(LinkQueue *Q, EType x);
void ShowQueue(LinkQueue *Q);
void DeQueue(LinkQueue *Q);
void GetHead(LinkQueue *Q, EType *v);
int Length(LinkQueue *Q);
void ClearQueue(LinkQueue *Q);
void DestroyQueue(LinkQueue *Q);
void InitQueue(LinkQueue *Q)
{
QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
assert(s != NULL);
Q->front = Q->tail = s;
Q->tail->next = NULL;
}
bool QueueIsEmpty(LinkQueue *Q)
{
return Q->front == Q->tail;
}
void EnQueue(LinkQueue *Q, EType x)
{
QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
assert(s != NULL);
s->data = x;
s->next = NULL;
Q->tail->next = s;
Q->tail = s;
}
void ShowQueue(LinkQueue *Q)
{
QueueNode *p = Q->front->next;
printf("Front:>");
while(p != NULL)
{
printf("%d ",p->data);
p = p->next;
}
printf("<:Tail.n");
}
void DeQueue(LinkQueue *Q)
{
if(Q->front == Q->tail)
return;
QueueNode *p = Q->front->next;
Q->front->next = p->next;
free(p);
if(p == Q->tail)
Q->tail = Q->front;
}
void GetHead(LinkQueue *Q, EType *v)
{
if(Q->front == Q->tail)
return;
QueueNode *p = Q->front->next;
*v = p->data;
}
int Length(LinkQueue *Q)
{
int len = 0;
QueueNode *p = Q->front->next;
while(p != NULL)
{
len++;
p = p->next;
}
return len;
}
void ClearQueue(LinkQueue *Q)
{
if(Q->front == Q->tail)
return;
QueueNode *p = Q->front->next;
while(p != NULL)
{
Q->front->next = p->next;
free(p);
p = Q->front->next;
}
Q->tail = Q->front;
}
void DestroyQueue(LinkQueue *Q)
{
ClearQueue(Q);
free(Q->front);
Q->front = Q->tail = NULL;
}
#endif //__LINKQUEUE_H__
树头文件
#pragma once
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include<string.h>
#define ElemType char
typedef struct BinTreeNode
{
ElemType data;
struct BinTreeNode *leftChild;
struct BinTreeNode *rightChild;
}BinTreeNode;
typedef struct BinTree
{
BinTreeNode *root;
ElemType
refvalue; //stop flag
}BinTree;
void InitBinTree(BinTree *bt, ElemType ref);
///
//1
void CreateBinTree_1(BinTree *bt);
void CreateBinTree_1(BinTree *bt, BinTreeNode **t);
void CreateBinTree_2(BinTree *bt);
void CreateBinTree_2(BinTree *bt, BinTreeNode *&t);
void CreateBinTree_3(BinTree *bt);
BinTreeNode* CreateBinTree_3_(BinTree *bt);
void CreateBinTree_4(BinTree *bt, char *str);
void CreateBinTree_4(BinTree *bt, BinTreeNode *&t, char *&str);
///
//2
void PreOrder(BinTree *bt);
void PreOrder(BinTreeNode *t);
void InOrder(BinTree *bt);
void InOrder(BinTreeNode *t);
void PostOrder(BinTree *bt);
void PostOrder(BinTreeNode *t);
void LevelOrder(BinTree *bt);
void LevelOrder(BinTreeNode *t);
/
//3
int Size(BinTree *bt);
int Size(BinTreeNode *t);
int Height(BinTree *bt);
int Height(BinTreeNode *t);
BinTreeNode* Search(BinTree *bt, ElemType key);
BinTreeNode* Search(BinTreeNode *t, ElemType key);
BinTreeNode* Parent(BinTree *bt, BinTreeNode *p);
BinTreeNode* Parent(BinTreeNode *t, BinTreeNode *p);
BinTreeNode* LeftChild(BinTreeNode *p);
BinTreeNode* RightChild(BinTreeNode *p);
bool BinTreeEmpty(BinTree *bt);
void Copy(BinTree *bt1, BinTree *bt2);
void Copy(BinTreeNode *&t1, BinTreeNode *t2);
void BinTreeClear(BinTree *bt);
void BinTreeClear(BinTreeNode *&t);
//
//4
void PreOrder_1(BinTree *bt);
void PreOrder_1(BinTreeNode *t);
void InOrder_1(BinTree *bt);
void InOrder_1(BinTreeNode *t);
void PostOrder_1(BinTree *bt);
void PostOrder_1(BinTreeNode *t);
//
//5
void CreateBinTree_5(BinTree *bt, char *VLR, char *LVR, int n);
void CreateBinTree_5(BinTreeNode *&t, char *VLR, char *LVR, int n);
void CreateBinTree_6(BinTree *bt, char *LVR, char *LRV, int n);
void CreateBinTree_6(BinTreeNode *&t, char *LVR, char *LRV, int n);
实现函数
#include"BinTree.h"
#include"Queue.h"
#include"Stack.h"
void InitBinTree(BinTree *bt, ElemType ref)
{
bt->root = NULL;
bt->refvalue = ref;
}
void CreateBinTree_1(BinTree *bt)
{
CreateBinTree_1(bt,&(bt->root));
}
void CreateBinTree_1(BinTree *bt, BinTreeNode **t)
{
ElemType Item;
scanf("%c",&Item);
if(Item == bt->refvalue)
(*t) = NULL;
else
{
(*t) = (BinTreeNode*)malloc(sizeof(BinTreeNode));
assert((*t) != NULL);
(*t)->data = Item;
CreateBinTree_1(bt,&((*t)->leftChild));
CreateBinTree_1(bt,&((*t)->rightChild));
}
}
void CreateBinTree_2(BinTree *bt)
{
CreateBinTree_2(bt,bt->root);
}
void CreateBinTree_2(BinTree *bt, BinTreeNode *&t)
{
ElemType Item;
scanf("%c",&Item);
if(Item == bt->refvalue)
t = NULL;
else
{
t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
assert(t != NULL);
t->data = Item;
CreateBinTree_2(bt,t->leftChild);
CreateBinTree_2(bt,t->rightChild);
}
}
void CreateBinTree_3(BinTree *bt)
{
bt->root = CreateBinTree_3_(bt);
}
BinTreeNode* CreateBinTree_3_(BinTree *bt)
{
ElemType Item;
scanf("%c",&Item);
if(Item == bt->refvalue)
return NULL;
else
{
BinTreeNode *t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
assert(t != NULL);
t->data = Item;
t->leftChild = CreateBinTree_3_(bt);
t->rightChild = CreateBinTree_3_(bt);
return t;
}
}
void CreateBinTree_4(BinTree *bt, char *str)
{
CreateBinTree_4(bt,bt->root,str);
}
void CreateBinTree_4(BinTree *bt, BinTreeNode *&t, char *&str)
{
if(*str == bt->refvalue)
t = NULL;
else
{
t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
assert(t != NULL);
t->data = *str;
CreateBinTree_4(bt,t->leftChild,++str);
CreateBinTree_4(bt,t->rightChild,++str);
}
}
//
//2
void PreOrder(BinTree *bt)
{
PreOrder(bt->root);
}
void PreOrder(BinTreeNode *t)
{
if(t != NULL)
{
printf("%c ",t->data);
PreOrder(t->leftChild);
PreOrder(t->rightChild);
}
}
void InOrder(BinTree *bt)
{
InOrder(bt->root);
}
void InOrder(BinTreeNode *t)
{
if(t != NULL)
{
InOrder(t->leftChild);
printf("%c ",t->data);
InOrder(t->rightChild);
}
}
void PostOrder(BinTree *bt)
{
PostOrder(bt->root);
}
void PostOrder(BinTreeNode *t)
{
if(t != NULL)
{
PostOrder(t->leftChild);
PostOrder(t->rightChild);
printf("%c ",t->data);
}
}
void LevelOrder(BinTree *bt)
{
LevelOrder(bt->root);
}
void LevelOrder(BinTreeNode *t)
{
if(t != NULL)
{
BinTreeNode *v;
LinkQueue Q;
InitQueue(&Q);
EnQueue(&Q,t);
while(!QueueIsEmpty(&Q))
{
GetHead(&Q,&v);
DeQueue(&Q);
printf("%c ",v->data);
if(v->leftChild != NULL)
EnQueue(&Q,v->leftChild);
if(v->rightChild != NULL)
EnQueue(&Q,v->rightChild);
}
}
}
///
//3
int Size(BinTree *bt)
{
return Size(bt->root);
}
int Size(BinTreeNode *t)
{
if(t == NULL)
return 0;
else
return Size(t->leftChild)+Size(t->rightChild)+1;
}
int Height(BinTree *bt)
{
return Height(bt->root);
}
int Height(BinTreeNode *t)
{
if(t == NULL)
return 0;
else
{
int left_height = Height(t->leftChild);
int right_height = Height(t->rightChild);
return (left_height>right_height ? left_height:right_height)+1;
}
}
BinTreeNode* Search(BinTree *bt, ElemType key)
{
return Search(bt->root,key);
}
BinTreeNode* Search(BinTreeNode *t, ElemType key)
{
if(t == NULL)
return NULL;
if(t->data == key)
return t;
BinTreeNode *p = Search(t->leftChild,key);
if(p != NULL)
return p;
return Search(t->rightChild,key);
}
BinTreeNode* Parent(BinTree *bt, BinTreeNode *p)
{
return Parent(bt->root,p);
}
BinTreeNode* Parent(BinTreeNode *t, BinTreeNode *p)
{
if(t==NULL || p==NULL)
return NULL;
if(t->leftChild==p || t->rightChild==p)
return t;
BinTreeNode *q = Parent(t->leftChild,p);
if(q != NULL)
return q;
return Parent(t->rightChild,p);
}
BinTreeNode* LeftChild(BinTreeNode *p)
{
if(p != NULL)
return p->leftChild;
return NULL;
}
BinTreeNode* RightChild(BinTreeNode *p)
{
if(p != NULL)
return p->rightChild;
return NULL;
}
bool BinTreeEmpty(BinTree *bt)
{
return
bt->root==NULL;
}
void Copy(BinTree *bt1, BinTree *bt2)
{
Copy(bt1->root,bt2->root);
}
void Copy(BinTreeNode *&t1, BinTreeNode *t2)
{
if(t2 == NULL)
t1 = NULL;
else
{
t1 = (BinTreeNode*)malloc(sizeof(BinTreeNode));
assert(t1 != NULL);
t1->data = t2->data;
Copy(t1->leftChild,t2->leftChild);
Copy(t1->rightChild,t2->rightChild);
}
}
void BinTreeClear(BinTree *bt)
{
BinTreeClear(bt->root);
}
void BinTreeClear(BinTreeNode *&t)
{
if(t != NULL)
{
BinTreeClear(t->leftChild);
BinTreeClear(t->rightChild);
free(t);
t = NULL;
}
}
//
//4
void PreOrder_1(BinTree *bt)
{
PreOrder_1(bt->root);
}
void PreOrder_1(BinTreeNode *t)
{
if(t != NULL)
{
SeqStack st;
InitStack(&st);
BinTreeNode *p;
Push(&st,t);
while(!IsEmpty(&st))
{
GetTop(&st,&p);
Pop(&st);
printf("%c ",p->data);
if(p->rightChild != NULL)
Push(&st,p->rightChild);
if(p->leftChild != NULL)
Push(&st,p->leftChild);
}
}
}
void InOrder_1(BinTree *bt)
{
InOrder_1(bt->root);
}
void InOrder_1(BinTreeNode *t)
{
if(t != NULL)
{
SeqStack st;
InitStack(&st);
BinTreeNode *p;
Push(&st,t);
while(!IsEmpty(&st))
{
while(t!=NULL && t->leftChild!=NULL)
{
Push(&st,t->leftChild);
t = t->leftChild;
}
GetTop(&st,&p);
Pop(&st);
printf("%c ",p->data);
if(p->rightChild != NULL)
{
t = p->rightChild;
if(t != NULL)
Push(&st,t);
}
}
}
}
//5
void CreateBinTree_5(BinTree *bt, char *VLR, char *LVR, int n)
{
CreateBinTree_5(bt->root,VLR,LVR,n);
}
void CreateBinTree_5(BinTreeNode *&t, char *VLR, char *LVR, int n)
{
if(n == 0)
t = NULL;
else
{
int k = 0;
while(VLR[0] != LVR[k])
k++;
t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
assert(t != NULL);
t->data = LVR[k];
CreateBinTree_5(t->leftChild,VLR+1,LVR,k);
CreateBinTree_5(t->rightChild,VLR+k+1,LVR+k+1,n-k-1);
}
}
void CreateBinTree_6(BinTree *bt, char *LVR, char *LRV, int n)
{
CreateBinTree_6(bt->root,LVR,LRV,n);
}
void CreateBinTree_6(BinTreeNode *&t, char *LVR, char *LRV, int n)
{
if(n == 0)
t = NULL;
else
{
int k = 0;
while(LRV[n-1] != LVR[k])
k++;
t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
assert(t != NULL);
t->data = LVR[k];
CreateBinTree_6(t->rightChild,LVR+k+1,LRV+k,n-k-1);
CreateBinTree_6(t->leftChild,LVR,LRV,k);
}
}
最后
以上就是飘逸太阳为你收集整理的c语言二叉树main的全部内容,希望文章能够帮你解决c语言二叉树main所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复