第十章 二叉树.pptVIP

第十章 二叉树 1、二叉树的概念 2、二叉树的结构 3、二叉树的遍历 4、线索二叉树 5、二叉有哪些信誉好的足球投注网站树 6、平衡二叉树 7、Splay树 1、二叉树的概念 二叉树的定义 一棵二叉树或是一棵空树，或由一个称为根结点和该根结点的二 棵被称为左子树和右子树的二叉树组成的树。 二叉树的5种不同的形态： ○ ○ ○ ○ ○ 结点的度、叶结点、结点的层次、树的高度 二叉树的性质 性质1：若二叉树的层次从0开始，则在二叉树的第i层最多有2i个 结点。( i≥0) 性质2：高度为k的二叉树最大结点数为2k+1－1个。( k≥ － 1) 性质3：对任何一棵二叉树，如果其叶结点个数为n0，度为2的非 叶结点个数为n2，则有n0 = n2+1。 特殊的二叉树 满二叉树：高度为k 的满二叉树是有2k+1－1个结点的二叉树。 完全二叉树：如果一棵具有n个结点的高度为k的二叉树，它的每 一个结点都与高度为k的满二叉树中编号为0～n －1的结点一一对应， 则称此二叉树为完全二叉树。 性质4：具有n个结点的完全二叉树的高度为「log2(n+1)?－1。 设该树的高度为k，由完全二叉树定义知，从第0层到第k－1层共 有2k－1个结点，第k层最多不超过2k个。于是 2 k－1 ＜n≤2k－1+ 2k＝ 2k+1－1 2 k ＜n+1≤ 2k+1 k＜log2(n+1)≤k+1 即 k+1 ＝ ? log2(n+1) ? 特殊的二叉树(续) 性质5：如果将一棵有n个结点的完全二叉树自顶向下，同一层自 左向右连续给结点编号0、1、2、…、n-1，然后按此结点编号给 对应的结点命名，则有以下关系： ①若i=0，则结点i为根，无双亲；若i＞0，则结点i的双亲为结点 ?(i－1)/2 ? 。 ②若2×i+1＜n，则结点i 的左孩子为结点2×i+1。 ③若2×i+2＜n，则结点i 的右孩子为结点2×i+2。 ④若结点编号i 为偶数，且i≠0，则它的左兄弟为结点i－1。 ⑤若结点编号i 为奇数，且i≠n－1，则它的右兄弟为结点i+1。 ⑥结点i 所在的层次为 ? log2(i－1) ? 。 2、二叉树的存储结构 链表结构二叉树的抽象数据类型 template class Entry struct Binary_node{ // data members: Entry data; // 允许外部函数修改的数据值 Binary_node Entry *left; // 指向结点左孩子的指针 Binary_node Entry *right; // 指向结点右孩子的指针 // constructors: Binary_node( ); Binary_node(const Entry x); }; template class Entry class Binary_tree{ public:. // Add methods here. protected: // Add auxiliary function prototypes here. Binary_node Entry *root; }; Binary_tree的实现 创建Binary_node对象，调用函数new创建新的结点时，将指针left和right 置为NULL。 空树的建立 templateclass Entry Binary_tree Entry ∷ Binary_tree( ) /* Post: An empty binary tree has been created. */ { root = NULL; } 空树的判断 templateclass Entry Bool Binary_tree Entry ∷ empty( ) const /* Post: A result of true is returned if the binary tree is empty. Otherwise, false is returned.*/ { return root = = NULL; } 二叉链表与三叉链表 示意图 二叉树的数组