二叉树的建立
#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);
}
else
wroot=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;
else
return 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); //右孩子入队
}
}