二叉树的链接存储 仅定义结点的类型即可。结点之间的关系通过指针实现。 标准形式:(二叉链表) datalleftright 广义标准形式:(三叉链表) data left ght Parent
二叉树的链接存储 仅定义结点的类型即可。结点之间的关系通过指针实现。 A B C D E F G I H L data left right 标准形式：（二叉链表） 广义标准形式：（三叉链表） data left right Parent
二叉树的链接存储 例: B C∧ ∧DA E G ∧F∧ ∧G∧
二叉树的链接存储 例： A B ∧ ∧ /\ ∧ ∧ ∧ ∧ ∧ C D E F G G F D B C A E
二叉树的ADT template< class Type>class BinaryTree;//二叉树类 Binary Tree的向前说明 template <class Type> class BinaryNode friend class BinaryTree< Type> publi Binary Node():left(NUL), right(NULL){}//二叉树结点的构造函数。 Binary Node( Type item, BinaryNode< Type>* L= NULL, BinaryNode< Type>* R= NULL ) data(item), left(L), right(r)[ Binarynode Type GetData() const{ return data;}//得到二叉树结点的数据值。 BinaryNode<Type>* GetLeft()const( return left //得到二叉树结点的左儿子地址 inaryNode <Type>* GetRight()consti return right; //得到二叉树结点的左儿子地址。 void SetData( const Type& item)i data= item; I /设置二叉树结点的数据值。 void SetLeft (BinaryNode< Type>*L)i left=L; j //设置二叉树结点的左儿子地址。 void Setright (BinaryNode< Type>*r) right =R; I //设置二叉树结点的右儿子地址
二叉树的ADT template <class Type> class BinaryTree; // 二叉树类 BinaryTree 的向前说明 template <class Type> class BinaryNode { friend class BinaryTree < Type>; public: BinaryNode ( ) : left(NULL), right(NULL) { } // 二叉树结点的构造函数。 BinaryNode ( Type item, BinaryNode < Type> * L = NULL, BinaryNode < Type> * R = NULL ): data(item),left(L), right( R) { } ～BinaryNode ( ) { } Type GetData ( ) const { return data; } // 得到二叉树结点的数据值。 BinaryNode<Type> * GetLeft( ) const { return left;} //得到二叉树结点的左儿子地址。 inaryNode<Type> * GetRight( ) const { return right; } //得到二叉树结点的左儿子地址。 void SetData ( const Type & item ) { data = item; } // 设置二叉树结点的数据值。 void SetLeft (BinaryNode < Type> * L ) { left = L; } // 设置二叉树结点的左儿子地址。 void SetRight (BinaryNode < Type> * R ) { right = R; } // 设置二叉树结点的右儿子地址
二叉树的ADT template< class Type>class BinaryTree;//二叉树类 Binary Tree的向前说明 template <class Type>class BinaryNode I friend class BinaryTree< Type> publi void Print PreOrder() const;//按前序打印二叉树的结点的数据值 void Printpostordero const //按后序打印二叉树的结点的数据值。 void Print InOrder() //按中序打印二叉树的结点的数据值 Binary Node<type>* Duplicate() const;//复制以本结点为根的子树。 private BinaryNode<Type)*left,* right;//结点的左、右儿子的地址 Type data //结点的数据信息
二叉树的ADT template <class Type> class BinaryTree; // 二叉树类 BinaryTree 的向前说明 template <class Type> class BinaryNode { friend class BinaryTree < Type>; public: void PrintPreOrder( ) const; // 按前序打印二叉树的结点的数据值。 void PrintPostOrder( ) const; // 按后序打印二叉树的结点的数据值。 void PrintInOrder( ) const; // 按中序打印二叉树的结点的数据值。 BinaryNode<Type> * Duplicate( ) const; // 复制以本结点为根的子树。 private: BinaryNode < Type> * left , * right ; // 结点的左、右儿子的地址 Type data; // 结点的数据信息 };
二叉树的ADT template <class Type>class binaryTree public: Binary tree(): root( NULL) //构造空二叉树 Binary tree( const Type value i root new Binary Node<Type>( value); I Binarytree() DelTree( root): I int isEmpty()const return root = NULL, /二叉树为空,返回非0,否则为0 const binary Node<T ype>* Getroot( )consti return root int MakeEmpty(){ Deltree(root);root=NUL;}/使二叉树为空。 const Binary Tree<Type>& operator=( const Binary Tree<Type>& T) private: Binary Node<type〉*root;//二叉树的根结点。 Binary tree( const Binary Tree<Type>&) void deltree( binaryNode <Type>*T) template <class Type> const BinaryTree<Type>& BinaryTree<Type>:: operator =(const Binary tree<type>&t) f( this! =&T) De ltree(root);//其具体实现,见程序5.1。 if T root =NULL )root = T. root->Duplicate()
二叉树的ADT template <class Type> class BinaryTree { public: BinaryTree( ) : root( NULL) { } // 构造空二叉树 BinaryTree ( const Type & value ) { root = new BinaryNode<Type> ( value ); } ~BinaryTree ( ) { DelTree ( root ); } int IsEmpty ( ) const { return root == NULL; } // 二叉树为空，返回非0，否则为0。 const BinaryNode<Type> * Getroot( )const { return root; } int MakeEmpty ( ) { DelTree( root); root == NULL; } // 使二叉树为空。 const BinaryTree<Type> & operator = ( const BinaryTree<Type> & T); private: BinaryNode<Type> * root; // 二叉树的根结点。 BinaryTree( const BinaryTree<Type> & ); void DelTree( BinaryNode<Type> * T ); }; template <class Type> const BinaryTree<Type> & BinaryTree<Type> :: operator = ( const BinaryTree<Type> & T ) { if ( this != &T ) { DelTree(root); // 其具体实现，见程序5.1。 if ( T.root != NULL ) root = T.root->Duplicate( ); } }