超全C语言二叉树基本操作及讲解 |
您所在的位置：网站首页 › 二叉树的基本操作总结 › 超全C语言二叉树基本操作及讲解 |
超全C语言二叉树基本操作及讲解
|
今天刷LeetCode上的题的时候，做到了关于二叉树的题，于是决定把这一块的知识整理一下。 1、二叉树的定义 二叉树通常以结构体的形式定义，如下，结构体内容包括三部分：本节点所存储的值、左孩子节点的指针、右孩子节点的指针。这里需要注意，子节点必须使用指针，就像我们定义结构体链表一样，下一个节点必须使用地址的方式存在在结构体当中。 struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; 当然，我们也可以为我们的的树节点结构体重新定义一下名字，使用C语言中的typedef方法就可以了。 typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } BiNode, *BiTree; 在本篇博客中，我们还是使用第一种方法来定义结构体，因为这是LeetCode中定义二叉树的方式，同时也方便下面讲解创建二叉树。 2、二叉树的创建
二叉树的操作通常使用递归方法，如果递归不太明白，建议去对此进行一下学习和练习。二叉树的操作可以分为两类，一类是需要改变二叉树的结构的，比如二叉树的创建、节点删除等等，这类操作，传入的二叉树的节点参数为二叉树指针的地址，这种参入传入，便于更改二叉树结构体的指针（即地址）。这里稍微有一点点绕，可能需要多思考一下。 如下是二叉数创建的函数，这里我们规定，节点值必须为大于0的数值，如果不是大于0的数，则表示结束继续往下创建子节点的操作。然后我们使用递归的方法以此创建左子树和右子树 int CreateTree(struct TreeNode** root) { int val; scanf_s("%d", &val); if (val 0) { (*root)->val = val; CreateTree(&((*root)->left)); CreateTree(&((*root)->right)); } return 0; }因为有小伙伴问了，可否在构建二叉树传入的参数为一级地址。上述的方法是一定要传二级参数的，但是这里给出一个传一级参数的方法，小伙伴也可以通过对比两种方法，对二叉树的构建和传参方式有更深的理解。 struct TreeNode* Create(){ int val; scanf("%d", &val); struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode*)); if (val 0) { root->val = val; root->left = Create(); root->right = Create(); } return root; }3、先、中、后序遍历二叉树
先序、中序和后序，实际上是指的根节点在子节点的先中后。以上图为例， 先序为：3、2、2、3、8、6、5、4， 中序为：2、2、3、3、4、5、6、8， 后序为2、3、2、4、5、6、8、3。 其实这三种遍历方式，实现过程还是十分相似的，在递归顺序方面有些不同，其他都一样，代码量很少，如下。 先序： void PreOrderTree(struct TreeNode* root) { if (root == NULL) { return; } printf("%d ", root->val); PreOrderTree(root->left); PreOrderTree(root->right); }中序： void InOrderTree(struct TreeNode* root) { if (root == NULL) { return; } InOrderTree(root->left); printf("%d ", root->val); InOrderTree(root->right); }后序： void PostOrderTree(struct TreeNode* root) { if (root == NULL) { return; } PostOrderTree(root->left); PostOrderTree(root->right); printf("%d ", root->val); }验证程序是否正确的主函数和结果图如下： int main() { struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode*)); //第二种构建方式： //root = Create(); CreateTree(&(root)); printf("先序排列为："); PreOrderTree(root); printf("\n中序排列为："); InOrderTree(root); printf("\n后序排列为："); PostOrderTree(root); return 0; }
4、二叉树的最大深度（LeetCode104） int maxDepth(struct TreeNode* root) { if (root == NULL) { return 0; } else { int maxLeft = maxDepth(root->left), maxRight = maxDepth(root->right); if (maxLeft > maxRight) { return 1 + maxLeft; } else { return 1 + maxRight; } } }这也是LeetCode 104 Maximum Depth of Binary Tree题的答案，在做这道题的时候，一开始我并没有定义maxLeft和maxRight这两个变量，直接在判断处调用函数，这导致整个程序的运行时间过长。这道题的思想很简单，一棵树的最大深度，左子树和右子树的最大深度+1即可，使用递归，截止条件判断好了，很容易就能够做出来。 5、二叉树叶子节点的数量 这里我们要提到“度”的定义，简单来说，一个节点的度就是一个节点的分支数，二叉树中的节点按照度来分类的话，分为三类，度分别为0、1、2的节点，我们将其数量表示为n0、n1、n2，且我们将一棵树的总结点数量用N来表示。那么一个数的叶子节点的数量即为n0，且有N=n0+n1+n2。如果我们按照一棵树的子节点数来计算一棵树的总结点数，那么一棵二叉树树的总结点数N=2*n2+n1+1，最后一个1表示树的根节点。我们将关于N的两个等式合并，则有结论： n0=n2+1 上述的结论与我们下面求叶子节点没有什么关系，只是作为一个知识的普及。 叶子节点计算方法如下： int LeafNodeNum(struct TreeNode* root) { if (root == NULL) { return 0; } if (root->left == NULL&&root->right == NULL) { return 1; } else { return LeafNodeNum(root->left) + LeafNodeNum(root->right); } }
|
【本文地址】
今日新闻 |
推荐新闻 |