二叉树(上)——“数据结构与算法”

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

各位CSDN的uu们好呀,好久没有更新我的数据结构与算法专栏啦,今天,小雅兰继续来更新二叉树的内容,下面,让我们进入链式二叉树的世界吧!!!


二叉树链式结构的实现 


二叉树链式结构的实现

普通的二叉树的增删查改是没有价值的!!!

只有搜索二叉树的增删查改才有价值。

那么,为什么要学习普通二叉树,而不是一上来就学搜索二叉树呢?

因为,一上来就学习搜索二叉树实在是太难了!!!

而且,学习普通二叉树,主要是学习它的控制结构(递归),为后续学习打基础。

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

 二叉树是:

1. 空树

2. 非空:根节点,根节点的左子树、根节点的右子树组成的。

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

 从概念中可以看出,二叉树定义是递归式的。


二叉树的遍历

前序、中序以及后序遍历

学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉 树中的节点进行相应的操作,并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历 是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

按照规则,二叉树的遍历有:

前序/中序/后序的递归结构遍历:

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

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

前序

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

1  2  3  4  5  6 

中序

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

3  2  1  5  4  6 

后序

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

 3  2  5  6  4  1

 既然已经清楚了前序中序后序的物理过程,下面,就可以写代码啦!!!

前序

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

 二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树  

中序

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

 二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

后序

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

二叉树结点个数

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

不能这么写!!!

因为这是递归调用,不是循环,在循环里面就可以不断++size,就可以

但是这是在递归里面,在不同的栈帧里面,每个栈帧里面都有一个size,这样显然有问题

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

这样写也不行!!!

这个static定义的size就不在栈帧里面了,而是在静态区里面。 

那么,该如何来验证这个问题呢?

//二叉树结点个数
void BTreeSize(BTNode* root)
{
	static int size = 0;
	printf("%p\n", &size);
	if (root == NULL)
	{
		return;
	}
	else
	{
		++size;
	}
	BTreeSize(root->left);
	BTreeSize(root->right);
}

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

会发现:每次打印出的size的地址都一样!!! 

//二叉树结点个数
void BTreeSize(BTNode* root)
{
	static int size = 0;
	printf("%p,%d\n", &size,size);
	if (root == NULL)
	{
		return;
	}
	else
	{
		++size;
	}
	BTreeSize(root->left);
	BTreeSize(root->right);
}

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

会发现:并不是每次都把size置为0,size是发生变化的!!! 

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

这样写表面上确确实实行得通,但是只要细细思索,会发现有大坑!!!

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

为什么结果会这样呢?

因为:size没办法置0!!!

那么,正确的写法该怎么写呢???

把size定义成全局变量!!!

//二叉树结点个数
int size = 0;//全局变量
void BTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	else
	{
		++size;
	}
	BTreeSize(root->left);
	BTreeSize(root->right);
}
int main()
{
    BTreeSize(root);
	printf("BTreeSize:%d\n", size);

	size = 0;
	BTreeSize(root);
	printf("BTreeSize:%d\n", size);

	size = 0;
	BTreeSize(root);
	printf("BTreeSize:%d\n", size);
	return 0;
}

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

这个方法是遍历记数法 

求解这个问题还有另一种方法。

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

可以采用分治的方法!!!

//二叉树结点个数
int BTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		return BTreeSize(root->left) + BTreeSize(root->right) + 1;
	}
}

另一种写法:

//二叉树结点个数
int BTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树

求叶子结点的个数

//求叶子结点的个数
int BTreeleafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BTreeleafSize(root->left) + BTreeleafSize(root->right);
}

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树


目前整个的源代码:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    node->data = x;
    node->left = NULL;
    node->right = NULL;
    return node;
}

BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);

    node1->left = node2;
    node1->right = node4;
    node2->left = node3;
    node4->left = node5;
    node4->right = node6;
    return node1;
}

//前序
void PrevOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%d ", root->data);
    PrevOrder(root->left);
    PrevOrder(root->right);
}

//中序
void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}

//后序
void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->data);
}

 

二叉树结点个数
//int size = 0;//全局变量
//int BTreeSize(BTNode* root)
//{
//    if (root == NULL)
//    {
//        return;
//    }
//    else
//    {
//        ++size;
//    }
//    BTreeSize(root->left);
//    BTreeSize(root->right);
//}


二叉树结点个数
//int BTreeSize(BTNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    else
//    {
//        return BTreeSize(root->left) + BTreeSize(root->right) + 1;
//    }
//}


//二叉树结点个数
int BTreeSize(BTNode* root)
{
    return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}


//求叶子结点的个数
int BTreeleafSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->left == NULL && root->right == NULL)
    {
        return 1;
    }
    return BTreeleafSize(root->left) + BTreeleafSize(root->right);
}

int main()
{
    BTNode* root = CreatBinaryTree();
    PrevOrder(root);
    printf("\n");

    InOrder(root);
    printf("\n");

    PostOrder(root);
    printf("\n");

    /*BTreeSize(root);
    printf("BTreeSize:%d\n", size);

    size = 0;
    BTreeSize(root);
    printf("BTreeSize:%d\n", size);

    size = 0;
    BTreeSize(root);
    printf("BTreeSize:%d\n", size);*/

    printf("BTreeSize:%d\n",BTreeSize(root));

    return 0;
}


好啦,这只是二叉树的刚开始的部分知识点,接下来,小雅兰会继续更新数据结构与算法专栏啦,继续加油!!!

二叉树(上)——“数据结构与算法”,数据结构与算法,数据结构,算法,b树,随机森林,霍夫曼树文章来源地址https://www.toymoban.com/news/detail-552999.html

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

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

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

相关文章

  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(63)
  • 探索树形数据结构,通识树、森林与二叉树的基础知识(专有名词),进一步利用顺序表和链表表示、遍历和线索树形结构

      结点之间有分支,具有层次关系 树的定义 : 树 (tree)是n(n≥0)个有限集。 若n = 0,则称为空树; 若n 0,则它满足如下两个条件: 有且仅有一个特定的称为根(Root)的结点; 其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,.....,Tm,其中每一个集合本身又是一棵树,并称为根的

    2024年02月01日
    浏览(53)
  • 【数据结构与算法】—— 二叉树

    目录 一、树 1、初识树 2、树的一些概念 3、树的表示形式 二、二叉树 1、初识二叉树 2、两种特殊的二叉树 3、二叉树的性质  4、二叉树的遍历 5、实现一棵二叉树  6、二叉树题目(没代码的后面会给补上) (1)根节点没有前驱。 (2)子树的根节点只有一个前驱,可以有

    2024年04月09日
    浏览(48)
  • 数据结构与算法-二叉树

            在计算机科学中,数据结构是组织和存储数据的基础框架,而算法则是处理这些数据的核心逻辑。在这众多的数据结构中,二叉树因其独特的层级结构、高效的搜索和插入操作,成为广泛应用的一种非线性数据结构。本文将深入探讨二叉树的定义、种类、操作方法

    2024年03月10日
    浏览(59)
  • 二叉树(上)——“数据结构与算法”

    各位CSDN的uu们好呀,好久没有更新我的数据结构与算法专栏啦,今天,小雅兰继续来更新二叉树的内容,下面,让我们进入链式二叉树的世界吧!!! 二叉树链式结构的实现  二叉树链式结构的实现 普通的二叉树的增删查改是没有价值的!!! 只有搜索二叉树的增删查改才

    2024年02月15日
    浏览(44)
  • 【数据结构】树与二叉树(十三):递归复制二叉树(算法CopyTree)

      二叉树是一种常见的树状数据结构,它由结点的有限集合组成。一个二叉树要么是 空集 ,被称为 空二叉树 ,要么由一个根结点和两棵不相交的子树组成,分别称为 左子树 和 右子树 。每个结点最多有两个子结点,分别称为左子结点和右子结点。 引理5.1:二叉树中层数

    2024年02月01日
    浏览(40)
  • 数据结构与算法之《二叉树》详解

    文章目录 一、树的概念及结构 二、二叉树的概念及结构 2、1 二叉树的概念 2、2 二叉树的特点 2、3 二叉树的结构(图片) 2、4 特殊的二叉树 三、二叉树的代码及思路实现 3、1 二叉树的存储结构 3、1、1 二叉树的顺序存储结构 3、1、2 二叉树的链式存储结构 3、2 二叉树链式

    2024年02月01日
    浏览(45)
  • 【数据结构与算法】树与二叉树

    除了之前我们讲的栈、队列、链表等线性结构,数据结构中还有着一对多的 非线性结构 ——— 树 。 树是有 n 个结点组成的有限集,当n=0时为空树,在任意一颗非空树中,有且仅有一个 特定的根结点 ;当n1时,其余结点又可以分为一棵树,称为根的 子树 。 如下图所示: A为

    2023年04月09日
    浏览(50)
  • 数据结构与算法——树与二叉树

    😊各位小伙伴久等了,本专栏新文章出炉了!!! 我又回来啦,接下来的时间里,我会持续把数据结构与算法专栏更新完。 👉树型结构👈 是一类重要的 ✍非线性数据结构 ,其中以树和二叉树最为常用,直观来看,树是以分支关系定义的层次结构。树型结构在客观世界中

    2024年02月11日
    浏览(46)
  • 【数据结构和算法】---二叉树(1)--树概念及结构

    树是一种 非线性的数据结构 ,它是由n(n=0)个有限结点组成一个具有层次关系的集合。之所以叫它树,是因为将此结构倒转后与现实生活中的树极其相似,一个主干分出多个分支,分支还可继续分展。 有一个特殊的结点,称为 根结点 ,根节点没有前驱结点; 除根节点外,

    2024年02月03日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包