《二叉树的定义.docx》由会员分享，可在线阅读，更多相关《二叉树的定义.docx（5页珍藏版）》请在三一办公上搜索。
1、二叉树的定义、定义、存储二叉树的定义 二叉树是每个节点最多有两个子树的树结构。通常子树被称作左子树 （left subtree）和 右子树（r/*g*t subtree）。二叉树常被用于实现二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树（不存在度大于2的结点），二叉树的子树有左右之分， 次序不能颠倒。特殊二叉树1. 斜树所有结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树。斜树 的每一层都只有一个结点，结点的个数与斜树的深度相同。2. 满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层 上，这样的二叉树称为满二叉树。（上图中所示
2、的二叉树，就是一棵满二叉树）3. 完全二叉树 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1i1)o (由性质1，通过等比数列求和 可证)性质3： 一棵二叉树的叶子结点数为n0,度为2的结点数为n2,则n0 = n2 + 1。证：结点总数n = n0 + n1 + n2o设B为分支总数，因为除根节点外，其余结点都有一个 分支进入，所以n = B + 1又因为分支是由度为1或2的结点射出，所以B = n1 + 2n2。综上：n = n0 + n1 + n2 = B + 1 = n1 + 2n2 + 1,得出：n0 = n2 + 1。性质4：具有n个结点的完全二叉树的深度为floor(lo
3、g2n) + 1。性质5：如果对一棵有n个结点的完全二叉树(其深度为floor(log2n) + 1 )的结点按层 序编号，则对任一结点i (lWiWn)有：(1) 如果i = 1，则结点i是二叉树的根，无双亲；如果i 1，则其双亲PARENT(i)是 结点 floor(i)/2)。(2) 如果2i n，则结点i无左孩子；否则其左孩子LCHILD(i)是结点2i。(3) 如果2i + 1 n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i + 1。二叉树的存储1. 顺序存储结构二叉树可以用一维数组或线性表来存储，而且如果这是完全二叉树，这种方法不会浪费空间。并且这种紧凑排列，如果一
4、个结点的索引为i,则它的子结点能在索引2i + 1和2i + 2找到， 并且它的父节点（如果有）能在索引floor（i-1）/2）找到（假设根节点的索引为0）。对于一般的二叉树，其层序编号不能反映出逻辑关系，但是可以将其按照完全二叉树编号， 只不过把不存在的结点设置为NULL即可。但这么做有一个问题，就是会浪费存储空间。最坏情况下，一个深度为k的斜树（只有k个结点），却需要长度为2k-1的一维数组。所 以顺序存储结构一般只用于完全二叉树。2. 链式存储结构每个结点含有一个数据域和两个指针域（分别指向左右子树）。/二叉树的二叉链表存储表示typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild; / 左右孩子指针BiTNode,*BiTree;利用这种结点结构所得的二叉树存储结构称之为二叉链表。在二叉链表中，如果想找到某个 结点的双亲，需要从根节点开始遍历，所以有时为了便于找到结点的双亲，还可以在结点结 构中增加一个指向其双亲结点的指针域，相应的二叉树存储结构称之为三叉链表。
