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