性质4具有n(≥0)个结点的完全二叉树 的高度为「og2(n+1)1-1 证明:设完全二叉树的高度为h,则有 2h-1<n<2h+1-1 上面h层结点数第h层结点数 变形2h<n+1≤2h+1 取对数h<log2n+1)sh+1 因此有「og2(n+1)1=h+1 h=「log2n+1)1-1
性质4 具有 n (n 0) 个结点的完全二叉树 的高度为 log2 (n+1) -1 证明：设完全二叉树的高度为h，则有 2 h - 1 < n 2 h+1 - 1 变形 2 h < n+1 2 h+1 取对数 h < log2 (n+1) h+1 因此有 log2 (n+1) = h+1 h = log2 (n+1) -1 上面h层结点数 第h层结点数
性质5如将一棵有n个结点的完全二叉树自 顶向下,同一层自左向右连续给结点编号0, 1,2,…,n-1,则有以下关系: 若i=0,则i无双亲 若i>0,则i的双亲为(-1)2」 若2*计1<n,则i的左子女为2计1,若 2*计+2<n,则i的右子女为2*计2 若i为偶数,且=0, 则其左兄弟为i-1,若 i为奇数,且i!=n-1, 则其右兄弟为计1680
性质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 0 1 2 3 7 4 5 6 8 9
二叉树的抽象数据类型 template <class Type> class Binary Tree public: Binary Tree (; /构造函数 Binary Tree( BinTreeNode<type>* Ich Bin TreeNode<Type>* rch, Type item ) /构造以em为根,lh和rch为左、右 //树的二叉树 int IsEmpty (; /判二叉树空否? Bintreenode<lype>* Parent();/双亲
二叉树的抽象数据类型 template <class Type> class BinaryTree { public: BinaryTree ( ); //构造函数 BinaryTree ( BinTreeNode<Type> * lch, BinTreeNode<Type> * rch, Type item ); //构造以item为根，lch和rch为左、右 //子树的二叉树 int IsEmpty ( ); //判二叉树空否？ BinTreeNode<Type> * Parent ( ); //双亲
BinTreeNode<Type> x Leftchild o 取左子女结点地址 BinTreeNode<type>* right Child o: 取右子女结点地址 int Insert( const Type& item //插入 int Find( const Type&item) const;搜索 Type GetData( const;∥得结点数据 BinTreeNode<type>* Getroot( const ∥取根结点地址
BinTreeNode<Type> * LeftChild ( ); //取左子女结点地址 BinTreeNode<Type> * RightChild ( ); //取右子女结点地址 int Insert ( const Type& item ); //插入 int Find ( const Type &item ) const; //搜索 Type GetData ( ) const; //取得结点数据 BinTreeNode<Type> *GetRoot ( ) const; //取根结点地址 }
二叉树的顺序表示 2 3 3 ⑦8 9 012345678901234567 89 完全二叉树 一般二叉树 的顺序表示 的顺序表示
完全二叉树 一般二叉树 的顺序表示 的顺序表示 二叉树的顺序表示 0 0 1 2 3 4 5 6 7 8 9 9 0 1 2 3 4 5 6 7 8 9 1 3 7 8 9 4 5 6 2 0 1 2 3 4 5 6 7 8