2022-1-25数据结构总结（3）

2022-1-25数据结构总结（3）

二叉树的建立

​
#include
#include

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
#include

//二叉树的结点（链式存储）
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);    //右孩子入队
    }
}