树 及 二叉树相关总结

一、思维导图

 ![](https://img2020.cnblogs.com/blog/2380994/202104/2380994-20210430201207791-745637088.png)

二、树的定义

1. 树是由n个结点（或元素）组成的有限集合（记为T）。
   如果n=0，它是一棵空树，这是树的特例；
   如果n>0,这n个结点中有且仅有一个结点作为树的根节点，简称为根，其余结点可分为m（m>=0)个互不相交的有限集T1，T2，...,Tn,其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。

三、树的基本术语

1.结点的度：树中某个结点的子树的个数.
2.树的度：树中所有结点中的最大值，通常将度为m的树称为m次树.
3. 分支结点：树中度不为零的结点称为非终端结点，又叫分支结点.
4.叶子结点：度为零的结点.
5.孩子结点、双亲结点：在一棵树中，每个结点的后继结点被称为该结点的孩子结点，相应的，该结点被称为孩子结点的双亲结点.
6.兄弟结点：具有同一个双亲结点的孩子结点互为兄弟结点.
7.树的高度：树中结点的最大层次，也叫书的深度.

四、二叉树

二叉树是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 。

五、二叉树的性质

 1.非空二叉树上的叶子结点数等于双分支结点数加1.

 2.非空二叉树的第i层上最多有2的（i-1）次方个结点（i>=1）.

 3.高度为h的二叉树最多有2的h次方-1个结点（h>=1）.

树 及 二叉树相关总结

原文：https://www.cnblogs.com/a2080941814/p/14723279.html