树的基本操作(数据结构)

数据结构)"/>

树的基本操作(数据结构)

树的创建

//结构结点 
typedef struct Node
{int data;struct Node *leftchild;struct Node *rightchild;
}*Bitree,BitNode;//初始化树 
void Create(Bitree &T)
{int d;printf("输入结点(按0为空结点):");scanf("%d",&d);if(d!=0){T = (Bitree)malloc(sizeof(BitNode));T->data=d;Create(T->leftchild);Create(T->rightchild);}else{T=NULL;return;}
}

遍历树(递归)

//先序遍历 
void PreOrder(Bitree &T)
{Bitree D;D=T;if (D){printf("%d", D->data);PreOrder(D->leftchild);PreOrder(D->rightchild);}
}//中序遍历
void InOrder(Bitree &T)
{Bitree D;D=T;if (T){InOrder(D->leftchild);printf("%d", D->data);InOrder(D->rightchild);}}//后序遍历
void PostOrder(Bitree &T)
{Bitree D;D=T;	if (T){PostOrder(D->leftchild);PostOrder(D->rightchild);printf("%d", D->data);}
}

非递归遍历

#define MaxSize 100
typedef struct{BitNode *data[MaxSize];int top;
}SqStack;//初始化栈
void InitStack(SqStack &S){S.top = -1;
} //判断栈空
bool StackEmpty(SqStack S){if(S.top==-1) return true;//空栈else return false; 
} //进栈
void Push(SqStack &S, BitNode *x){if(S.top==MaxSize-1) return;//满栈S.top = S.top+1;//指针加1S.data[S.top]=x;//新元素入栈  
} //出栈
BitNode* Pop(SqStack &S){if(S.top==-1) return NULL;//空栈BitNode *x;x= S.data[S.top];S.top = S.top-1; return x;
} 
//非递归遍历
void InOrder2(Bitree &T){SqStack S;InitStack(S);//初始化栈 Bitree P=T;//p是遍历指针 while(P||!StackEmpty(S)){if(P){//一路向左 Push(S,P);//当前结点入栈 P=P->leftchild;//左孩子不为空，一直向左走 } else{P=Pop(S);//出栈，并转向右子树 printf("%d",P->data);//输出出栈元素 P=P->rightchild;//向右子树走 }}
}void PreOrder2(Bitree &T){SqStack S;InitStack(S);//初始化栈 Bitree P=T;//p是遍历指针 while(P||!StackEmpty(S)){if(P){//一路向左 printf("%d",P->data);Push(S,P);//当前结点入栈 P=P->leftchild;//左孩子不为空，一直向左走 } else{P=Pop(S);P=P->rightchild; }}
}

层次遍历

#define MaxSize 100
typedef struct{int front,rear;BitNode *data[MaxSize];
}SqQueue;//初始化队列
void InitQueue(SqQueue &Q){Q.front=Q.rear=0;
} //判断队列是否为空
bool QueueEmpty(SqQueue Q){if(Q.front==Q.rear) return true;//空队列else return false; 
}//入队
bool EnQueue(SqQueue &Q,BitNode *x){if((Q.rear+1)%MaxSize==Q.front){//判断队满return false; }Q.data[Q.rear]=x;//新元素入队 Q.rear = (Q.rear+1)%MaxSize;//队尾指针加一取模 让队列循环使用 return true;
} //出队
BitNode* DeQueue(SqQueue &Q){if(Q.front==Q.rear) return NULL;//队列为空 BitNode *x;x = Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;//对头指针后移 return x;
} //层次遍历
void LevelOrder(Bitree &T){SqQueue Q;InitQueue(Q);Bitree P;EnQueue(Q,T);while(!QueueEmpty(Q)){P=DeQueue(Q);printf("%d ",P->data);if(P->leftchild!=NULL)EnQueue(Q,P->leftchild);if(P->rightchild!=NULL)EnQueue(Q,P->rightchild);}
} 

主函数

int main(){Bitree T;Create(T);printf("前序遍历:");PreOrder(T);printf("\n");printf("中序遍历:");InOrder(T);printf("\n");printf("后序遍历:");PostOrder(T);printf("\n");printf("中序遍历(非):");InOrder2(T);printf("\n");printf("前序遍历(非):"); PreOrder2(T);printf("\n");printf("层次遍历:");LevelOrder(T);return 0;
}