树是n(n>=0)个节点的有限集合。当n=0时称为空树，当n>0 为非空树，任何非空树中，有且仅有一个根节点；其余节点可分为m(m>=0)个互不相交的有限集合T1、T2 等，其中每一个集合都可以称为一棵树，称为根节点的子树。 双亲孩子、兄弟：节点的字数的根称为该节点的孩子，该节点称为其子节点的双亲。具有相同双亲的节点互为兄弟节点。如图：A是根节点，B、C、D互为兄弟；B是E、F的父节点（双亲）；E、F 互为兄弟节点。节点的度：一个节点下的子节点个数称为节点的度。比如 A的度为3，D的度为1。叶子节点：是指度为0的节点，也被称为终端节点。比如 C、E、F、G都是叶子节点。内部节点：度不为零的节点称为分支节点或非终端节点。去掉根节点，分支节点称为内部节点。比如：B、D。节点的层次：根节点A属于第一层，依次类推。B属于第二层，E属于第三层。树的高度：一棵树的最大层次数称为树的高度或者树的深度。有序（无序）树：树中的节点的各个子树看成是从左到右有次序的，即不能交换，则称为有序树，否则为无序树。二叉树是n(n>=0)个节点的有限集合，它或者是空树（n=0），或者是由一个根节点及两棵不相交的、分别称为左子树、右子树的二叉树所组成。二叉树中节点区分左子树、右子树，即便只有一个子树的情况下也有标明是左子树还是右子树，普通树则不区分；二叉树中节点最大度为2，普通树则没有限制节点的度数。3、对任何一棵二叉树，若其终端节点数为n,度为2的节点数为n2，则n=n2+14、具有n个节点的完全二叉树的深度为(log2^n)+11、满二叉树：深度为k的二叉树有2^(k-1)个节点,是满二叉树2、完全二叉树:高度为k的二叉树，除了第k层都是满的，称为完全二叉树。满二叉树也是完全二叉树。具有n个节点的完全二叉树高度为 (log2^n) +13、非完全二叉树：不满足完全二叉树的称为非完全二叉树。用一组地址连续的存储单元存储二叉树的节点，必须把节点排成一个适当的线性序列，并且节点在这个序列中的相互位置可以反映出节点之间的逻辑关系顺序存储适合对完全二叉树的存储方式，既简单又节省空间。对于一般二叉树而言，因为在顺序存储结构中，以节点在存储单元中的位置来表示节点之间的关系，所以存储方式也必须按照完全二叉树的方式存储，这样会造成空间上的浪费。最坏的情况，一个深度为h且只有h个节点的二叉树（也是单枝树）需要(2^h) -1 存储单元.由于二叉树中节点包含数据、左子树根、右子树根、双亲信息，因此可以用三叉链表或二叉链表来 存储二叉树，链表的头指针指向二叉树的根节点。遍历是按某种策略访问树中的每个节点，仅访问一次。对于含有n个节点的二叉树遍历算法的时间复杂度都是O(n).节点的路径：从树的一个节点到另一个节点之前的通路。节点的带权路径：节点到树根之间的路径长度*该节点的权重值。树的带权路径长度为树种所有叶子节点的带权路径长度之和。数值最小的就是哈夫曼树。IT技术分享社区
个人博客网站：https://programmerblog.xyz
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
