代码编织梦想

二叉树中序遍历

二叉树中序遍历的实现思想是:

  1. 访问当前节点的左子树
  2. 访问根节点
  3. 访问当前节点的右子树

图 1 二叉树

以上图 1 为例,中序遍历的过程如下:

  1. 访问该二叉树的根节点,找到 1
  2. 遍历节点 1 的左子树,找到节点 2
  3. 遍历节点 2 的左子树,找到节点 4
  4. 由于节点 4 无左孩子,因此找到节点 4,并遍历节点 4 的右子树
  5. 由于节点 4 无右子树,因此节点 2 的左子树遍历完成,访问节点 2
  6. 遍历节点 2 的右子树,找到节点 5
  7. 由于节点 5 无左子树,因此访问节点 5 ,又因为节点 5 没有右子树,因此节点 1 的左子树遍历完成,访问节点 1 ,并遍历节点 1 的右子树,找到节点 3
  8. 遍历节点 3 的左子树,找到节点 6
  9. 由于节点 6 无左子树,因此访问节点 6,又因为该节点无右子树,因此节点 3 的左子树遍历完成,开始访问节点 3 ,并遍历节点 3 的右子树,找到节点 7
  10. 由于节点 7 无左子树,因此访问节点 7,又因为该节点无右子树,因此节点 1 的右子树遍历完成,即整棵树遍历完成

因此,图 1 中二叉树采用中序遍历得到的序列为:4 2 5 1 6 3 7 

二叉树中序遍历代码实现

先谈一下递归实现!!!

#include <stdio.h>
#include <stdlib.h>
 
typedef struct MyBiTNode{
    int data;  // 数据域
    struct MyBiTNode *lchild, *rchild;  // 左右孩子指针
} BiTNode;

BiTNode *CreateBiTree(BiTNode *T){
	// 结点 1 
    T = (BiTNode*)malloc(sizeof(BiTNode));
    T->data = 1;
    // 结点 2
	T->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->data = 2;
	// 结点 3
	T->rchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->rchild->data = 3;
	// 结点 4 
	T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->lchild->data = 4;
	T->lchild->lchild->lchild = NULL;
	T->lchild->lchild->rchild = NULL;
	// 结点 5
	T->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->rchild->data = 5;
	T->lchild->rchild->lchild = NULL;
	T->lchild->rchild->rchild = NULL;
	// 结点 6
	T->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->rchild->lchild->data = 6;
	T->rchild->lchild->lchild = NULL;
	T->rchild->lchild->rchild = NULL;
	// 结点 7
	T->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->rchild->rchild->data = 7; 
	T->rchild->rchild->lchild = NULL;
	T->rchild->rchild->rchild = NULL;
	return T;
}
 
// 模拟操作结点元素的函数,输出结点本身的数值
void displayElem(BiTNode* elem){
    printf("%d ", elem->data);
}

// 中序遍历
void INOrderTraverse(BiTNode *T){
    if(T){
        INOrderTraverse(T->lchild);  // 遍历左孩子
        displayElem(T);  // 调用操作结点数据的函数方法
        INOrderTraverse(T->rchild);  // 遍历右孩子
    }
    // 如果结点为空,返回上一层
    return;
} 

int main() {
    BiTNode *Tree = NULL;  // 结构体指针指向空 
    Tree = CreateBiTree(Tree);  // 传入结构体指针 
    printf("%d\n",Tree->rchild->lchild->data);  // 4 
    
    INOrderTraverse(Tree);
    return 0;
}

再谈一下非递归实现!!!

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

int top = -1;  // top变量表示栈顶元素所在位置
 
typedef struct MyBiTNode{
    int data;  // 数据域
    struct MyBiTNode *lchild, *rchild;  // 左右孩子指针
} BiTNode;

BiTNode *CreateBiTree(BiTNode *T){
	// 结点 1 
    T = (BiTNode*)malloc(sizeof(BiTNode));
    T->data = 1;
    // 结点 2
	T->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->data = 2;
	// 结点 3
	T->rchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->rchild->data = 3;
	// 结点 4 
	T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->lchild->data = 4;
	T->lchild->lchild->lchild = NULL;
	T->lchild->lchild->rchild = NULL;
	// 结点 5
	T->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->lchild->rchild->data = 5;
	T->lchild->rchild->lchild = NULL;
	T->lchild->rchild->rchild = NULL;
	// 结点 6
	T->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->rchild->lchild->data = 6;
	T->rchild->lchild->lchild = NULL;
	T->rchild->lchild->rchild = NULL;
	// 结点 7
	T->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
	T->rchild->rchild->data = 7; 
	T->rchild->rchild->lchild = NULL;
	T->rchild->rchild->rchild = NULL;
	return T;
}
 
// 模拟操作结点元素的函数,输出结点本身的数值
void displayElem(BiTNode* elem){
    printf("%d ", elem->data);
}

// 先序和中序遍历使用的进栈函数
void push(BiTNode **a, BiTNode *elem){
    a[++top] = elem;
}

// 弹栈函数
void pop(){
    if(top == -1){
        return;
    }
    top--;
}

// 拿到栈顶元素
BiTNode *getTop(BiTNode **a){
    return a[top];
}

// 中序遍历非递归算法
void InOrderTraverse_1(BiTNode *Tree){
    BiTNode *a[20]; 
    BiTNode *p; 
    push(a, Tree);  
    while(top != -1){  
        while((p = getTop(a)) && p){ 
            push(a, p->lchild);
        }
        pop();
        if(top != -1){
            p = getTop(a);
            pop();
            displayElem(p);
            push(a, p->rchild);
        }
    }
}

// 中序遍历实现的另一种方法
void InOrderTraverse_2(BiTNode *Tree){
    BiTNode *a[20];
    BiTNode *p;
    p = Tree;
    while(p || top!=-1){
        if(p){
            push(a, p);
            p = p->lchild;
        }else{  // 如果 p为 NULL,表明左子树遍历完成,需要遍历上一层结点的右子树 
            p = getTop(a);
            pop();
            displayElem(p);
            p = p->rchild;
        }
    }
}

int main() {
    BiTNode *Tree = NULL;  // 结构体指针指向空 
    Tree = CreateBiTree(Tree);  // 传入结构体指针 
    printf("%d\n",Tree->rchild->lchild->data);  // 4 
    
    InOrderTraverse_2(Tree);
    InOrderTraverse_2(Tree);
    return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_51927215/article/details/123843860

二叉树遍历之中序遍历(源代码)-爱代码爱编程

二叉树的中序遍历 要点: 1.中序遍历左子树 2.访问根节点 3.中序遍历右子树 实例: 如图:中序遍历结果:DBEAFC 中序遍历的时间复杂度为:O(n)。 如果一棵二叉排序树的节点值是数值,中序

【数据结构】二叉树的实现&递归遍历(完整代码)_ly_1115的博客-爱代码爱编程_二叉树的递归遍历及其应用代码

本次模拟二叉树实现的功能 1.按要求创建一棵树 2.计算树节点,树叶子节点的个数 3.输出树中第n层的节点个数 4.关于树前序,中序,后序的递归遍历 5.树的层序遍历 6.判断树是否为完全二叉树 7.树的前序,中序,后序的

数据结构 - 树(二叉树的 前序、中序、后序 遍历)-爱代码爱编程

二叉树遍历(前序中序后序,主要是看父节点的输出顺序) package tree; public class BinaryTreeDemo { public static void main(String[] args) { //先需要创建一颗二叉树 BinaryTree binaryTree = new

[数据结构] 二叉树中序遍历(非递归)-爱代码爱编程

#include <iostream> #include <string> #include <stack> using namespace std; class BiTreeNode { public : char data; BiTreeNode *LeftChild; BiTreeNod

二叉树的四种遍历 以及代码实现,看这一篇就够了-爱代码爱编程

★ 前言:二叉树的遍历,是我们数据结构 重点中的重点 ,90% 的笔试题都是二叉树遍历的变形 但是呢,有很多小伙伴对它的遍历方式还是有些模糊 那么,接下来我就为大家详细介绍各种遍历方式的区别: 二叉树的遍历: 1、DFS(Depth First Search):深度优先遍历 -- 栈(1)前序遍历:(2)中序遍历:(3)后序遍历:2、BFS(Br

二叉树中序遍历的实现-爱代码爱编程

二叉树中序遍历的实现 【C语言】 代码如下: #include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node *Lc,*Rc; } Bnode,*Btree; void inordor(Btree T) { if(T!=NU

数据结构——二叉链表创建二叉树(C语言版)-爱代码爱编程

数据结构——二叉链表创建二叉树 一、思想(先序思想创建):二、创建二叉树(1)传一级参数方法(2)传二级参数方法 一、思想(先序思想创建): 第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树,直到递归创建到的节点下不继续创建左子树,也就是当下递归到的节点下的左子树指向NULL,结束本次左子树递归,返回这个节点的上一个节点,开

【二叉树遍历】二叉树的中序遍历/C++/leedcode/源码-爱代码爱编程

中序遍历二叉树:按照左孩子 -> 根节点 -> 右孩子的顺序遍历二叉树。 1.递归方法 void bst(TreeNode* root){ if(root == nullptr) return; //如果为空则返回 bst(root->right); //遍历左孩子 cout

二叉树的遍历(前序、中序、后序)和查找-爱代码爱编程

文章目录 1、二叉树简介2、二叉树遍历(前序、中序、后序)3、二叉树查找指定结点4、代码实现 1、二叉树简介 树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。 二叉树的子节点分为左节点和右节点。 如果该二叉树的所有叶子节点都在最后一层,并且结点总数=2^n-1 , n为层数,则称为满二叉树。 完全二叉树是由满二叉树而引出

二叉树的前序、中序、后序遍历(附java代码)-爱代码爱编程

前序、中序、后序遍历思想 前序遍历的顺序是根左右,即先遍历根节点,接着遍历左节点,最后遍历右节点;中序遍历的顺序是左根右,即先遍历左节点,接着遍历根节点,最后遍历右节点;后序遍历的顺序是左右根,即先遍历左节点,接着遍历右节点,最后遍历根节点。总结:前序、中序、后序遍历就是看访问根节点的位置。  举例说明  假设一颗如图所示的二叉树,如

数据结构之二叉树的前序遍历、中序遍历、后序遍历、层序遍历_前序遍历二叉树-爱代码爱编程

最近也是在准备笔试,由于没有系统的学过数据结构,所以每次在考到二叉树的遍历的时候都是直接跪,次数多了也就怒了,前些天也是准备论文没时间整这些,现在提交了,算是稍微轻松点了,所以花了半天的时间来学了下二叉树。现在记下来,以便后序查阅。 一、二叉树的遍历概念     1.  二叉树的遍历是指从根结点触发,按照某种次序依次访问二叉树中所有结点,使得每个结点被