首页 > 其他分享 >数据结构 树的遍历代码实现

数据结构 树的遍历代码实现

时间:2022-11-01 22:48:05浏览次数:61  
标签:node 遍历 LinkNode 代码 NULL front 数据结构 root

7.5、二叉树的遍历

  • 先序遍历:根左右(NLR)
  • 中序遍历:左根右(LNR)
  • 后序遍历:左右根(LRN)
  • 层次遍历:一层从左到右遍历

代码实现

//访问结点
void Vist(TreeNode *node){
    printf("%d , ",node->data);
}

//先序遍历
void PreOrder(LinkTree T){
    if(T != NULL){
        Vist(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

//中序遍历
void InOrder(LinkTree T){
    if(T != NULL){
        InOrder(T->lchild);
        Vist(T);
        InOrder(T->rchild);
    }
}

//后序遍历
void PostOrder(LinkTree T){
    if(T != NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        Vist(T);
    }
}

//求一个二叉树的深度
int TreeDepth(LinkTree T){
    if(T == NULL){
        return 0;
    }else{
        int l = TreeDepth(T->lchild);
        int r = TreeDepth(T->rchild);
        return l > r? l+1:r+1;
    }
}

测试

int main(){
    LinkTree root;
    InitTree(&root,1);
    AddLeftChild(2,root);
    AddRightChild(3,root);
    AddLeftChild(4,root->lchild);
    AddRightChild(5,root->lchild);
    AddLeftChild(6,root->rchild);
    AddRightChild(7,root->rchild);

    printf("先序遍历:");
    PreOrder(root);
    printf("\n");
    printf("中序遍历:");
    InOrder(root);
    printf("\n");
    printf("后序遍历:");
    PostOrder(root);
    printf("\n 二叉树的深度为:%d \n",TreeDepth(root));
}
//结果:
先序遍历:1 , 2 , 4 , 5 , 3 , 6 , 7 , 
中序遍历:4 , 2 , 5 , 1 , 6 , 3 , 7 , 
后序遍历:4 , 5 , 2 , 6 , 7 , 3 , 1 ,
二叉树的深度为:3 

层次遍历

借助队列来操作

//结点
typedef struct LinkNode{
    TreeNode *data;
    struct LinkNode *next;
}LinkNode;
//链队列定义
typedef struct{
    LinkNode *front,*rear;//*front 队头指针, *rear 队尾指针
}LinkQueue;
//初始化带头结点的队列
int InitLinkQueue(LinkQueue *Q){
    (*Q).front = (*Q).rear = (LinkNode *)malloc(sizeof(LinkNode));
    if((*Q).front == NULL || (*Q).rear == NULL) return false;
    (*Q).front->next = NULL;
    return true;
};
//带头结点判断是否为空
int IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear) return true;
    else return false;
}
//带头结点入队操作
int EnQueue(LinkQueue *Q,TreeNode *e){
    LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
    if(p==NULL) return false;//分配内存失败
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
}
//带头结点出队操作
int DeQueue(LinkQueue *Q,TreeNode **e){
    if(Q->front == Q->rear) return false;//队列为空,出队失败
    LinkNode *p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if(Q->rear == p){       //如果出队的元素是对尾元素,需要特殊处理
        Q->rear = Q->front;
    }
    free(p);//释放片
    return true;
}

//访问结点
void Vist(TreeNode *node){
    printf("%d , ",node->data);
}

//层次遍历
void LevelOrder(LinkTree T){
    LinkQueue Q;
    InitLinkQueue(&Q);
    TreeNode *node;
    EnQueue(&Q,T);
    while(!IsEmpty(Q)){
        DeQueue(&Q,&node);
        Vist(node);
        if(node->lchild != NULL) EnQueue(&Q,node->lchild);
        if(node->rchild != NULL) EnQueue(&Q,node->rchild);
    }
}

测试

int main(){
    printf("层次遍历:");
    LevelOrder(root);
}    
//结果:
层次遍历:1 , 2 , 3 , 4 , 5 , 6 , 7 , 

知道遍历恢复二叉树,

必须需要知道其中之一:

  • 中序 + 前序

  • 中序 + 后序

  • 中序 + 层次

可以得到一个唯一的二叉树

标签:node,遍历,LinkNode,代码,NULL,front,数据结构,root
From: https://www.cnblogs.com/shuisanya/p/16849418.html

相关文章