データ構造学習ノート---ツリー
1.引用
1本の木がどれだけフォークを持っていても、長男とその下の兄弟が一番多い.このような定義によれば,各ノードの構造は二叉に統一される.
チェーン
時計の構造ができた.これにより、ノードの操作が容易になります.
2.ツリーの二叉チェーン(子供-兄弟)ストレージ
1本の木がどれだけフォークを持っていても、長男とその下の兄弟が一番多い.このような定義によれば,各ノードの構造は二叉に統一される.
チェーン
時計の構造ができた.これにより、ノードの操作が容易になります.
2.ツリーの二叉チェーン(子供-兄弟)ストレージ
#include "ds.h"
typedef char TElemType;
TElemType Nil=' '; //
typedef struct CSNode
{
TElemType data;
CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;
#define ClearTree DestroyTree //
typedef CSTree QElemType;
typedef struct QNode{
QElemType data;
struct QNode *next;
}*QueuePtr;
struct LinkQueue{
QueuePtr front, rear;
};
void InitQueue(LinkQueue &Q);
void DestroyQueue(LinkQueue &Q);
void ClearQueue(LinkQueue &Q);
Status QueueEmpty(LinkQueue Q);
void EnQueue(LinkQueue &Q, QElemType e);
Status DeQueue(LinkQueue &Q, QElemType &e);
//
void InitQueue(LinkQueue &Q)
{
Q.front = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front) exit(OVERFLOW);
Q.front->next = NULL;
Q.rear = Q.front;
}
void DestroyQueue(LinkQueue &Q)
{
QueuePtr q, p = Q.front;
while (p)
{
q = p->next;
free(p);
p = q;
}
Q.front = Q.rear = NULL;
}
void ClearQueue(LinkQueue &Q)
{
QueuePtr q, p = Q.front->next;
while (p)
{
q = p->next;
free(p);
p = q;
}
Q.front->next = NULL;
Q.rear = Q.front;
}
Status QueueEmpty(LinkQueue Q)
{
if (Q.front == Q.rear)
return TRUE;
else
return FALSE;
}
void EnQueue(LinkQueue &Q, QElemType e)
{
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if (!p) exit(OVERFLOW);
p->next = NULL;
memcpy(&(p->data), &e, sizeof(QElemType));
Q.rear->next = p;
Q.rear = p;
}
Status DeQueue(LinkQueue &Q, QElemType &e)
{
QueuePtr p = Q.front, q;
if (Q.front == Q.rear)
return FALSE;
q = p->next;
memcpy(&e, &(q->data), sizeof(QElemType));
p->next = q->next;
if (Q.rear == q)
Q.rear = Q.front;
free(q);
return OK;
}
// — T
void PreOrderTraverse(CSTree T, void(*Visit)(TElemType))
{
if (T)
{
Visit(T->data); //
PreOrderTraverse(T->firstchild, Visit); //
PreOrderTraverse(T->nextsibling, Visit); //
}
}
void InitTree(CSTree &T)
{
T = NULL;
}
void DestroyTree(CSTree &T)
{
if (T)
{
if (T->firstchild)
DestroyTree(T->firstchild);
if (T->nextsibling)
DestroyTree(T->nextsibling);
free(T);
T = NULL;
}
}
void CreateTree(CSTree &T)
{
char c[20];
CSTree p, p1;
LinkQueue q;
int i, l;
InitQueue(q);
printf(" ( , ): ");
scanf("%c%*c", &c[0]);
if (c[0] != Nil) //
{
T = (CSTree)malloc(sizeof(CSNode)); //
T->data = c[0];
T->nextsibling = NULL;
EnQueue(q, T); //
while (!QueueEmpty(q)) //
{
DeQueue(q, p); //
printf(" %c : ",p->data);
gets(c);
l = strlen(c);
if (l > 0) //
{
p1 = p->firstchild = (CSTree)malloc(sizeof(CSNode)); //
p1->data = c[0];
for (i = 1; i < l; i++)
{
p1->nextsibling = (CSTree)malloc(sizeof(CSNode)); //
EnQueue(q, p1); //
p1 = p1->nextsibling;
p1->data = c[i];
}
p1->nextsibling = NULL;
EnQueue(q, p1); //
}
else
p->firstchild = NULL; //
}
}
else
T = NULL; //
}
// ： T 。 ： T ， TURE， FALSE
Status TreeEmpty(CSTree T)
{
if(T) // T
return FALSE;
else
return TRUE;
}
// ： T 。 ： T
int TreeDepth(CSTree T)
{
CSTree p;
int depth, max = 0;
if (!T) //
return 0;
if (!T->firstchild) //
return 1;
for (p = T->firstchild; p; p = p->nextsibling)
{ //
depth = TreeDepth(p);
if (depth > max)
max = depth;
}
return max + 1; // = +1
}
// p
TElemType Value(CSTree p)
{
return p->data;
}
// ： T 。 ： T
TElemType Root(CSTree T)
{
if(T)
return Value(T);
else
return Nil;
}
// ( — ) T s 。
CSTree Point(CSTree T,TElemType s)
{
LinkQueue q;
QElemType a;
if(T) //
{
InitQueue(q); //
EnQueue(q,T); //
while(!QueueEmpty(q)) //
{
DeQueue(q,a); // , a
if(a->data==s)
return a;
if(a->firstchild) //
EnQueue(q,a->firstchild); //
if(a->nextsibling) //
EnQueue(q,a->nextsibling); //
}
}
return NULL;
}
// ： T ，cur_e T 。 ： cur_e value
Status Assign(CSTree &T,TElemType cur_e,TElemType value)
{
CSTree p;
if (T) //
{
p = Point(T, cur_e); // p cur_e
if (p) // cur_e
{
p->data = value; //
return OK;
}
}
return ERROR; //
}
// ： T ，cur_e T
// ： cur_e T ， ， ＂ ＂
TElemType Parent(CSTree T,TElemType cur_e)
{
CSTree p,t;
LinkQueue q;
InitQueue(q);
if(T) //
{
if (Value(T) == cur_e) // cur_e
return Nil;
EnQueue(q, T); //
while(!QueueEmpty(q))
{
DeQueue(q,p);
if(p->firstchild) // p
{
if(p->firstchild->data==cur_e) // cur_e
return Value(p); //
t=p; // t
p=p->firstchild; // p
EnQueue(q,p); //
while(p->nextsibling) //
{
p=p->nextsibling; // p
if(Value(p)==cur_e) // cur_e
return Value(t); //
EnQueue(q,p); //
}
}
}
}
return Nil; // cur_e
}
// ： T ，cur_e T
// ： cur_e T ， ， ＂ ＂
TElemType LeftChild(CSTree T,TElemType cur_e)
{
CSTree f;
f = Point(T,cur_e); // f cur_e
if(f && f->firstchild) // cur_e cur_e
return f->firstchild->data;
else
return Nil;
}
// ： T ，cur_e T
// ： cur_e ， ， ＂ ＂
TElemType RightSibling(CSTree T,TElemType cur_e)
{
CSTree f;
f = Point(T,cur_e); // f cur_e
if(f && f->nextsibling) // cur_e cur_e
return f->nextsibling->data;
else
return Nil; //
}
// ： T ，p T ，1≤i≤p +1， c T
// ： c T p i
// p ， p
Status InsertChild(CSTree &T,CSTree p,int i,CSTree c)
{
int j;
if(T) // T
{
if(i==1) // c p
{
c->nextsibling=p->firstchild; // p c (c )
p->firstchild=c;
}
else //
{
p=p->firstchild; // p
j=2;
while(p&&j<i)
{
p=p->nextsibling;
j++;
}
if(j==i) //
{
c->nextsibling=p->nextsibling;
p->nextsibling=c;
}
else // p i-1
return ERROR;
}
return OK;
}
else // T
return ERROR;
}
// ： T ，p T ，1≤i≤p
// ： T p i
// p ， p
Status DeleteChild(CSTree &T,CSTree p,int i)
{
CSTree b;
int j;
if(T) // T
{
if(i==1) //
{
b=p->firstchild;
p->firstchild=b->nextsibling; // p
b->nextsibling=NULL;
DestroyTree(b);
}
else //
{
p=p->firstchild; // p
j=2;
while(p&&j<i)
{
p=p->nextsibling;
j++;
}
if(j==i) // i
{
b=p->nextsibling;
p->nextsibling=b->nextsibling;
b->nextsibling=NULL;
DestroyTree(b);
}
else // p i
return ERROR;
}
return OK;
}
else
return ERROR;
}
// — T
void PostOrderTraverse(CSTree T,void(*Visit)(TElemType))
{
CSTree p;
if(T)
{
if(T->firstchild) //
{
PostOrderTraverse(T->firstchild,Visit); //
p=T->firstchild->nextsibling; // p
while(p)
{
PostOrderTraverse(p,Visit); //
p=p->nextsibling; // p
}
}
Visit(Value(T)); //
}
}
// — T
void LevelOrderTraverse(CSTree T,void(*Visit)(TElemType))
{
CSTree p;
LinkQueue q;
InitQueue(q);
if(T)
{
Visit(Value(T)); //
EnQueue(q,T); //
while(!QueueEmpty(q)) //
{
DeQueue(q,p); //
if(p->firstchild) //
{
p=p->firstchild;
Visit(Value(p)); //
EnQueue(q,p); //
while(p->nextsibling) //
{
p=p->nextsibling;
Visit(Value(p)); //
EnQueue(q,p); //
}
}
}
}
}
void vi(TElemType c)
{
printf("%c ",c);
}
int main()
{
int i;
CSTree T,p,q;
TElemType e,e1;
InitTree(T);
printf(" , ? %d(1: 0: ) %c %d
",TreeEmpty(T),Root(T),TreeDepth(T));
CreateTree(T);
printf(" T , ? %d(1: 0: ) %c %d
",TreeEmpty(T),Root(T),TreeDepth(T));
printf(" T:
");
PreOrderTraverse(T,vi);
printf("
: ");
scanf("%c%*c%c%*c",&e,&e1);
Assign(T,e,e1);
printf(" T:
");
PostOrderTraverse(T,vi);
printf("
%c %c, %c, %c
",e1,Parent(T,e1),LeftChild(T,e1),RightSibling(T,e1));
printf(" p:
");
InitTree(p);
CreateTree(p);
printf(" p:
");
LevelOrderTraverse(p,vi);
printf("
p T ， T p : ");
scanf("%c%d%*c",&e,&i);
q=Point(T,e);
InsertChild(T,q,i,p);
printf(" T:
");
LevelOrderTraverse(T,vi);
printf("
T e i ， e i: ");
scanf("%c%d",&e,&i);
q=Point(T,e);
DeleteChild(T,q,i);
printf(" T:
",e,i);
LevelOrderTraverse(T,vi);
printf("
");
DestroyTree(T);
}