首页 > 其他分享 >第5章. 二叉树

第5章. 二叉树

时间:2023-12-06 20:34:38浏览次数:39  
标签:度为 节点 叶子 二叉树 n2 数量

二叉树


一、树的基本概念

  • 节点、根节点、父节点、子节点、兄弟节点
  • 一棵树可以没有任何节点,称为空树
  • 一棵树可以只有一个节点,也就是只有根节点
  • 子树、左子树、右子树
  • 节点的:子树的个数
  • 树的:所有节点度中的最大值
  • 叶子节点:度为0的节点
  • 非叶子节点:度不为0的节点
  • 层数:根节点在第1层,根节点的子节点在第二层,依次类推(有些根节点从第0层开始算)
  • 节点的深度:从根节点到当前节点的唯一路径上的节点总数
  • 节点的高度:从当前节点到最远叶子节点的路径上的节点总数
  • 树的深度:所有节点深度中的最大值
  • 树的高度:所有节点高度中的最大值
  • 树的深度等于树的高度

二、有序树、无序数、森林

  • 有序树:树中任意节点的子节点之间有顺序关系
  • 无序树:树中任意节点的子节点之间没有顺序关系,也称为"自由树"
  • 森林:由m(m >-= 0)棵互不相交的树组成的集合

三、二叉树(Binary Tree)(重要)

这些都是二叉树:

3.1 二叉树的特点
  • 每个节点的度最大为2(最多拥有2棵子树) (可以为0或1或2)
  • 左子树和右子树是有顺序的
  • 即使某节点只有一颗子树,也要区分左右子树
  • 二叉树是有序树
3.2 二叉树的性质
  • 非空二叉树的第i层,最多有2i-1个节点(i >= 1)
  • 在高度为h的二叉树上最多有2h - 1个节点(h >= 1) (等比数列求和)
  • 对于任何一颗非空二叉树,如果叶子节点的个数为n0,度为2的节点的个数为n2,则
  • 假设度为1的节点的个数为n1,那么二叉树的节点总数n = n0 + n1+ n2
  • 二叉树的边数T = n1 + 2*n2 = n - 1 = n0 + n1 + n2 - 1
  • 得出n0 = n2 + 1

四、真二叉树(Proper Binary Tree)

真二叉树:所有节点的度都要么为0,要么为2

五、满二叉树(Full Binary Tree)

满二叉树:最后一层节点的度都为0,其他节点的度都为2。

满二叉树:所有节点的度要么为0,要么为2,且所有的叶子节点都在最后一层。

  • 在同样高度的二叉树中,满二叉树的叶子节点数量最多,总节点树量最多

  • 满二叉树一定是真二叉树,真二叉树不一定是满二叉树

  • 假设满二叉树的高度为h(h >= 1),那么

第1层节点数量   1
第2层节点数量   2
第3层节点数量   4
第4层节点数量	  8
...
第i层节点数量   2^(i - 1)
总节点数量  1 + 2 + 4 + 8 + ... 等比数列求和
  • 第i层的节点数量:2i-1
  • 叶子节点数量:2h-1
  • 总结点数量:n = 2h - 1,所以h = log2(n+1)

六、完全二叉树(Complete Binary Tree)(重要)

完全二叉树:叶子节点只会出现在最后2层,且最后1层的叶子结点都靠左对齐。

完全二叉树:对节点从上至下、左至右开始编号,其所有编号都能与相同高度的满二叉树中的编号对应

6.1 完全二叉树的特点
  • 叶子节点只会出现在最后2层,最后一层的叶子节点都靠左对齐
  • 完全二叉树从根节点至倒数第2层是一颗满二叉树
  • 满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树
  • 度为1的节点只有左子树
  • 度为1的节点要么是0个,要么是1个
  • 同样节点数量的二叉树,完全二叉树的高度最小
6.2 完全二叉树的性质



标签:度为,节点,叶子,二叉树,n2,数量
From: https://www.cnblogs.com/keyongkang/p/17880460.html

相关文章

  • 17_二叉树的所有路径
    二叉树的所有路径给你一个二叉树的根节点root,按任意顺序,返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。示例1:输入:root=[1,2,3,null,5]输出:["1->2->5","1->3"]示例2:输入:root=[1]输出:["1"]【思路】题目要求从根节点到叶子的路径,所以需要......
  • 16_平衡二叉树
    平衡二叉树【题外话】二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数。(从上往下看)二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数。(从下往上看)小疑惑:为什么104.二叉树的最大深度中求的是二叉树的最大深度,也用的是后序遍历。(本质上求解的就是根节......
  • 15_完全二叉树的节点个数
    完全二叉树的节点个数给你一棵完全二叉树的根节点root,求出该树的节点个数。完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层,则该层包含1~2h个节点。示......
  • 二叉树创建及遍历
    #include<stdio.h>#include<iostream>usingnamespacestd;typedefcharTElemType;typedefvoidStatus;typedefintElemType;typedefstructBiTNode{ TElemTypedata; BiTNode*lchild,*rchild;}BiTNode,*BiTree;voidCreateBiTree(BiTree......
  • C++U5-08-二叉树1
    上节课作业分析讲解视频链接:https://pan.baidu.com/s/1_jaM_TlZmLJX4JbLuJtKzA?pwd=2us4提取码:2us4学习目标  树在C++中,二叉树是一种常用的数据结构,由节点(Node)组成,每个节点可以有最多两个子节点。二叉树具有以下几个主要的作用:存储和组织数据:二叉树可用于存储和组织大......
  • 二叉树
    二叉树分析二叉树的前序,中序,后序的遍历步骤1.创建一颗二叉树2前序遍历2.1先输出当前节点初始的时候是root节点2.2如果左子节点不为空则递归继续前序遍历2.3如果右子节点不为空,则递归继续前序遍历3.中序遍历3.1如果当前节点的左子节点不为空,则递归中序遍历3.2输出当前......
  • 多叉树转二叉树
    CPP代码点击查看代码#include<iostream>#include<queue>#include<stack>usingnamespacestd;//多叉树节点structNode{ stringname;//节点名称 vector<Node*>nodes;//子节点指针数组 // 构造函数 Node(stringname,vector<Node*>nodes):name(n......
  • 查找 - 二叉排序树/平衡二叉树
    二叉排序树性质:中序遍历是递增的查找算法实现BSTreeSearchBST(BSTreeT,KeyTypekey){if(!T||key==T->data)returnT;elseif(key<T->data)returnSearchBST(T->lchild,key);elsereturnSearchBST(T->rchild,key);}算法分析最坏情况:单支树A......
  • 13_翻转二叉树
    翻转二叉树给你一棵二叉树的根节点root,翻转这棵二叉树,并返回其根节点。示例1:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]示例2:输入:root=[2,1,3]输出:[2,3,1]示例3:输入:root=[]输出:[]【思路】基本思想就是想要翻转二叉树,只需要把每一个节点的左右孩子交......
  • Python实现完全二叉树
    给定一个元素序列(如列表),递归的创建一颗完全二叉树完整代码如下#!/usr/bin/envpython3classTreeNode:"""Nodeofcompletetree"""def__init__(self,data=0):self.data=dataself.left=Noneself.right=Nonedefb......