二叉树的建立

​
#include<stdio.h>
#include<string.h>struct Tree{int data;struct Tree *Lch, *Rch;
}BiTNode, *BiTree;//递归创建二叉树
BiTNode *CreatTree(BiTree &wroot){int x;scanf("%d",&x);if(x==1){        //输入x=1时，表示继续递归创建结点wroot=(BiTNode *)malloc(sizeof(BiTNode));scanf("%d",&wroot->data);wroot->Lch=CreatTree(wroot->Lch);wroot->Rch=CreatTree(wroot->Rch);}elsewroot=NULL;return wroot;
}//先序(根左右)遍历
void Preorder(BiTree wroot){if(wroot!=NULL){printf("%d",wroot->data);Preorder(wroot->Lch);Preorder(wroot->Rch);}
}//中序(左根右)遍历
void Midorder(BiTree wroot){if(wroot!=NULL){Midorder(wroot->Lch);printf("%d",wroot->data);Midorder(wroot->Rch);}
}//后序(左右根)遍历
void Postorder(BiTree wroot){if(wroot!=NULL){Postorder(wroot->Lch);Postorder(wroot->Rch);printf("%d",wroot->data);}
}//中序遍历的非递归算法，栈的思想
void Midorder2(BiTree wroot){struct Tree *s[255];int top=1;s[top]=wroot;do{while(s[top]!=NULL){S[top+1]=s[top]->Lch;    //第一步，左进栈，遇到空才停止top++;}if(top>1){top--;print("%d",s[top]->data);    //第二步，退栈打印s[top]=s[top]->Rch;    //第三步，右进栈覆盖已经打印出的元素}}while(top!=1||s[top]!=NULL)    //栈底时，栈元素为空时，跳出循环
}//求树深度
int treeDepth(BiTree T){if(T==NUll)return 0;else{int l=treeDepth(T->Lch);int r=treeDepth(T->Rch);return l>r?l+1:r+1;}}void TestTree(){BiTree root=NULL;wroot=CreatTree(root);//...........
}​

 二叉树的层次遍历

#include<stdio.h>
#include<string.h>//二叉树的结点（链式存储）
struct Tree{int data;struct Tree *Lch, *Rch;
}BiTNode, *BiTree;//链式队列结点
typedef struct LinkNode{ElemType *data;    //这里存储的是树结点的指针，以便节省存储空间struct LinkNode *next;
}LinkNode;typedef struct {LinkNode *front, *rear;
}LinkQueue;//初始化队列，带头结点
void InitQueue(LinkQueue &Q){//初始时，front,rear都指向头结点,Q.rear=Q.front=(LinkNode *)malloc(sizeof(LinkNode));Q.front->next=NULL;
}//判断队列是否为空
bool IsEmpty(LinkQueue Q){if(Q.rear=Q.front)return true;elsereturn false;
}//入队操作
bool EnQueue(LinkQueue &Q,ElemType x){LinkQueue *s=(LinkQueue *)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;Q.rear->next=s;    //新节点插入到队尾指针之后Q.rear=s;    //移动队尾指针位置
}//出队操作
bool DeQueue(LinkQueue &Q, ElemType &x){if(Q.rear==Q.front)    //队空则报错return false;LinkQueue *p=Q.front->next;x=p->data;Q.front->next=p->next;if(Q.rear==p)    //最后一个结点出队Q.rear=Q.front;free(p);return true;
}void LevelOrder(BiTree T){    LinkQueue Q;InitQueue(Q);    //初始化辅助队列BiTree P;    //新建立一个树结点接纳出队的结点EnQueue(Q,T)    //根结点入队while(!IsEmpty(Q)){DeQueue(Q,p);    //队头结点访问出队visit(p);    //访问出队结点if(p->Lch!=NULL)EnQueue(Q,p->Lch);    //左孩子入队if(p->Rch!=NULL)EnQueue(Q,p->Rch);    //右孩子入队}
}