C语言二叉树的遍历示例介绍

在本算法中先利用先序遍历创建了树,利用了递归的算法使得算法简单,操作容易,本来无printf("%c的左/右子树:", ch);的语句,但由于计算机需要输入空格字符来判断左右子树,为了减少人为输入的失误,特地加入这条语句,以此保证准确率。

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW 3

typedef int Status;
typedef int Boolean;
typedef char TElemType;

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

//创建二叉树函数

Status CreateBiTree(BiTree &T){
	TElemType ch;
	scanf("%c", &ch);
	getchar();
	if(ch == ' '){	T = NULL;}
	else {
		if( !(T=(BiTree)malloc(sizeof(BiTNode))))(exit(OVERFLOW));
		T->data = ch;
		printf("%c的左子树:", ch);
		CreateBiTree(T->lchild);
		printf("%c的右子树:", ch);
		CreateBiTree(T->rchild);	}
	return OK;
}

//先序遍历函数
Status PreOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){
	if(T){
		if(Visit(T->data)){
			if(PreOrderTraverse(T->lchild, Visit)){
				if(PreOrderTraverse(T->rchild, Visit)){
					return OK;
               }
            }
         }
		return ERROR;
    }
	else {return OK;}
}

//中序遍历函数
Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){
	if(T){
		if(PreOrderTraverse(T->lchild, Visit) ){
			if(Visit(T->data)){
				if(PreOrderTraverse(T->rchild, Visit) ){
					return OK;
           }
	   }
   }
		return ERROR;
        }
	else {
		return OK;
        }
	}

//后序遍历函数
Status PosOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){
	if(T){
		if(PreOrderTraverse(T->lchild, Visit) ){
			if(PreOrderTraverse(T->rchild, Visit) ){
				if(Visit(T->data)){return OK;
}
	}
}
		return ERROR;}
	else {return OK;
}
}

//输出二叉树函数
Status PrintElement(TElemType e){
	printf("%c",e);
	return OK;
}

//主函数
int main(){
	BiTree T;
	printf("输入根结点:");
	CreateBiTree(T);
	printf("先序遍历:\n");
	PreOrderTraverse(T, PrintElement);
	printf("\n");
	printf("中序遍历:\n");
	InOrderTraverse(T, PrintElement);
	printf("\n");
	printf("后序遍历:\n");
	PosOrderTraverse(T, PrintElement);
	return 0;
}

遍历操作有四种,其不同在于对根结点的访问顺序不同。在先序遍历中,首先访问根结点,然后递归地做左子树的先序遍历,然后是右子树的递归先序遍历。 在中序遍历中,递归地对左子树进行中序遍历,访问根结点,最后递归中序遍历右子树。在后序遍历中,递归地对左子树和右子树进行后序遍历,然后访问根结点。先序,中序,后序遍历就是对于根节点的访问顺序。

但无论哪种遍历方式,递归的方法是最简便,最直接,最简单的算法。

运行截图:

到此这篇关于C语言二叉树的遍历示例介绍的文章就介绍到这了,更多相关C语言二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言二叉树的三种遍历方式的实现及原理

    二叉树遍历分为三种:前序.中序.后序,其中序遍历最为重要.为啥叫这个名字?是根据根节点的顺序命名的. 比如上图正常的一个满节点,A:根节点.B:左节点.C:右节点,前序顺序是ABC(根节点排最先,然后同级先左后右):中序顺序是BAC(先左后根最后右):后序顺序是BCA(先左后右最后根). 比如上图二叉树遍历结果 前序遍历:ABCDEFGHK 中序遍历:BDCAEHGKF 后序遍历:DCBHKGFEA 分析中序遍历如下图,中序比较重要(java很多树排序是基于中序,后面讲解分析) 下面介绍一下,二

  • C语言平衡二叉树详解

    目录 调整措施: 一.单旋转 二.双旋转 AVL树的删除操作: 删除分为以下几种情况: 1.要删除的节点是当前根节点T. 2.要删除的节点元素值小于当前根节点T值,在左子树中进行删除. 3.要删除的节点元素值大于当前根节点T值,在右子树中进行删除. 总结 平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树.这个方案很好的解决了二叉查找树退化成链表的

  • C语言递归实现线索二叉树

    本文实例为大家分享了C语言递归实现线索二叉树的具体代码,供大家参考,具体内容如下 描述:将二叉树中结点的空左孩子指针域指向前驱结点,将空的右孩子指针域指向后继结点. code: #pragma warning(disable:4996) #include<stdio.h> #include<stdlib.h> typedef struct TreeNode { char data; struct TreeNode *lchild, *rchild; int ltag, rtag;

  • C语言非递归后序遍历二叉树

    本文实例为大家分享了C语言非递归后序遍历二叉树的具体代码,供大家参考,具体内容如下 法一:实现思路:一个栈 先按 根->右子树->左子树的顺序访问二叉树.访问时不输出.另一个栈存入前一个栈只进栈的结点. 最后输出后一个栈的结点数据. #include<stdio.h> #include<stdlib.h> typedef struct TreeNode{ char element; struct TreeNode *left,*right; }Tree,*BTree;

  • C语言二叉树的遍历示例介绍

    在本算法中先利用先序遍历创建了树,利用了递归的算法使得算法简单,操作容易,本来无printf("%c的左/右子树:", ch);的语句,但由于计算机需要输入空格字符来判断左右子树,为了减少人为输入的失误,特地加入这条语句,以此保证准确率. #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW 3 typedef int Status; typedef

  • C语言二叉树层序遍历

    实现下面图中的二叉树层序遍历 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <unistd.h> typedef struct node { char data; struct node *lchild; struct node *rchild; }NODE, *PNODE; typedef struct qnode { PNODE pnode; struct qno

  • C语言实现二叉树层次遍历介绍

    目录 什么是层次遍历? 那我们如何来实现这个算法呢? 主体代码: 总结 什么是层次遍历? 对于一颗二叉树来说,从根节点开始,按从上到下.从左到右的顺序访问每一个结点. 注:每一个结点有且访问一次. 那我们如何来实现这个算法呢? 实现原理: 对于二叉树来说,它是一个递归的定义,我们要实现层次遍历必然要满足从上到下.从左到右这个要求,从根结点出发,我们可以将所有意义上的根结点都存储在队列之中,那我们可以使用队列先进先出的特点来实现要求的遍历. 这里我们需要引用队列来实现. 主体代码: BiTree

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • C语言数据结构系列篇二叉树的遍历

    目录 前言: Ⅰ. 定义二叉树 0x00二叉树的概念(回顾) 0x00定义二叉树 0x01 手动创建二叉树 Ⅱ. 二叉树的遍历 0x00关于遍历 0x01二叉树前序遍历 0x02二叉树中序遍历 0x03二叉树后序遍历 0x04层序遍历 前言: 学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建一颗简单的二叉树,用来方便大家学习.等二叉树结构了解的差不多后,后期我们会带大家研究二叉树地真正的创建方式.

  • C语言详解实现链式二叉树的遍历与相关接口

    目录 前言 一.二叉树的链式结构 二.二叉树的遍历方式 1.1 遍历方式的规则 1.2 前序遍历 1.3 中序遍历 1.4 后序遍历 1.5 层序遍历 三.二叉树的相关接口实现 3.1 二叉树节点个数 3.2 二叉树叶子节点个数 3.3 二叉树第 k 层节点个数 3.4 二叉树的深度(高度) 3.5 二叉树查找值为 x 的节点 3.6 总结 & 注意 四.二叉树的创建和销毁 4.1 通过前序遍历的字符串来构建二叉树 4.2 二叉树销毁 4.3 判断二叉树是否是完全二叉树 前言 二叉树的顺序结构就

  • C语言单链表遍历与求和示例解读

    目录 单链表的遍历 单链表的求和 单链表的遍历 描述: 牛牛从键盘输入一个长度为 n 的数组,问你能否用这个数组组成一个链表,并顺序输出链表每个节点的值. 输入描述: 第一行输入一个正整数 n ,表示数组的长度 第二行输入n个数据 输出描述: 制作一个链表然后输出这个链表的值 输入: 4 5 4 2 1 输出: 5 4 2 1 #include<stdio.h> #include<stdlib.h> typedef int DataType; typedef struct link

  • C语言数据结构之线索二叉树及其遍历

    C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,¥不能直接得到节点在遍历中的前驱和后继¥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继

  • go语言代码生成器code generator使用示例介绍

    目录 代码生成器介绍 code-generator 示例 代码生成tag 全局tag 局部tag 补充 代码生成器介绍 client-go为每种k8s内置资源提供了对应的clientset和informer.那么我们要监听和操作自定义资源对象,应该如何做呢? 方式一:使用client-go提供的dynamicClient来操作自定义资源对象,当然由于dynamicClient是基于RESTClient实现的,所以我们可以使用RESTClient来达到同样的目的. 方式二: 使用conde-gen

随机推荐