淮安制作企业网站,wordpress点击慢,开网站建设公司怎么样,美团网站开发合作商文章目录树二叉树满二叉树和完全二叉树二叉树的性质代码实现求二叉树的深度树
树是一种非线性的数据结构#xff0c;它是由n个有限结点组成一个具有层次关系的集合。
树的相关名词#xff1a;
根节点#xff1a;没有前驱结点的结点。父节点#xff0c;子节点#xff1a…
文章目录树二叉树满二叉树和完全二叉树二叉树的性质代码实现求二叉树的深度树
树是一种非线性的数据结构它是由n个有限结点组成一个具有层次关系的集合。
树的相关名词
根节点没有前驱结点的结点。父节点子节点有 节点C 为 节点E 的前驱节点那么 E 就是 C 的后继节点称 C 为 E 的父节点 E 为 C 的子节点。兄弟节点具有相同的父节点的结点互称为兄弟节点如B,C是兄弟节点深度高度从根节点到叶节点依次经过的节点含根、叶节点形成树的一条路径最长路径的长度为树的深度。度该节点的子节点个数。树的度则是其中节点度的最大值。边父子节点间的连线N 个节点有 N-1 条边。叶子节点度为零的结点为叶子节点如下图中所有# 二叉树
二叉树每个节点最多含有两个子树的树称为二叉树。特点如下
每个节点最多有两棵子树即二叉树不存在度大于2的节点二叉树的子树有左右之分其子树的次序不能颠倒
满二叉树和完全二叉树
满二叉树
一个二叉树如果每一层的节点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且节点总数为(2^k)-1则就是满二叉树
完全二叉树
满二叉树是一种特殊的完全二叉树对于深度为k的有n个节点的二叉树当且仅当每一个节点都与深度为K的满二叉树中编号1~n的结点相对应时称为完全二叉树 有一个很好的区分它们的方法满二叉树是除叶子节点外所有节点都存在左右子树的一棵树而完全二叉树则是所有节点都是连续的不存在有右子树而没有左子树的情况
二叉树的性质
一棵非空二叉树上的 第n层 最多有 2n-1 个节点层数从1开始深度为n 的二叉树的最大节点数为 2n - 1 个如果叶子节点的个数为 n0 度为2 的结点的个数为 n2 则有 n0 n2 1具有 n 个节点的完全二叉树的深度为 log2(n) 1如果 某结点 的编号为 i从0开始那么他的 左孩子 编号为 2i 1 右孩子 编号为 2i 2 他的 父节点 为 (i - 1) / 2 。
代码实现求二叉树的深度
求树的深度需要遍历树的所有节点树的遍历方式总体分为两类 深度优先搜索DFS、广度优先搜索BFS 常见的 DFS 先序遍历、中序遍历、后序遍历常见的 BFS 层序遍历即按层遍历。
本文将介绍基于 后序遍历DFS 和 层序遍历BFS 的两种解法。
DFS深度优先搜索
/**- Definition for a binary tree node.- struct TreeNode {- int val;- TreeNode *left;- TreeNode *right;- TreeNode(int x) : val(x), left(NULL), right(NULL) {}- };*/
class Solution { // 后序遍历
public:int maxDepth(TreeNode* root) {if(rootnullptr) return 0;return max(maxDepth(root-left), maxDepth(root-right)) 1;}
};BFS广度优先搜索
class Solution { // 层序遍历
public:int maxDepth(TreeNode* root) {if(rootnullptr) return 0;queueTreeNode* que;que.push(root);int res 0;while(!que.empty()){queueTreeNode* tmp;while(!que.empty()){TreeNode* node que.front();que.pop();if(node-left) tmp.push(node-left);if(node-right) tmp.push(node-right);}que tmp;res;}return res;}
};
