632二叉树的链式存储结构—一二叉(三叉)链表结构 二叉链表结构 左子指针数据元素右子指针 leftChild data rightChild 叉链表结构 左子指针数据元素右子指针 leftChild data father right Child 父指针 2021220
2021/2/20 6 6.3.2 二叉树的链式存储结构——二叉（三叉）链表结构 二叉链表结构： 左子指针 数据元素 右子指针 三叉链表结构： 左子指针 数据元素 右子指针 父指针 leftChild data rightChild leftChild data father rightChild
二叉链表结构的二叉树结点(简称二叉树结点)的类定义 template< class Type> class binary tree;叉树类声明 template< class Type> class bin treeNode./叉树结点类定义 friend class Binary Tree< Type>;/叉树类是二叉树结点类的友元 public Bin TreeNode(: left child(null), right Child(null)) ∥构造函数 Bin TreeNode( type item, Bin TreeNode< type>* left- NULL Bin TreeNode<type>* right- NULL): data(item) leftchild( left), right Child(right){M构造函数 /其他成员函数 private Bin TreeNode<Type>* leftchild, * rightChild 在子指针、右子指针 Type data/(数据元素 2021220
2021/2/20 7 二叉链表结构的二叉树结点（简称二叉树结点）的类定义： template <class Type> class BinaryTree;//二叉树类声明 template <class Type> class BinTreeNode//二叉树结点类定义 { friend class BinaryTree<Type>;//二叉树类是二叉树结点类的友元 public: BinTreeNode( ): leftChild(NULL),rightChild(NULL) { } //构造函数 BinTreeNode( Type item,BinTreeNode<Type> * left = NULL, BinTreeNode<Type> * right = NULL):data(item), leftChild(left),rightChild(right) { }//构造函数 … //其他成员函数 private: BinTreeNode<Type> * leftChild , * rightChild ; //左子指针、右子指针 Type data;//数据元素 }
叉链表结构的二叉树的类定义 template <class Type> class Binary Tree i public Binary tree():roo(NULL){}创建一棵空二叉树 Binary Tree( Type value ) RefValue(value), root(NULL&) virtual~ Binary Tree(){ destroy(root)}删除一棵二叉树 virtual int IsEmpty(){ return root=NUL;}判树空 virtual Bin TreeNode< type>* Parent( Bin TreeNode<type> *current) return root- NULL root current? NULL Parent(root, current);}求* current结点的父结点指针 virtual Bin TreeNode< Type>* Left Child( Bin TreeNode<type s current)i return current != NULL? Current-left Child NULL;I 求* current结点的左子结点指针 virtual BinTreeNode< Type>* rightChild( bin TreeNode<type> s current) return current !=NULL Current->rightChild NULL;) /)* current结点的右子结点指针 2021220
2021/2/20 8 二叉链表结构的二叉树的类定义 template <class Type> class BinaryTree { public: BinaryTree( ) : root(NULL) { }//创建一棵空二叉树 BinaryTree( Type value ) : RefValue(value) , root(NULL) { } virtual ~ BinaryTree( ) { destroy ( root ) }//删除一棵二叉树 virtual int IsEmpty( ) { return root == NULL ;}//判树空 virtual BinTreeNode<Type> * Parent( BinTreeNode<Type> *current ) { return root == NULL || root == current ?NULL : Parent( root , current ) ;}//求*current 结点的父结点指针 virtual BinTreeNode<Type> * LeftChild( BinTreeNode<Type> * current ) { return current != NULL ? Current ->leftChild :NULL ; } //求 *current 结点的左子结点指针 virtual BinTreeNode<Type> * RightChild( BinTreeNode<Type> * current ) { return current != NULL ? Current ->rightChild :NULL ; } //求*current 结点的右子结点指针
virtual int Insert(( const Type&item)/插入值为item的新结点 virtual int find( const Type&item) const/查找值为item的结点 const Bin TreeNode< Type>* Getroot() const{ return root;}/求根结点的指针 friend istream operator >> istream in, BinTreeNode<Type>& Tree ∥重载操作:输入数据元素并建立一棵二叉树Tree friend ostream operator << ostream out, Bin Tree Node<Type> tree ); ∥重载操作:输出一棵二叉树Tro Private BinTreeNode<Type>*root/根结点指针 Type Ref value;/数据输入结束标志,仅用于输入 BinTreeNode<Type>* Parent( BinTreeNode<Type> x start BinTreeNode<type>*current /)求 start树中* current结点的父结点指针 int Insert( BinTreeNode<Type>*& current, const Type item ) / current树中插入值为item的新结点 void Traverse ( Bin Tree Node<Type> current ostream out)const )历输出 current二叉树 int Find( BinTreeNode<Type>* current, const Type item)const current树中查找值为item的结点 void destroy(( binTreeNode<Type> s current /删除 current树的所有结点 2021220
2021/2/20 9 virtual int Insert( const Type & item );//插入值为 item 的新结点 virtual int Find( const Type & item ) const ;//查找值为 item 的结点 const BinTreeNode<Type> * GetRoot( ) const { return root ; } //求根结点的指针 friend istream & operator >> ( istream & in , BinTreeNode<Type> & Tree ); //重载操作：输入数据元素并建立一棵二叉树 Tree friend ostream & operator << ( ostream & out , BinTreeNode<Type> & Tree ) ; //重载操作：输出一棵二叉树Tree Private: BinTreeNode<Type> * root;//根结点指针 Type RefValue;//数据输入结束标志，仅用于输入 BinTreeNode<Type> * Parent( BinTreeNode<Type> * start, BinTreeNode<Type> * current ); //求 start 树中 *current 结点的父结点指针 int Insert( BinTreeNode<Type> * & current, const Type & item ); //在 current 树中插入值为 item 的新结点 void Traverse(BinTreeNode<Type> * current ,ostream & out ) const; //遍历输出 current 二叉树 int Find ( BinTreeNode<Type> * current, const Type & item ) const ; //在 current 树中查找值为 item 的结点 void destroy(( BinTreeNode<Type> * current ); //删除 current 树的所有结点 }
叉树的基本操作 (1)初始化操作- 般由构造函数实现 (2)建立一棵二叉树 (3)撤销一棵二叉树—可以由析构函数实现 (4)插入一个新结点 (5)删除一个结点 (6)查找 (7)判树空 (8)读取结点数据 (9)修改结点数据 (10)求二叉树的某一或某些性能(如结点数、高度、平衡度等) (11)求根结点、父结点、左子结点、右子结点等结点的指针 (12)调整一棵二叉树,优化某一或某些性能 (13)二叉树遍历操作 (14)其他操作 2021220
2021/2/20 10 二叉树的基本操作 （1）初始化操作——一般由构造函数实现 （2）建立一棵二叉树 （3）撤销一棵二叉树——可以由析构函数实现 （4）插入一个新结点 （5）删除一个结点 （6）查找 （7）判树空 （8）读取结点数据 （9）修改结点数据 （10）求二叉树的某一或某些性能（如结点数、高度、平衡度等） （11）求根结点、父结点、左子结点、右子结点等结点的指针 （12）调整一棵二叉树，优化某一或某些性能 （13）二叉树遍历操作 （14）其他操作