1、树和子树(1)、什么是树在学习二叉树前非常有必要先了解一下什么是树、什么是子树并清楚什么是树形结构如下图所示的是我们日常生活中随处可见的树木。仔细观察可以发现这棵树是从一根主干开始然后向上不断分叉其中从任何一个分叉点节点开始连同它上方长出的所有更小分叉和叶片都构成这棵大树的子树。这种“大树枝干中包含小树枝干”的结构就是计算机科学中“树”这种数据结构的递归本质的生动写照。通过对比此前所学习的链表和队列这样一对一关系的线性结构满足一颗大树这样一对多的关系的就可以称之为树形结构。在计算机中树是一种非线性的分层数据结构。它由节点Node和连接节点的边Edge组成。可以把上图这颗树想象成一颗倒挂的“现实中的树”根在上枝叶在下。(2)、树的关键术语A - 根节点 / \ B C - B和C是A的子节点它们互为兄弟 / \ \ D E F - D、E、F是叶子节点没有子节点 / \ G H - G和H是E的子节点节点Node树中的每个元素如 A、B、C...。父节点Parent和子节点ChildA是B和C的父节点B和C是A的子节点。兄弟节点Sibling具有相同父节点的节点如B和C。祖先节点Ancestor从根节点到该节点路径上的所有节点对G来说A、B、E都是祖先。后代节点Descendant该节点子树中的所有节点对E来说G、H是后代。度Degree一个节点拥有的子节点数量A的度为2B的度为2C的度为1D的度为0。树的度整棵树中所有节点度的最大值上例中为2。叶子Leaf度为0的节点D、F、G、H。层Level根节点在第1层其子节点在第2层依此类推。高度Height或深度Depth树中节点的最大层数上例中高度为4。2、二叉树(1)、什么是二叉树二叉树Binary Tree 是一种树形的数据结构它的每个节点最多只有两个子节点度不大于2分别称为左子节点和右子节点。这个“最多两个”的特性是它和一般树子节点数量不限的根本区别。一个二叉树主要由以下部分组成根节点Root树的最顶层节点没有父节点。内部节点Internal Node至少有一个子节点的节点。叶子节点Leaf Node没有子节点的节点位于树的末端。子树Subtree每个节点及其所有后代节点构成的树。(2)、二叉树类型二叉树有如下几种常见的类型类型特点满二叉树每个节点要么是叶子要么有两个子节点。没有“单分支”节点。完全二叉树除了最后一层其他层节点全满且最后一层节点从左到右连续排列。堆Heap就是基于此结构。完美二叉树既是满二叉树又是完全二叉树。所有叶子节点都在同一层节点总数正好为 2^k - 1。平衡二叉树任意节点的左右子树高度差不超过1如AVL树、红黑树可保证查找效率为 O(log n)。二叉搜索树左子树所有节点值 根节点值 右子树所有节点值。支持快速查找、插入和删除。退化二叉树每个节点只有一个子节点实际上退化为链表查找效率变为 O(n)。(3)、二叉树的遍历方式遍历是访问树中所有节点的过程根据根节点的访问顺序分为三类深度优先遍历前序遍历根 → 左 → 右用途复制树结构或用于序列化。中序遍历左 → 根 → 右用途在二叉搜索树中会得到有序序列。后序遍历左 → 右 → 根用途删除树或计算目录大小先处理子项。先序、中序、后序 是针对 “根”来讲的若 “左” 和 “右”不是终端结点则会进入递归遍历但每次访问的都是“根”。另外还有层序遍历属于广度优先遍历从上到下、从左到右逐层访问通常借助队列实现。(3)、二叉树的存储方式和其它逻辑结构类似二叉树既可以使用顺序存储也可以使用链式存储。顺序存储主要用于完全二叉树如堆。按层序编号根节点索引为1则节点 i 的左子为 2i右子为 2i1父节点为 i/2。节省空间但不适合稀疏树。由于在顺序存储时数据元素之间的逻辑关系是用物理位置来表达的而二叉树中每一个节点都有一个对应的标号因此可以使用标号来作为数组的下标但除非是完美或者完全二叉树否则会浪费存储空间如下图所所示。在顺序存储中节点彼此之间的关系要用到二叉树标号的基本特性。简单观察二叉树的标号会发现如下规律根节点标号为1根节点没有父节点标号为n的节点其父节点的标号为n/2标号为n的节点其左孩子若有的标号为2n其右孩子若有的标号为2n1根据以上结论在顺序存储的二叉树中虽然没有任何信息连接节点e和f但根据他们的下标序号可以得知e是f的父节点且f是e的左孩子。链式存储每个节点包含数据域、左指针、右指针可能还有父指针。对于链式存储而言二叉树节点的设计与链表无异如下typedef struct node { datatype data; // 用户数据 struct node *lchild; // 左子树指针 struct node *rchild; // 右子树指针 }node;