文章目录

• 😏专栏导读
• 🤖文章导读
• 🙀树的预备知识
• 🙀二叉树
• • 😳树的代码实现及其各类讲解
  • • 🌲树的结构体初始化
    • 总结

      ---

      😏专栏导读

      👻作者简介：M malloc，致力于成为嵌入式大牛的男人

      👻专栏简介：本文收录于 初阶数据结构，本专栏主要内容讲述了初阶的数据结构，如顺序表，链表，栈，队列等等，专为小白打造的文章专栏。

      👻相关专栏推荐：LeetCode刷题集，C语言每日一题。

      ---

      🤖文章导读

      本篇文章我将详细的讲解关于树的知识点

      

      🙀树的预备知识

      前情介绍

      对于大量的输入数据，链表的线性访问时间太慢，不宜使用。本片文章，我将讲述一种简单的数据结构，其大部分操作的时间复杂度为O(log n)。

      ---

      树

      树(tree)可以用几种方式定义。定义树的一种自然的方式是递归的方法。一棵树是一些节点的集合。这个集合可以是空集;若非空，则一棵树由称做根(root)的节点r以及0个或多个非空的(子)树 T1，T2，…，T 组成，这些子中每一的根都被来自根的一条有向的边(edge)所连接。

      每一棵子树的根叫做根r的儿子(child)而r每一棵子的根的父亲(parent)。下图是显示用递归定义的典型的树。

      

      ---

      从递归定义中我们发现，一棵树是 N 个节点和N - 1条边的集合，其中的一个节点叫做根。存在 N -1条边的结论是由下面的事实得出的，每条边都将某个节点连接到它的父亲，而除去根节点外每一个节点都有一个父亲,如下图所示。

      

      根节点，父亲节点，叶子节点，兄弟节点的详解

      在上图的树中，节点A是根结点，节点F有一个父亲A并且有儿子K、L、M。每一个节点可以有任意多个儿子，也可以没有儿子也就是0个，但是只能有一个父亲。没有儿子的节点成为叶子节点(leaf)；上图的叶子节点是B,C,H,I,P,Q,K,L,M和N。具有相同父亲的节点称为兄弟节点(sibing);因此K、L和M都是兄弟。

      ---

      深度(depth)

      首先，根的深度为0。在上图中E节点的深度为1，但是高为2，F的深度为1，高为1，该树的高为3，一个树的深度等于它的最深的树叶的深度；该深度总是等于这颗树的高。

      🙀二叉树

      二叉树(binary tree)是一棵树，其中每个节点都不能有多于两个的儿子。

      

      二叉树的一个性质是平均二叉树的深度要比 N 小得多这个性质有时很重要。分析表明，这个平均深度为 O(/N).而对于特殊类型的二叉树，即二叉查找树(binary search tree)其深度的平均值是 O(log N)。不幸的是，正如下图中的例子所示，这个深度是可以大到 N -1的。

      最坏情况的二叉树

      

      😳树的代码实现及其各类讲解

      🌲树的结构体初始化

      树的结构

      typedef int BTDataType;
      typedef struct BinaryTreeNode
      {
      	BTDataType data;
      	struct BinaryTreeNode* left;
      	struct BinaryTreeNode* right;
      }BTNode;
      

      二叉树，顾名思义就是一个左子树，一个右子树，所以在这里我们定义了一个结构体类型的左子树和右子树。那么是不是还要存放数据呢？对的没错！所以还需要一个数据域data

      ---

      手动创建一个树和开辟新节点

      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;
      }
      

      在上述代码中运用到了malloc这个库函数。这是在堆上动态开辟一块区域，把我们想要存入的值再放进去。

      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);
      	BTNode* node7 = BuyNode(7);
      	BTNode* node8 = BuyNode(8);
      	node1->left = node2;
      	node1->right = node4;
      	node2->left = node3;
      	node4->left = node5;
      	node4->right = node6;
      	//node5->left = node7;
      	node2->right = node7;
      	node3->left = node8;
      	return node1;
      }
      

      上述是手动进行指向节点，就是我们要对应着一幅图进行画它的指向，比如，node1的左边指向node2，就说明node2在node1的左边，然后node1的右边存放着node4，就说明node4的父亲是node1，也就是node4在node1的右边，也就是下图所示

      

      ---

      树的前序遍历

      其实在树的前序遍历过程中其实就是递归的过程。有一个很好的口诀，就是中左右，意思就是先遍历根节点，然后在遍历左子树，再从左子树递归下去，右子树也是样的操作。

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

      

      ---

      树的中序遍历

      那么中序遍历呢？中序遍历的口诀是左中右，就是先遍历左子树，在遍历根节点，右子树。就是这样的一系列的操作就行啦

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

      

      ---

      树的后序遍历

      后序遍历的自然也是有口诀的啦！我们的口诀是左右中，此时我们的根节点是最后才遍历的不知道你们发现没有！

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

      ---

      总结

      在本片文章中只是粗略的介绍了一下树的前中后序的遍历，其实代码的思路是很简单的就是几个递归的操作，大家多画画递归的展开图就能理解啦！那么这只是树的上篇。在树的下篇中，我将详细讲解怎么利用递归求出树的一系列操作等问题，我是爱你们的M malloc 我们下期再见！

       
       网站建设设计方案  十大免费推广平台  建网球场多少钱  网站设计的主要步骤  网络营销所学课程  香港域名注册网站