二叉树的类定义 template <class T> struct BinTreeNode 川二叉树结点类定义 T data; 川数据域 BinTreeNode<T>*leftChild,*rightChild; 川左子女、右子女链域 BinTreeNode /构造逐数 leftChild NULL;rightChild NULL;} BinTreeNode (T x,BinTreeNode<T>*1=NULL, BinTreeNode<T>*r=NULL) data =x;leftChild =1;rightChild =r; }; 26
二叉树的类定义 template <class T> struct BinTreeNode { //二叉树结点类定义 T data; //数据域 BinTreeNode<T> *leftChild, *rightChild; //左子女、右子女链域 BinTreeNode () //构造函数 { leftChild = NULL; rightChild = NULL; } BinTreeNode (T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL) { data = x; leftChild = l; rightChild = r; } }; 26
template <class T> class BinaryTree 川二叉树类定义 public: BinaryTree (root (NULL) /构造函数 BinaryTree(T value):Refvalue(value),root(NULL) {} /构造函数 BinaryTree (BinaryTree<T>&s); /复制构造函数 ~BinaryTree(){Destroy(root);}/∥析构函数 bool IsEmpty O return root ==NULL;} 川判二叉树空否 int Height{return Height(root);}/求树高度 int Size (return Size(root); 川求结点数 27
template <class T> class BinaryTree { //二叉树类定义 public: BinaryTree () : root (NULL) { } //构造函数 BinaryTree (T value) : RefValue(value), root(NULL) { } //构造函数 BinaryTree (BinaryTree<T>& s); //复制构造函数 ～BinaryTree () { Destroy(root); } //析构函数 bool IsEmpty () { return root == NULL;} //判二叉树空否 int Height () { return Height(root); } //求树高度 int Size () { return Size(root); } //求结点数 27
BinTreeNode<T>*Parent (BinTreeNode <T>*t) return (root =NULL root =t)? NULL:Parent(root,t);}/返回双亲结点 BinTreeNode<T>*LeftChild (BinTreeNode<T>*t) return (t!=NULL)t->leftChild NULL; 川返回左子女 BinTreeNode<T>*RightChild (BinTreeNode<T>*t) return (t !NULL)t->rightChild NULL;} 川返回右子女 BinTreeNode<T>*GetRoot (const return root; /取根 28
BinTreeNode<T> *Parent (BinTreeNode <T> *t) { return (root == NULL || root == t) ? NULL : Parent (root, t); } //返回双亲结点 BinTreeNode<T> *LeftChild (BinTreeNode<T> *t) { return (t != NULL)？t->leftChild : NULL; } //返回左子女 BinTreeNode<T> *RightChild (BinTreeNode<T> *t) { return (t != NULL)？t->rightChild : NULL; } //返回右子女 BinTreeNode<T> *GetRoot () const { return root; } //取根 28
void PreOrder (void (*visit)(BinTreeNode<T>*t)) PreOrder (root,visit); 川前序遍历 void InOrder (void (*visit)(BinTreeNode<T>*t)) InOrder (root,visit); 川中序遍历 void PostOrder (void (*visit)(BinTreeNode<T>*t)) PostOrder (root,visit);} 川后序遍历 void LevelOrder (void (*visit)(BinTreeNode<T> *)； 川层次序遍历 int Insert (const T item); /插入新元素 BinTreeNode<T>*Find(T item)const;/搜索 29
void PreOrder (void (*visit) (BinTreeNode<T> *t)) { PreOrder (root, visit); } //前序遍历 void InOrder (void (*visit) (BinTreeNode<T> *t)) { InOrder (root, visit); } //中序遍历 void PostOrder (void (*visit) (BinTreeNode<T> *t)) { PostOrder (root, visit); } //后序遍历 void LevelOrder (void (*visit)(BinTreeNode<T> *t)); //层次序遍历 int Insert (const T item); //插入新元素 BinTreeNode<T> *Find (T item) const; //搜索 29
protected: BinTreeNode<T>*root; 川二叉树的根指针 T RefValue; 川数据输入停止标志 void CreateBinTree (istream&in, BinTreeNode<T>*&subTree); /川从文件读入建树 bool Insert (BinTreeNode<T>*subTree,T&x); /插入 void Destroy (BinTreeNode<T>*subTree); /删除 bool Find (BinTreeNode<T>*subTree,T&x); /查找 30
protected: BinTreeNode<T> *root; //二叉树的根指针 T RefValue; //数据输入停止标志 void CreateBinTree (istream& in, BinTreeNode<T> *& subTree); //从文件读入建树 bool Insert (BinTreeNode<T> *& subTree, T& x); //插入 void Destroy (BinTreeNode<T> *& subTree); //删除 bool Find (BinTreeNode<T> *subTree, T& x); //查找 30