数据结构 -- 二叉树的遍历_先序遍历二叉树数据结构-CSDN博客

本文链接：https://blog.csdn.net/2202_75324779/article/details/146381766

二叉树的遍历

二叉树的先中后序遍历

什么是遍历

遍历：按照某种次序把所有的结点都访问一遍

线性结构：从头到尾依次遍历或者从尾到头一次遍历

树形结构：（层次遍历）基于树的层次特性确定的次序规则

二叉树的遍历：基于二叉树的递归特性确定的次序规则

二叉树的递归特性：

①要么是空二叉树

②要么就是由“根结点+左子树+右子树”组成的二叉树

先序遍历：根左右（NLR）

中序遍历：左根右（LNR）

后序遍历：左右根（LRN）

分支结点逐层展开法（手算练习）

在这里插入图片描述

先序遍历：A B D G E C F

中序遍历：D G B E A F C

后序遍历：G D E B F C A

先序遍历

操作过程：

若二叉树为空树，则什么也不做；
若二叉树为非空树：

① 访问根结点；

② 先序遍历左子树；

③ 先序遍历右子树。

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//先序遍历
void PreOrder(BiTree T){
    if(T != NULL){
        visit(T);				//访问根结点
        PreOrder(T->lchild);	//先序遍历左子树
        PreOrder(T->rchild);	//先序遍历右子树
    }
}

时间复杂度：O(h)

中序遍历

操作过程：

若二叉树为空树，则什么也不做；
若二叉树为非空树：

① 中序遍历左子树；

② 访问根结点；

③ 中序遍历右子树。

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//先序遍历
void InOrder(BiTree T){
    if(T != NULL){
        InOrder(T->lchild);	//中序遍历左子树
        visit(T);				//访问根结点
        InOrder(T->rchild);	//中序遍历右子树
    }
}

时间复杂度：O(h)

后序遍历

操作过程：

若二叉树为空树，则什么也不做；
若二叉树为非空树：

① 后序遍历左子树；

② 后序遍历右子树；

③ 访问根结点；

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//后序遍历
void PostOrder(BiTree T){
    if(T != NULL){
        PostOrder(T->lchild);	//后序遍历左子树
        PostOrder(T->rchild);	//后序遍历右子树
        visit(T);				//访问根结点
    }
}

时间复杂度：O(h)

求树的深度（应用）

int treeDepth(BiTree T){
    if(T == NULL){
        return 0;
    }else{
        int l = treeDepth(T->lchild);
        int r = treeDepth(T->rchild);
        //树的深度 = Max（左子树深度，右子树深度）+1
        return l>r ? l+1 : r+1;
    }
}

二叉树的层序遍历

在这里插入图片描述

层序遍历：A B C D E F G

算法思想：

① 初始化一个辅助队列

② 根结点入队

③ 若队列非空，则队头结点出队，访问该结点，并将其左右孩子插入队尾（如果有的话）

④ 重复③直至队列为空

//二叉树结点（链式存储）
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


typedef struct LinkNode{	//链式队列节点
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{				//链式队列
    LinkNode *front,*rear;	//队列的队头和队尾指针
}LinkQueue;

//层序遍历
void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);			//初始化辅助队列
    BiTree p;
    EnQueue(Q,T);			//将根结点入队
    while(!isEmpty){		//队列不空则循环
        DeQueue(Q,p);		//队头结点出队
        visit(p);			//访问出队结点
        if(p->lchild != NULL)	EnQueue(Q,p->lchild);	//左孩子入队
        if(p->rchild != NULL)	EnQueue(Q,p->rchild);	//右孩子入队
    }
}