链式二叉树的查找,遍历(递归实现)等接口的实现

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

目录

前言:

一:二叉树的建立

(1)本文采用的二叉树表示方法

(2)手动建立一颗二叉树

二:二叉树的遍历

(1)二叉树的三种遍历方式

(2)分治思想

(3)前序遍历

 (4)中序遍历

(5)后序遍历

三:求二叉树的节点和高度(深度)

(1)求二叉树节点

①求二叉树的全部节点

②求二叉树的叶子节点

③求二叉树第k层节点的个数

(2)求二叉树的高度(深度)

四:二叉树的查找


前言:

之前我们初步的讲解了二叉树并且实现了堆这种特殊的二叉树,本次我们将实现链式二叉树的遍历(链式二叉树中非常重要的部分),查找等功能。

附初识二叉树链接:http://t.csdn.cn/pMOia

一:二叉树的建立

(1)本文采用的二叉树表示方法

①每一个节点都是一个结构体。

②每一个节点除了存储数据,还存储了自己孩子节点的地址(结构体指针)。

③如果节点没有孩子就指向空

示意图:

链式二叉树的查找,遍历(递归实现)等接口的实现

代码:

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	//存储左孩子的地址
	struct BinaryTreeNode* left;
	//存储右孩子的地址
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

(2)手动建立一颗二叉树

①调用malloc( )函数申请空间,插入数据。

②将节点依次链接

③因为需要多次申请空间,插入数据,我们把这个部分封装成函数BuyNewNode( )。

代码:

//申请新节点
BTNode* BuyNewNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		printf("malloc error\n");
		exit(-1);
	}

	newnode->data = x;
	newnode->left = newnode->right = NULL;
	
	return newnode;
}


void test1()
{
    //手动建立一个二叉树
	BTNode* nodeA = BuyNewNode('A');
	BTNode* nodeB = BuyNewNode('B');
	BTNode* nodeC = BuyNewNode('C');
	nodeA->left = nodeB;
	nodeA->right = nodeC;
	BTNode* nodeD = BuyNewNode('D');
	BTNode* nodeE = BuyNewNode('E');
	BTNode* nodeF = BuyNewNode('F');
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;
}

这个二叉树的图:

链式二叉树的查找,遍历(递归实现)等接口的实现

二:二叉树的遍历

(1)二叉树的三种遍历方式

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右
子树之前
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中
(间)。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后

(2)分治思想

分治就是分而治之,大概意思就是将一个看似复杂的问题化成一个个简单的小问题,最后解决问题的思想,也是本文的核心。
好比一个学校要统计学生人数,可以让校长一个个去数,也可以让校长告诉年级主任,主任告诉班主任,班主任告诉宿舍长。
链式二叉树的查找,遍历(递归实现)等接口的实现

(3)前序遍历

链式二叉树的查找,遍历(递归实现)等接口的实现

 我们看这颗二叉树,如果要进行前序遍历。

先打印A,然后遍历A左子树。

打印B,遍历B左子树。

打印D,遍历D左子树。

为空,遍历D右子树。

为空,B的左子树遍历结束,遍历B的右子树。

为空,A的左子树遍历结束,遍历A的右子树。

……………………

②我们不难发现,如果要前序遍历整棵树

可以转化为先访问A后前序遍历A的左子树和右子树

前序遍历A的左子树可以转化为先访问B后前序遍历B的左子树和右子树

前序遍历B的右子树又可以转化为先访问D后前序遍历D的左子树和右子树,这样可以把一个较大的问题转化为一个个极小的问题。

代码:

//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("空  ");
		return;
	}

	//打印
	printf("%c  ", root->data);
	//左子树
	PreOrder(root->left);
	//右子树
	PreOrder(root->right);
}

大家遇到这种递归不理解的话可以画一下递归展开图

链式二叉树的查找,遍历(递归实现)等接口的实现

 (4)中序遍历

链式二叉树的查找,遍历(递归实现)等接口的实现

如果要对这颗二叉树进行中序遍历。

先遍历A左子树。

遍历B左子树。

遍历D左子树。

空,打印D,遍历D右子树。

空,打印B,遍历B右子树。

空,打印A,遍历A右子树。

………………

②中序遍历整颗树,

可以转化为中序遍历A的左子树后访问A,然后中序遍历右子树

中序遍历A的左子树可以转化为中序遍历B的左子树后访问B,然后中序遍历右子树

中序遍历B的右子树又可以转化为中序遍历D的左子树后访问D,然后中序遍历右子树,这样可以把一个较大的问题转化为一个个极小的问题。

代码:

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("空  ");
		return;
	}

	//左树
	InOrder(root->left);
	//打印
	printf("%c  ", root->data);
	//右树
	InOrder(root->right);
}

递归展开图:

链式二叉树的查找,遍历(递归实现)等接口的实现

(5)后序遍历

链式二叉树的查找,遍历(递归实现)等接口的实现

如果要对这颗二叉树进行后序遍历。

先遍历A左子树。

遍历B左子树。

遍历D左子树。

空,遍历D右子树。

空,打印D,遍历B右子树。

空,打印B,遍历A右子树。

……………………

②后序遍历整颗树,

可以转化为后序遍历A的左子树和右子树后访问A

后序遍历A的左子树可以转化为后序遍历B的左子树和右子树后访问B

后序遍历B的右子树又可以转化为后序遍历D的左子树和右子树后访问D,这样可以把一个较大的问题转化为一个个极小的问题。

代码:

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("空  ");
		return;
	}
	//左树
	PostOrder(root->left);
	//右树
	PostOrder(root->right);
	//打印
	printf("%c  ", root->data);
}

递归展开图:

链式二叉树的查找,遍历(递归实现)等接口的实现

三:求二叉树的节点和高度(深度)

(1)求二叉树节点

①求二叉树的全部节点

链式二叉树的查找,遍历(递归实现)等接口的实现

思路:

①只有节点地址不为空就算一个节点。

②求整颗树节点,可以转化为A的左子树节点数加A的右子树节点数加1

A的左子树节点数可以转化为B的左子树节点数加B的右子树节点数加1

B的左子树节点数可以转化为D的左子树节点数加D的右子树节点数加1

D的左右子树都是空,B的左子树节点数为1

………………………………

代码:

//求树的节点数
int BinaryTreeSize(BTNode* root)
{
	/*if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;*/
	//更加简洁的写法
	return root == NULL ? 0 :
		BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

递归展开图:

链式二叉树的查找,遍历(递归实现)等接口的实现

②求二叉树的叶子节点

链式二叉树的查找,遍历(递归实现)等接口的实现

思路:

左右孩子都为空的节点算作一个叶子节点

②求整颗树的叶子节点,可以转化为求A的左子树叶子节点和A的右子树叶子节点

A的左子树叶子节点可以转化为求B的左子树叶子节点加B的右子树叶子节点

D的左右孩子都为空,B的左子树叶子节点为1。

…………………………

代码:

//求叶子节点
int BinaryLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	if ((root->left == NULL) && (root->right == NULL))
	{
		return 1;
	}

	return BinaryLeafSize(root->left) + BinaryLeafSize(root->right);
}

递归展开图:

链式二叉树的查找,遍历(递归实现)等接口的实现

③求二叉树第k层节点的个数

链式二叉树的查找,遍历(递归实现)等接口的实现

思路:

假设k为3。

一颗树第一层节点数为1

空节点代表节点数为0

③求整颗树第3层的节点数,可以转化为求A的左子树以及右子树的第2层节点数之和

A的左子树第2层节点数,可以转化为求B的左子树以及右子树的第1层节点数之和

B左子树不为空,层数为1,节点数为1

B的右子树为空,节点数为0

………………………………

代码:

//求第k层节点的个数
int BinaryTreeLevelKSize(BTNode* root,int k)
{
	//非法输入直接报错
	assert(k >= 1);

	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLevelKSize(root->left, k - 1)
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

递归展开图:

链式二叉树的查找,遍历(递归实现)等接口的实现

(2)求二叉树的高度(深度)

链式二叉树的查找,遍历(递归实现)等接口的实现

思路:

空树高度为0

②一颗树根节点左右孩子均为空,高度为1

③一颗树最终的高度为左右子树中深度较大的一方加1

④求整颗树的高度可以转化为A的左右子树中高度较大的一方加1

A的左子树高度可以转化为B的左右子树中高度较大的一方加1

B的左子树高度可以转化为D的左右子树中高度较大的一方加1

D的左右孩子均为空,B的左子树高度为1

B的右子树为空树,B的右子树高度为0

取大的一方加1,A的左子树高度为2

代码:

//求二叉树的高度(深度)
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return max(BinaryTreeDepth(root->left), BinaryTreeDepth(root->right)) + 1;
}

递归展开图:

链式二叉树的查找,遍历(递归实现)等接口的实现

四:二叉树的查找

功能:输入要查找的数据x,返回节点的地址

链式二叉树的查找,遍历(递归实现)等接口的实现

思路:

假设要查找E

①如果找到返回节点地址,没找到返回空

②递归调用的时候要根据返回值来判断是否找到

如果不为空代表找到了,不需要继续查找,返回节点地址

③在整颗树查找E,先看根部是否为E,不是在A的左右子树中查找。

先看A的左子树根部是否为E,不是在B的左右子树中查找。

先看B的左子树根部是否为E,不是在D的左右子树中查找。

D的左右子树为空,返回空。

B的右子树为空,返回空。

A的左子树查找完毕,没找到,查找A的右子树。

先看A的右子树根部是否为E,不是在C的左右子树查找。

………………………………

代码:

//查找值为x的节点
BTNode* BianrtTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->data == x)
	{
		return root;
	}

	BTNode* leftRet = BianrtTreeFind(root->left,x);
	if (leftRet != NULL)
	{
		return leftRet;
	}

	BTNode* rightRet = BianrtTreeFind(root->right,x);
	if (rightRet != NULL)
	{
		return rightRet;
	}

	return NULL;
}

递归展开图(查找E):

链式二叉树的查找,遍历(递归实现)等接口的实现文章来源地址https://www.toymoban.com/news/detail-424878.html

到了这里,关于链式二叉树的查找,遍历(递归实现)等接口的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 用java实现二叉树的后序遍历(递归和迭代)

    目录 1.题目内容 2.用递归实现后序遍历 2.1解题思路 2.2代码 3.用迭代实现后序遍历 3.1解题思路 3.2代码 给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。 示例 1: 输入:root = [1,null,2,3] 输出:[3,2,1] 示例 2: 输入:root = [] 输出:[] 示例 3: 输入:root = [1] 输出:[1]

    2024年02月08日
    浏览(58)
  • 【二叉树part01】| 二叉树的递归遍历、二叉树的迭代遍历、二叉树的统一迭代遍历

    目录 ✿二叉树的递归遍历❀ ☞LeetCode144.前序遍历 ☞LeetCode145.二叉树的后序遍历  ☞LeetCode94.二叉树的中序遍历  ✿二叉树的迭代遍历❀  ☞LeetCode144.前序遍历  ☞LeetCode145.二叉树的后序遍历   ☞LeetCode94.二叉树的中序遍历  ✿二叉树的统一迭代遍历❀   ☞LeetCode144.前序遍

    2024年02月09日
    浏览(38)
  • Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 二叉树的说明         1.1 二叉树的实现         2.0 二叉树的优先遍历说明         3.0 用递归方式实现二叉树遍历         3.1 用递归方式实现遍历 - 前序遍历         3.2 用递归

    2024年02月05日
    浏览(53)
  • 二叉树的链式结构 - C语言(含有大量递归)

    目录: 🍔前言 🍔二叉树链式结构的实现 🍟基本构架 😍代码: 🍔二叉树的遍历 🍟前序遍历 🍟中序遍历 🍟后序遍历 🍟层序遍历 🔴层序遍历的思路及代码 🍔 构建二叉树  😍代码: 🍔二叉树销毁 😍代码:   🍔二叉树节点个数 😍代码: 🍔二叉树叶子节点个数

    2024年02月08日
    浏览(38)
  • 数据结构——二叉树的创建与遍历(链式存储结构)

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

    2024年02月05日
    浏览(51)
  • 【算法与数据结构】二叉树的三种遍历代码实现(下)—— 非递归方式实现(大量图解)

     上篇: 【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解_Hacynn的博客-CSDN博客 https://blog.csdn.net/zzzzzhxxx/article/details/133609612?spm=1001.2014.3001.5502 目录 前言 1、先序遍历 1.1、详细图解描述 1.2、先序遍历非递归代码实现  2、中序遍历 2.1、详细图解描

    2024年02月08日
    浏览(39)
  • 二叉树的遍历(递归法)

    递归的三要素: ①确定递归函数的参数和返回值 ②确定终止条件 ③确定单层递归的逻辑 以前序遍历为例: 1、确定递归函数的参数和返回值: 参数中需要传入list来存放节点的数值,除了这一点就不需要再处理什么数据了也不需要有返回值,因此递归函数的返回类型就是v

    2024年01月17日
    浏览(74)
  • 二叉树的递归遍历与迭代遍历(图示)

    本文将讲述二叉树递归与迭代的相关知识。 🕺作者: 迷茫的启明星 专栏:【数据结构从0到1】 相关文章:《数据结构二叉树的链式存储讲解及前中后序遍历和层次遍历》 😘欢迎关注:👍点赞🙌收藏✍️留言 🏇 码字不易,你的👍点赞🙌收藏❤️关注对我真的很重要,有

    2024年02月04日
    浏览(48)
  • 二叉树的非递归遍历算法

    二叉树的遍历是指访问二叉树的每个结点,且每个结点仅被访问一次。二叉树的遍历可按二叉树的构成以及访问结点的顺序分为4种方式:先序遍历、中序遍历、后序遍历和层次遍历。请至少给出其中一种遍历方式的非递归算法的思路和代码,并举例演示算法的执行过程。 算

    2023年04月24日
    浏览(41)
  • 【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解

      本篇博客 (上篇) 先带大家学习 递归方式 进行三种遍历, 而在后续的 (下篇) 中将为大家详细讲解非递归的三种遍历方式。 目录 1、二叉树 2、二叉树的递归遍历 2.1、先序遍历 2.2、中序遍历 2.3、后序遍历  二叉树(Binary tree)是树形结构的一个重要类型。许多实际问

    2024年02月08日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包