二叉树的抽家数据类烈 template <class Type> class BinaryTree i public BinaryTree( Binary Tree( Bin TreeNode<Type>* lch Bin TreeNode<Type>*rch, Type item int /( Bin TreeNode<Type>xParent (; Bin TreeNode<Type> *leftchild o; Bin TreeNode<Type>* RightChild (; int Insert( const Type &item ) int Find( const Type &item )const Type GetData( consts Bin TreeNode<Type> *Getroot( const
二叉树的抽象数据类型 template <class Type> class BinaryTree { public: BinaryTree ( ); BinaryTree ( BinTreeNode<Type> * lch, BinTreeNode<Type> * rch, Type item ); int IsEmpty ( ); BinTreeNode<Type> *Parent ( ); BinTreeNode<Type> *LeftChild ( ); BinTreeNode<Type> *RightChild ( ); int Insert ( const Type &item ); int Find ( const Type &item ) const; Type GetData ( ) const; BinTreeNode<Type> *GetRoot ( ) const; }
二叉树的表示 教组表示 05 05 14 (a) 012345678910 01234567891011121314 31231266940577016249583123{12661051770162 完全二叉树的数组表示一般二叉树的数组表示
完全二叉树的数组表示 一般二叉树的数组表示 二叉树的表示 数组表示
由于一般二叉树必须仿照完a1 全二叉树那样存储,可能会 浪费很多存储空间,单支树 6 就是一个极端情况。 14 (88 30 单支树 49 链表表示 leftChild data parent rightChild leftchild data right child parent data leftchild right child leftchild right Child (a)二叉链表 (b)三叉链表
单支树 链表表示 由于一般二叉树必须仿照完 全二叉树那样存储，可能会 浪费很多存储空间，单支树 就是一个极端情况
root root root A ∠A△ B B C C D E E^F內 (a)二叉树 (b)二叉链表 (C)三叉链表 二又树链表表示的示例
二叉树链表表示的示例
root data parent leftchild right Child (E)(F 2345 ABCDEFG 1214111 356 G 11334 1 (a)二叉树 二叉链表的静恋结构
二叉链表的静态结构