在线客服:
亚博直播 亚博直播
全国服务热线:010-34915482
您的位置:首页 > 新闻中心 >

二叉树(递归和非递归)的预遍历和C语言实现

浏览 104次 来源:【jake推荐】 作者:-=Jake=-    时间:2021-01-20 18:01:20
[摘要] 二叉树先序遍历的实现思想是:访问根节点;访问当前节点的左子树;若当前节点无左子树,则访问当前节点的右子树;二叉树为根节点的子树遍历完成。为根节点的子树也遍历完成。的左右子树全部遍历完成,因此整个二叉树遍历完成;中二叉树采用先序遍历得到的序列为:语言实现代码为:先序遍历:语言实现代码为:运行结果先序遍历:

二叉树预遍历的实现思路是:访问根节点;访问当前节点的左子树;如果当前节点没有左子树,则访问当前节点的右子树;

二叉树遍历非递归

图1二叉树

以图1为例,以预遍历的思想遍历二叉树的过程是:访问二叉树的根节点并找到1;访问节点1的左子树并找到节点2;访问节点2树的左子节点二叉树遍历非递归,找到节点4;因为访问节点4的左子树失败二叉树遍历非递归,并且没有右子树,所以以节点4为根节点的子树的遍历完成。但是节点2尚未遍历其右子树,因此现在开​​始遍历,即访问节点5。由于节点5没有左子树和右子树,因此遍历了节点5,并且以节点2为根节点的子树被遍历。也遍历了。 。现在返回到节点1yabo亚博 ,并开始遍历该节点的右子树,即访问节点3。访问节点3的左侧子树,并找到节点6;因为节点6没有左子树和右子树,所以遍历节点6并返回到节点3。遍历右子树以找到节点7。节点7没有左右子树yabo手机版凤凰体育平台 ,因此以节点3为根节点的子树遍历完成,并且节点1同时返回。由于遍历了节点1的所有左,右子树,因此遍历了整个二叉树;

二叉树的遍历 非递归_二叉树遍历非递归_二叉树遍历非递归

因此,遍历图1中的二叉树以获得序列:

1 2 4 5 3 6 7

二叉树的遍历遍历的递归实现采用递归思想,因此可以递归实现。 C语言实现代码为:

#include 
#include 
#define TElemType int
//构造结点的结构体
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
  
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
//模拟操作结点元素的函数,输出结点本身的数值
void displayElem(BiTNode* elem){
    printf("%d ",elem->data);
}
//先序遍历
void PreOrderTraverse(BiTree T){
    if (T) {
        displayElem(T);//调用操作结点数据的函数方法
        PreOrderTraverse(T->lchild);//访问该结点的左孩子
        PreOrderTraverse(T->rchild);//访问该结点的右孩子
    }
    //如果结点为空,返回上一层
    return;
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("先序遍历: \n");
    PreOrderTraverse(Tree);
}

运行结果:

一阶遍历:

1 2 4 5 3 6 7

非递归实现和递归的基础实现依赖于堆栈存储结构。因此,可以直接通过递归思维来实现二叉树的预遍历yabo网页版 ,或者可以使用堆栈的存储结构来模拟递归思维。其C语言实现的代码是:

二叉树遍历非递归_二叉树的遍历 非递归_二叉树遍历非递归

#include 
#include 
#define TElemType int
int top=-1;//top变量时刻表示栈顶元素所在位置
//构造结点的结构体
typedef struct BiTNode{
    TElemType data;//数据域
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
    *T=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->data=1;
    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->data=2;
    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->lchild->rchild->data=5;
    (*T)->lchild->rchild->lchild=NULL;
    (*T)->lchild->rchild->rchild=NULL;
    (*T)->rchild->data=3;
    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->lchild->data=6;
    (*T)->rchild->lchild->lchild=NULL;
    (*T)->rchild->lchild->rchild=NULL;
    (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
    (*T)->rchild->rchild->data=7;
    (*T)->rchild->rchild->lchild=NULL;
    (*T)->rchild->rchild->rchild=NULL;
    (*T)->lchild->lchild->data=4;
    (*T)->lchild->lchild->lchild=NULL;
    (*T)->lchild->lchild->rchild=NULL;
}
//前序遍历使用的进栈函数
void push(BiTNode** a,BiTNode* elem){
    a[++top]=elem;
}
//弹栈函数
void pop( ){
    if (top==-1) {
        return ;
    }
    top--;
}
//模拟操作结点元素的函数,输出结点本身的数值
void displayElem(BiTNode* elem){
    printf("%d ",elem->data);
}
//拿到栈顶元素
BiTNode* getTop(BiTNode**a){
    return a[top];
}
//先序遍历非递归算法
void PreOrderTraverse(BiTree Tree){
    BiTNode* a[20];//定义一个顺序栈
    BiTNode * p;//临时指针
    push(a, Tree);//根结点进栈
    while (top!=-1) {
        p=getTop(a);//取栈顶元素
        pop();//弹栈
        while (p) {
            displayElem(p);//调用结点的操作函数
            //如果该结点有右孩子,右孩子进栈
            if (p->rchild) {
                push(a,p->rchild);
            }
            p=p->lchild;//一直指向根结点最后一个左孩子
        }
    }
}
int main(){
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("先序遍历: \n");
    PreOrderTraverse(Tree);
}

运行结果

一阶遍历:

1 2 4 5 3 6 7

老王
本文标签:递归,先序遍历,二叉树遍历

推荐阅读

最新评论