数据结构——二叉树的创建与遍历(链式存储结构)

这篇具有很好参考价值的文章主要介绍了数据结构——二叉树的创建与遍历(链式存储结构)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二叉树(binary tree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树。以下是对链式存储结构的二叉树的创建与先序、中序、后序遍历操作:

定义二叉树节点

每个节点由三个部分组成:
数据部分
左孩子节点
右孩子节点

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

主函数

声明初始节点时,是BiTree bt,此时bt是节点指针,如果写的是BiTNode bt,则为节点元素。为了传地址操作方便,我们使用声明节点地址的形式。

int main(){
	BiTree bt;//指针 
	initial(&bt);
	cout<<"先序创建树(输入#停止生成节点):\n"; 
	createTree(&bt);
	cout<<"先序遍历:\n"; 
	preOrder(bt);
	cout<<"\n中序遍历:\n"; 
	inOrder(bt);
	cout<<"\n后序遍历:\n";
	postOrder(bt); 
	return 0;
} 

初始化

我们在主函数里以initial(&bt)的形式调用bt指针,即将指针地址传入初始化函数里。参数里写的是(BiTree bt)表示bt是指向根节点这个节点指针的指针。
此时
bt指的是根节点指针,(BiTree)malloc(sizeof(BiTNode))为该节点分配空间。
初始时均无左右孩子,所以设为NULL。

Status initial(BiTree *bt){//指针的指针 
	*bt = (BiTree)malloc(sizeof(BiTNode));
	(*bt)->lchild = NULL;
	(*bt)->rchild = NULL;
}

创建二叉树

依然是以指针的指针的形式将节点指针传入函数里
我们设置输入“#”为输入结束。
当输入的元素不是“#”时,为节点指针开辟空间后,将元素赋给该节点的data。
然后递推式创建左右孩子。

Status createTree(BiTree *bt){
	ElemType c;
	c = getchar();
	if(c=='#'){
		*bt = NULL;
	}else{
		*bt = (BiTree)malloc(sizeof(BiTNode));
		(*bt)->data = c;
		createTree(&(*bt)->lchild);
		createTree(&(*bt)->rchild);
	}
}

值得注意的是:因为我们使用的是“指针的指针”,所以递推式将创建其左右孩子时,记得是将其左右孩子的地址传入createTree函数里
(即:&(*bt)->child的形式)

关于先序、中序和后序遍历

先序遍历最容易理解:从根节点开始输出,一直向左遍历输出,到尽头后再找到该节点兄弟右节点输出,然后再去到父亲节点的兄弟右节点输出……以此类推。
中序遍历:从左子树的最左边最底层的左孩子节点开始输出,然后输出其父亲节点,再输出其兄弟右节点,然后输出其父亲节点的父亲节点……以此类推。
后序遍历:从左子树的最左边最底层的左孩子节点开始输出,然后输出其兄弟右节点,然后输出其父亲节点,然后输出其父亲节点的熊迪右节点……以此类推。

示例1

我们来创建一个如下图的树:
【问题描述】完成二叉树的建立与层次遍历,具体要求包括:(1)采用链式存储结构,数据结构,数据结构,算法,c++,c语言

【问题描述】完成二叉树的建立与层次遍历,具体要求包括:(1)采用链式存储结构,数据结构,数据结构,算法,c++,c语言

示例2

【问题描述】完成二叉树的建立与层次遍历,具体要求包括:(1)采用链式存储结构,数据结构,数据结构,算法,c++,c语言
【问题描述】完成二叉树的建立与层次遍历,具体要求包括:(1)采用链式存储结构,数据结构,数据结构,算法,c++,c语言

示例3

【问题描述】完成二叉树的建立与层次遍历,具体要求包括:(1)采用链式存储结构,数据结构,数据结构,算法,c++,c语言
【问题描述】完成二叉树的建立与层次遍历,具体要求包括:(1)采用链式存储结构,数据结构,数据结构,算法,c++,c语言
【问题描述】完成二叉树的建立与层次遍历,具体要求包括:(1)采用链式存储结构,数据结构,数据结构,算法,c++,c语言
简单粗暴地画法就是遵守这个规律:
【问题描述】完成二叉树的建立与层次遍历,具体要求包括:(1)采用链式存储结构,数据结构,数据结构,算法,c++,c语言

先序、中序、后序遍历代码实现:

void preOrder(BiTree bt){//指针形参 
	if(bt!=NULL){
		cout<<bt->data<<" ";
		preOrder(bt->lchild);
		preOrder(bt->rchild);
	}
}

void inOrder(BiTree bt){//指针形参 
	if(bt!=NULL){
		inOrder(bt->lchild);
		cout<<bt->data<<" ";
		inOrder(bt->rchild);
	}
}

void postOrder(BiTree bt){//指针形参 
	if(bt!=NULL){
		postOrder(bt->lchild);
		postOrder(bt->rchild);
		cout<<bt->data<<" ";
	}

}

源代码(编程风格参考严蔚敏版《数据结构》)

#include<iostream>
#include<stdio.h>
#include<malloc.h>
using namespace std;
#define MAXSIZE 5
#define ElemType char
#define Status int//表示状态 
#define OK 1
#define ERROR 0
#define STOP 0
#define OVERFLOW 0

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

Status initial(BiTree *bt){//指针的指针 
	*bt = (BiTree)malloc(sizeof(BiTNode));
	(*bt)->lchild = NULL;
	(*bt)->rchild = NULL;
}

Status createTree(BiTree *bt){
	ElemType c;
	c = getchar();
	if(c=='#'){
		*bt = NULL;
	}else{
		*bt = (BiTree)malloc(sizeof(BiTNode));
		(*bt)->data = c;
		createTree(&(*bt)->lchild);
		createTree(&(*bt)->rchild);
	}
}

void preOrder(BiTree bt){//指针形参 
	if(bt!=NULL){
		cout<<bt->data<<" ";
		preOrder(bt->lchild);
		preOrder(bt->rchild);
	}
}

void inOrder(BiTree bt){//指针形参 
	if(bt!=NULL){
		inOrder(bt->lchild);
		cout<<bt->data<<" ";
		inOrder(bt->rchild);
	}
}

void postOrder(BiTree bt){//指针形参 
	if(bt!=NULL){
		postOrder(bt->lchild);
		postOrder(bt->rchild);
		cout<<bt->data<<" ";
	}

}
int main(){
	BiTree bt;//指针 
	initial(&bt);
	cout<<"先序创建树(输入#停止生成节点):\n"; 
	createTree(&bt);
	cout<<"先序遍历:\n"; 
	preOrder(bt);
	cout<<"\n中序遍历:\n"; 
	inOrder(bt);
	cout<<"\n后序遍历:\n";
	postOrder(bt); 
	return 0;
} 

敬请批评指正!文章来源地址https://www.toymoban.com/news/detail-753254.html

到了这里,关于数据结构——二叉树的创建与遍历(链式存储结构)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构 | 二叉树的各种遍历

    我们本章来实现二叉树的这些功能 Tree.h 我们先来几个简单的 直接手动个创建即可,很简单~~ 这里也是很简单,也可以看做下图这样遍历,或者画一下递归展开图 我们这里看一下递归展开图 为空就返回0 不是空,是叶子,返回1 不是空,也不是叶子,就递归左子树和右子树

    2024年02月04日
    浏览(38)
  • go数据结构(二叉树的遍历)

      用数组来存储二叉树如何遍历的呢? 如果父节点的数组下表是i,那么它的左孩子就是i * 2 + 1,右孩子就是 i * 2 + 2。  二叉树的遍历方式: 二叉树有 三种基本遍历方式 ,分别是 前序遍历、中序遍历和后序遍历 。遍历的原理是从根节点开始,按照特定方式递归遍历左子树

    2023年04月15日
    浏览(37)
  • 【数据结构】二叉树的层序遍历

    当我们面对一个树结构时,常常需要对其进行遍历以获取其中的节点信息。其中一种常用的遍历方式是层序遍历,也称为广度优先搜索(BFS)。本篇博客将详细介绍层序遍历的原理和实现方法。 层序遍历以树的根节点开始,按照从上到下、从左到右的顺序逐层遍历树中的节点

    2024年02月03日
    浏览(43)
  • 数据结构——二叉树的遍历与应用

    目录 一.前言 二. 二叉树链式结构的实现 2.1 前置说明 2.2 二叉树的遍历 2.2.1 前序、中序以及后序遍历 前序遍历: 中序遍历递归图: 后序遍历: 2.3节点个数 2.4叶子节点个数 2.5第K层的节点个数 2.6 二叉树查找值为x的节点 2.7 二叉树的销毁 三.结语   大家好久不见,放寒假了咱

    2024年01月19日
    浏览(46)
  • 【数据结构】二叉树的三种遍历

    目录 一、数据结构 二、二叉树 三、如何遍历二叉树 数据结构是计算机科学中用于组织和存储数据的方式。它定义了数据元素之间的关系以及对数据元素的操作。常见的数据结构包括数组、链表、栈、队列、树、图等。 数组是一种线性数据结构,它使用连续的内存空间存储

    2024年02月21日
    浏览(42)
  • 数据结构与算法-二叉树的遍历

    🌞 “少年没有乌托邦,心向远方自明朗!” 二叉树的遍历是按照一定次序访问二叉树中的所有结点,且每个结点仅被访问一次的过程。遍历线性结构是容易解决的,而二叉树的结构是非线性结构,需要寻找规律,使二叉树的结点排列在一个线性队列上,便于遍历。 由二叉树

    2024年02月08日
    浏览(44)
  • Java数据结构——二叉树的遍历

     作者:敲代码の流川枫 博客主页:流川枫的博客 专栏:和我一起学java 语录:Stay hungry stay foolish 工欲善其事必先利其器,给大家介绍一款超牛的斩获大厂offer利器——牛客网 点击注册和我一起刷题 文章目录 1.创建二叉树 2.二叉树的三种遍历方式 3.代码实现遍历 前序遍历

    2024年01月22日
    浏览(45)
  • 【数据结构】二叉树的前序遍历(七)

    题目详情: 给你二叉树的根节点 root ,返回它节点值的  前序   遍历; 我们先来看几个示例: 输入:root = [ 1,null,2,3 ] 输出:[ 1,2,3 ]  示例2: 输入:root = [ 1,2 ] 输出:[ 1,2 ] 示例三: 输入:root = [  ] 输出:[  ] 提示: 树中结点数目在范围【0,100】内 -100 = Nod

    2024年02月07日
    浏览(43)
  • 【C语言 数据结构】二叉树的遍历

    所谓先序遍历二叉树,指的是从根结点出发,按照以下步骤访问二叉树的每个结点: 访问当前结点; 进入当前结点的左子树,以同样的步骤遍历左子树中的结点; 遍历完当前结点的左子树后,再进入它的右子树,以同样的步骤遍历右子树中的结点; 先序遍历这棵二叉树的过

    2024年02月04日
    浏览(42)
  • 数据结构——二叉树的遍历【前序、中序、后序】

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 、C语言系列函数实现 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可

    2024年03月15日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包