首页 > 其他分享 >二叉树的遍历

二叉树的遍历

时间：2024-07-27 12:55:15浏览次数：20  
标签：结点 遍历 BinTree BT 二叉树 printf Data

提纲挈领的说，先序中序后序的遍历区别在于遍历根节点的时机。 

1.先序

        1.1递归形式

 遍历过程为：

① 访问根结点； ② 先序遍历其左子树； ③ 先序遍历其右子树。

void PreOrderTraversal( BinTree BT )
{
    if( BT ) {
     printf(“%d”, BT->Data);
     PreOrderTraversal( BT->Left );
     PreOrderTraversal( BT->Right );
    }
}

        1.2非递归形式

使用一个栈，按照根节点、右子树、左子树的顺序入栈。 

void PreOrderTraversal(BinTree BT) {
    if (BT == NULL) return;

    Stack S = CreatStack(100); /* 示例最大大小，根据需要调整 */
    Push(&S, BT);

    while (!IsEmpty(S)) {
        BinTree T = Pop(&S);
        printf("%5d ", T->Data);
        
        if (T->Right) Push(&S, T->Right);  // 右子节点先入栈
        if (T->Left) Push(&S, T->Left);    // 左子节点后入栈
    }
}

2.中序

        2.1递归形式

遍历过程为： ① 中序遍历其左子树； ② 访问根结点； ③ 中序遍历其右子树。 

void InOrderTraversal( BinTree BT )
{
 if( BT ) {
     InOrderTraversal( BT->Left );
     printf(“%d”, BT->Data);
     InOrderTraversal( BT->Right );
 }
}

        2.2非递归形式

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。使用栈的方式进行遍历时，通常先遍历左子树直到没有左子节点，然后访问根节点，最后遍历右子树。 

中序遍历非递归遍历算法【使用堆栈】

 遇到一个结点，就把它压栈，并去遍历它的左子树；

 当左子树遍历结束后，从栈顶弹出这个结点并访问它；

 然后按其右指针再去中序遍历该结点的右子树。 

void InOrderTraversal( BinTree BT )
{ 
    BinTree T=BT;
    Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/
    while( T || !IsEmpty(S) ){
         while(T){ /*一直向左并将沿途结点压入堆栈*/
             Push(S,T);
             T = T->Left;
         }
         if(!IsEmpty(S)){
             T = Pop(S); /*结点弹出堆栈*/
             printf(“%5d”, T->Data); /*（访问）打印结点*/
             T = T->Right; /*转向右子树*/
         }
    }
}

3.后序

        3.1递归形式

 遍历过程为： ① 后序遍历其左子树； ② 后序遍历其右子树； ③ 访问根结点。

void PostOrderTraversal( BinTree BT )
{
 if( BT ) {
     PostOrderTraversal( BT->Left );
     PostOrderTraversal( BT->Right);
     printf(“%d”, BT->Data);
 }
}

        3.2非递归形式

        使用两个栈，第一个栈用于存储节点，第二个栈用于存储遍历结果，最后反向打印第二个栈的内容。

void PostOrderTraversal(BinTree BT) {
    if (BT == NULL) return;

    Stack S1 = CreatStack(100);  // 用于保存节点
    Stack S2 = CreatStack(100);  // 用于保存遍历结果

    Push(&S1, BT);

    while (!IsEmpty(S1)) {
        BinTree T = Pop(&S1);
        Push(&S2, T);  // 将节点压入S2

        if (T->Left) Push(&S1, T->Left);
        if (T->Right) Push(&S1, T->Right);
    }

    // 打印结果栈中的节点数据，顺序为后序遍历结果
    while (!IsEmpty(S2)) {
        BinTree T = Pop(&S2);
        printf("%5d ", T->Data);
    }
}

4.层序

        4.1层序遍历的核心问题 

我们需要从上到下，从左至右依次输出每个结点，这相当于“二维结构的线性化”

 从结点访问其左、右儿子结点

 访问左儿子后，右儿子结点怎么办？

 需要一个存储结构保存暂时不访问的结点

 存储结构：堆栈、队列 

        4.1队列实现 

         遍历从根结点开始，首先将根结点入队，然后开始执行循环：结点出队、访问该结点、其左右儿子入队。

层序基本过程：

 先根结点入队，然后：

 从队列中取出一个元素；

 访问该元素所指结点；

 若该元素所指结点的左、右孩子结点非空， 则将其左、右孩子的指针顺序入队。 

void LevelOrderTraversal ( BinTree BT )
{ 
    Queue Q; 
    BinTree T;
    if ( !BT ) return; /* 若是空树则直接返回 */
    Q = CreatQueue( MaxSize ); /*创建并初始化队列Q*/
    AddQ( Q, BT );
    while ( !IsEmptyQ( Q ) ) {
         T = DeleteQ( Q );
         printf(“%d\n”, T->Data); /*访问取出队列的结点*/
         if ( T->Left ) AddQ( Q, T->Left );
         if ( T->Right ) AddQ( Q, T->Right );
    }
}

 5.二叉树及其遍历C语言实现

二叉树示例

代码示例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义学生信息结构体
typedef struct student {
    char num[50];   // 学号
    char name[50];  // 姓名
    char sex[10];   // 性别
    int age;        // 年龄
} ElementType;

typedef struct TreeNode *BinTree;
typedef BinTree Position;

struct TreeNode {
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

// 栈结构体及相关操作函数的声明
typedef struct StackNode *Stack;
Stack CreateStack(int MaxSize);
void Push(Stack S, BinTree BT);
BinTree Pop(Stack S);
int IsEmpty(Stack S);

// 队列结构体及相关操作函数的声明
typedef struct QueueNode *Queue;
Queue CreateQueue(int MaxSize);
void AddQ(Queue Q, BinTree BT);
BinTree DeleteQ(Queue Q);
int IsEmptyQ(Queue Q);

// 递归先序遍历
void PreOrderTraversalRecursive(BinTree BT) {
    if (BT) {
        printf("%s ", BT->Data.num);
        PreOrderTraversalRecursive(BT->Left);
        PreOrderTraversalRecursive(BT->Right);
    }
}

// 非递归先序遍历
void PreOrderTraversal(BinTree BT) {
    if (BT == NULL) return;

    Stack S = CreateStack(100); /* 示例最大大小，根据需要调整 */
    Push(S, BT);

    while (!IsEmpty(S)) {
        BinTree T = Pop(S);
        printf("%s ", T->Data.num);

        if (T->Right) Push(S, T->Right);  // 右子节点先入栈
        if (T->Left) Push(S, T->Left);    // 左子节点后入栈
    }
}

// 递归中序遍历
void InOrderTraversalRecursive(BinTree BT) {
    if (BT) {
        InOrderTraversalRecursive(BT->Left);
        printf("%s ", BT->Data.num);
        InOrderTraversalRecursive(BT->Right);
    }
}

// 非递归中序遍历
void InOrderTraversal(BinTree BT) {
    BinTree T = BT;
    Stack S = CreateStack(100); /* 示例最大大小，根据需要调整 */
    while (T || !IsEmpty(S)) {
        while (T) { /* 一直向左并将沿途结点压入堆栈 */
            Push(S, T);
            T = T->Left;
        }
        if (!IsEmpty(S)) {
            T = Pop(S); /* 结点弹出堆栈 */
            printf("%s ", T->Data.num); /* （访问）打印结点 */
            T = T->Right; /* 转向右子树 */
        }
    }
}

// 递归后序遍历
void PostOrderTraversalRecursive(BinTree BT) {
    if (BT) {
        PostOrderTraversalRecursive(BT->Left);
        PostOrderTraversalRecursive(BT->Right);
        printf("%s ", BT->Data.num);
    }
}

// 非递归后序遍历
void PostOrderTraversal(BinTree BT) {
    if (BT == NULL) return;

    Stack S1 = CreateStack(100);  // 用于保存节点
    Stack S2 = CreateStack(100);  // 用于保存遍历结果

    Push(S1, BT);

    while (!IsEmpty(S1)) {
        BinTree T = Pop(S1);
        Push(S2, T);  // 将节点压入S2

        if (T->Left) Push(S1, T->Left);
        if (T->Right) Push(S1, T->Right);
    }

    // 打印结果栈中的节点数据，顺序为后序遍历结果
    while (!IsEmpty(S2)) {
        BinTree T = Pop(S2);
        printf("%s ", T->Data.num);
    }
}

// 层序遍历
void LevelOrderTraversal(BinTree BT) {
    if (BT == NULL) return;

    Queue Q = CreateQueue(100); /* 创建并初始化队列 */
    AddQ(Q, BT);
    while (!IsEmptyQ(Q)) {
        BinTree T = DeleteQ(Q);
        printf("%s ", T->Data.num); /* 访问取出队列的结点 */
        if (T->Left) AddQ(Q, T->Left);
        if (T->Right) AddQ(Q, T->Right);
    }
}

// 栈和队列相关函数的占位符实现
struct StackNode {
    BinTree *Data;
    int Top;
    int MaxSize;
};

struct QueueNode {
    BinTree *Data;
    int Front, Rear;
    int MaxSize;
};

Stack CreateStack(int MaxSize) {
    Stack S = (Stack)malloc(sizeof(struct StackNode));
    S->Data = (BinTree *)malloc(MaxSize * sizeof(BinTree));
    S->Top = -1;
    S->MaxSize = MaxSize;
    return S;
}

void Push(Stack S, BinTree BT) {
    if (S->Top < S->MaxSize - 1) {
        S->Data[++S->Top] = BT;
    } else {
        printf("Stack Full\n");
    }
}

BinTree Pop(Stack S) {
    if (S->Top > -1) {
        return S->Data[S->Top--];
    } else {
        printf("Stack Empty\n");
        return NULL;
    }
}

int IsEmpty(Stack S) {
    return S->Top == -1;
}

Queue CreateQueue(int MaxSize) {
    Queue Q = (Queue)malloc(sizeof(struct QueueNode));
    Q->Data = (BinTree *)malloc(MaxSize * sizeof(BinTree));
    Q->Front = Q->Rear = 0;
    Q->MaxSize = MaxSize;
    return Q;
}

void AddQ(Queue Q, BinTree BT) {
    if ((Q->Rear + 1) % Q->MaxSize != Q->Front) {
        Q->Data[Q->Rear] = BT;
        Q->Rear = (Q->Rear + 1) % Q->MaxSize;
    } else {
        printf("Queue Full\n");
    }
}

BinTree DeleteQ(Queue Q) {
    if (Q->Front != Q->Rear) {
        BinTree BT = Q->Data[Q->Front];
        Q->Front = (Q->Front + 1) % Q->MaxSize;
        return BT;
    } else {
        printf("Queue Empty\n");
        return NULL;
    }
}

int IsEmptyQ(Queue Q) {
    return Q->Front == Q->Rear;
}

// 创建一个简单的二叉树用于测试
BinTree CreateSampleTree() {
    BinTree node1 = (BinTree)malloc(sizeof(struct TreeNode));
    BinTree node2 = (BinTree)malloc(sizeof(struct TreeNode));
    BinTree node3 = (BinTree)malloc(sizeof(struct TreeNode));
    BinTree node4 = (BinTree)malloc(sizeof(struct TreeNode));
    BinTree node5 = (BinTree)malloc(sizeof(struct TreeNode));

    strcpy(node1->Data.num, "1");
    strcpy(node2->Data.num, "2");
    strcpy(node3->Data.num, "3");
    strcpy(node4->Data.num, "4");
    strcpy(node5->Data.num, "5");

    node1->Left = node2;
    node1->Right = node3;
    node2->Left = node4;
    node2->Right = node5;
    node3->Left = node3->Right = NULL;
    node4->Left = node4->Right = NULL;
    node5->Left = node5->Right = NULL;

    return node1;
}

int main() {
    // 创建一个样例二叉树
    BinTree root = CreateSampleTree();

    // 测试递归先序遍历
    printf("递归先序遍历: ");
    PreOrderTraversalRecursive(root);
    printf("\n");

    // 测试非递归先序遍历
    printf("非递归先序遍历: ");
    PreOrderTraversal(root);
    printf("\n");

    // 测试递归中序遍历
    printf("递归中序遍历: ");
    InOrderTraversalRecursive(root);
    printf("\n");

    // 测试非递归中序遍历
    printf("非递归中序遍历: ");
    InOrderTraversal(root);
    printf("\n");

    // 测试递归后序遍历
    printf("递归后序遍历: ");
    PostOrderTraversalRecursive(root);
    printf("\n");

    // 测试非递归后序遍历
    printf("非递归后序遍历: ");
    PostOrderTraversal(root);
    printf("\n");

    // 测试层序遍历
    printf("层序遍历: ");
    LevelOrderTraversal(root);
    printf("\n");

    return 0;
}

程序运行结果： 

 

6.二叉树遍历的总结 

先序、中序和后序遍历过程：遍历过程中经过结点的路线一 样，只是访问各结点的时机不同。

 图中在从入口到出口的曲线上用⊗，☆和△三种符号分别标 记出了先序、中序和后序访问各结点的时刻

 

标签：结点,遍历,BinTree,BT,二叉树,printf,Data
From： https://blog.csdn.net/weixin_65866298/article/details/140724347

相关文章

  • [C++]广度优先遍历
       代码与图见上图思路定义一个一维数组（char）和一个二维数组（int），一个bool类型数组来判断该节点是否被访问过。函数中定义队列，对各个结点进行入队出队，并标记为已访问。当该邻结点未被标记且与该节点连接，进行上述操作。注意：for循环的i变量初始赋值随二维数组而变化。如：......
  • 二叉树及其存储实现C语言（附上源码）
    1.什么是二叉树        二叉树是一种特殊的树型结构，其特点是每个结点至多只有两棵子树（即二叉树不存在度大于二的结点），并且二叉树的子树有左右之分，次序不可颠倒【有序树】。 2.二叉树的定义二叉树T：一个有穷的结点集合。    -这个集合可以为空；    -......
  • 数据结构 二叉树 前 中 后 序列
    简单二叉树的遍历如果看完还是不太懂就观看速成视频https://www.bilibili.com/video/BV1Ub4y147Zv/?spm_id_from=333.337.search-card.all.click&vd_source=e5f8765d50fb89ef04eb150bd76075b5引用资料文献链接放到篇尾简单术语解释节点(Node)：二叉树中的一个元素，包含值和......
  • 【秋招 Learning_note】| 拿捏二叉树考点！(一)
    文章目录引言二叉树的性质性质一结点数与层数的关系性质二结点数与层数的关系性质三叶子节点与度为2的节点关系性质四深度与节点数的关系两种特殊的二叉树满二叉树完全二叉树二叉树的遍历顺序前序遍历中序遍历后序遍历常考内容及详细解法题型一、基本概念与性质题......
  • P9304 「DTOI-5」3-1题解，c++树的遍历例题
    题意给定以n(1≤n≤1......
  • leetcode103. 二叉树的锯齿形层序遍历，简单易懂附代码详解
    leetcode103.二叉树的锯齿形层序遍历给你二叉树的根节点root，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。示例1：输入：root=[3,9,20,null,null,15,7]输出：[[3],[20,9],[15,7]]示例2：输入：root=[1]输出：[[1......
  • 二叉树的分类
    二叉树是最常见的树，二叉树的每个节点最多只有两个子节点二叉树的分类 完全二叉树 指二叉树的所有节点按照从左往右填充就像这样： 满二叉树是一种完全二叉树，当完全二叉树每个层次都被填满时，就是满二叉树例如上图中的最后一棵树堆 堆是一种带有特定排序的完全二叉......
  • 二叉树的三序遍历之非递归版
    二叉树的先序遍历/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode():val(0),left(nullptr),right(nullptr){}*TreeNode(intx):val(x),left(nullptr),right(n......
  • 【数据结构】二叉树
    二叉树结构描述：#include<iostream>#include<queue>usingnamespacestd;typedefintDataType;classNode{private:DataTypedata;Node*left;Node*right;friendclassBinaryTree;};typedefclassBinaryTree{private:N......
  • 算法力扣刷题记录 五十七【236. 二叉树的最近公共祖先】和【235. 二叉搜索树的最近公
    前言公共祖先解决。二叉树和二叉搜索树条件下的最近公共祖先。二叉树篇继续。一、【236.二叉树的最近公共祖先】题目阅读给定一个二叉树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树T的两个节点p、q，最近公共祖先表示为一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99