#include<stdio.h>
#include<string.h>
//定义元素类型
typedef int ElemType;
//定义二叉树链式存储结构
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//定义线索二叉树链式存储结构
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode, *ThreadTree;
//双亲表示法的存储结构
#define MAX_TREE_SIZE 100
typedef struct{
ElemType data;
int parent;
}PTNode;
typedef struct{
PTNode nodes[MAX_TREE_SIZE];
int n;
}PTree;
//孩子兄弟表示法
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode, *CSTree;
//访问结点信息
void visit(BiTNode T){
printf("Node Info is : %d",T->data);
}
//递归二叉树先序遍历
void preOrder(BiTree T){
if (T!=NULL){
visit(T); // 访问结点信息
preOrder(T->lchild);
preOrder(T->rchild);
}
}
//递归二叉树中序遍历
void InOrder(BiTree T){
if (T!=NULL){
InOrder(T->lchild);
visit(T); // 访问结点信息
InOrder(T->rchild);
}
}
//递归二叉树的后序遍历
void PostOrder(BiTree T){
if (T!=NULL){
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}
//非递归二叉树的先序遍历
void PreOrder2(BiTree T){
InitStack(S); //这里初始化栈，简写
BiTNode p = T; //遍历指针
if (p||!IsEmpty(S)){ // 栈判空方法
if (p){
visit(p);
Push(S,p); // 进栈
p=p->lchild;
}
else{
Pop(S,p); // 出栈
p=p->rchild;
}
}
}
//非递归二叉树的中序遍历
void InOrder2(BiTree T){
InitStack(S);
BiTNode p = T;
if (p||!IsEmpty(S)){
if (p){
Push(S,p);
p=p->lchild;
}
else{
visit(p);
Pop(S,p);
p=p->rchild;
}
}
}
//层次遍历
void LevelOrder(BiTree T){
InitQueue(Q); //这里初始化队列，简写
BiTNode p; // 用户指针遍历
EnQueue(Q,T); // 将根结点入队
while (!IsEmpty(Q)){
DeQueue(Q,p); //出队
visit(p);
if (p->lchild != NULL){
EnQueue(Q,P->lchild);
}
if (p->rchild != NULL){
EnQueue(Q,p->rchild);
}
}
}
//二叉排序树的非递归查找算法
BSTNode *BST_Search(BiTree T,ElemType key){
while (T!=NULL&&key!=T->data){
if (key<T->data){
T = T->lchild;
}else{
T = T->rchild;
}
return T;
}
}
