2023年6月22日发(作者：)

数据结构-⼆叉树（2）链表法和⼴义表法表⽰⼆叉树数组表⽰法⽤于完全⼆叉树的存储表⽰⾮常有效，但表⽰⼀般⼆叉树，尤其是形态剧烈变化的⼆叉树，存储空间的利⽤很不理想使⽤⼆叉链表表⽰⼆叉树:#include using namespace std;template struct BinTreeNode{ T data; BinTreeNode *leftChild,*rightChild; BinTreeNode():leftChild(NULL),rightChild(NULL){} BinTreeNode(T x,BinTreeNode *l=NULL,BinTreeNode *r=NULL):data(x),leftChild(l),rightChild(r){};};template class BinaryTree{public: BinaryTree():root(NULL){} BinaryTree(T value):RefValue(value),root(NULL){} BinaryTree(const BinaryTree& s){root=Copy();} //复制构造函数 ~BinaryTree(){destroy(root);} bool IsEmpty(){return(root==NULL);} BinTreeNode *Parent(BinTreeNode *current){ //返回⽗结点 return(root==NULL||root==current)?NULL:Parent(root,current); } BinTreeNode *LeftChild(BinTreeNode *current){ //返回左⼦⼥ return(current!=NULL)?current->leftChild:NULL; } BinTreeNode *RightChild(BinTreeNode *current){ //返回右⼦⼥ return(current!=NULL)?current->rightChild:NULL; } int Height(){return Height(root);} //返回树⾼度 int Size(){return Size(root);} //返回结点数 BinTreeNode *getRoot()const{return root;} //取根 void preOrder(void (*visit)(BinTreeNode *p)){preOrder(root,visit);} //对根结点前序遍历 void InOrder(void (*visit)(BinTreeNode *p)){InOrder(root,visit);} //对根结点中序遍历 void postOrder(void (*visit)(BinTreeNode *p)){postOrder(root,visit);} //对根结点后序遍历 void levelOrder(void (*visit)(BinTreeNode *p)); //层次序遍历 int Insert(const T& item); //插⼊新元素 BinTreeNode *Find(T& item)const; //搜索protected: BinTreeNode *root; //⼆叉树根指针 T RefValue; //数据输⼊停⽌标志，⽤⼴义表表⽰⼆叉树的时候⽤ void CreateBinTree(istream& in,BinTreeNode *subTree); //从⽂件读⼊建树 bool Insert(BinTreeNode *subTree,const T&x); //插⼊ void destroy(BinTreeNode *subTree); //删除 BinTreeNode *Copy(BinTreeNode *orignode); //复制 int Height(BinTreeNode *subTree)const; //返回树⾼度 int Size(BinTreeNode *subTree)const; //返回结点数 BinTreeNode *Parent(BinTreeNode *subTree,BinTreeNode *current); //从结点subTree开始搜索结点current的⽗结点 BinTreeNode *Find(BinTreeNode *subTree,const T& x)const; //搜寻值为x的结点 void Traverse(BinTreeNode *subTree,ostream& out); //前序遍历输出 void preOrder(BinTreeNode* subTree, void (*visit)(BinTreeNode *p)); //对p结点前序遍历 void InOrder(BinTreeNode* subTree, void (*visit)(BinTreeNode *p)); //中序遍历 void postOrder(BinTreeNode* subTree, void (*visit)(BinTreeNode *p)); //后序遍历 friend istream& operator>>(istream& in,BinaryTree& Tree); friend ostream& operator<<(ostream& out,BinaryTree& Tree); friend bool operator==(const BinaryTree& s,const BinaryTree& t); bool equal(BinTreeNode *a,BinTreeNode *b)const;};template void BinaryTree::destroy(BinTreeNode *subTree){ //私有函数，若指针subTree不为空，则删除根为subTree的⼦树 if(subTree!=NULL){ destroy(subTree->leftChild); destroy(subTree->rightChild); delete subTree; }}template BinTreeNode *BinaryTree::Parent(BinTreeNode *subTree,BinTreeNode *current){ //私有函数，从结点subTree开始搜索结点current的⽗结点，返回⽗结点地址或者NULL if(subTree==NULL) return NULL; if(subTree->leftChild==current || subTree->rightChild==current) return subTree; BinTreeNode *p; if((p=Parent(subTree->leftChild,current))!=NULL) return p; //使⽤p=Parent(subTree->leftChild,current)递归在左⼦树中搜索，p==NULL则说明搜索失败 else return Parent(subTree->rightChild,current);}template void BinaryTree::Traverse(BinTreeNode *subTree,ostream& out){ //私有函数，搜索并前序输出根为subTree的⼆叉树 if(subTree!=NULL){ out<data<<''; Traverse(subTree->leftChild,out); //递归搜索并输出subTree的左⼦树 Traverse(subTree->rightChild,out); //递归搜索并输出subTree的右⼦树 }}template istream& operator>>(istream& in,BinaryTree& Tree){ //重载操作，输⼊并建⽴⼀颗⼆叉树Tree,in是输⼊流对象 BinTree(in,); //此处友元函数不能直接访问类的成员函数 return in;}template ostream& operator<<(ostream& out,BinaryTree& Tree){ //重载操作，输出⼀颗⼆叉树Tree，out是输出流对象 out<<"⼆叉树的前序遍历n"; se(,out); //从根开始输出 out<bool operator==(const BinaryTree& s,const BinaryTree& t){ //判断两棵⼆叉树的等价性，它需要是BinaryTree类的友元函数 return (,); //此处s是const对象，equal应该是const⽅法}template void BinaryTree::preOrder(BinTreeNode *subTree, void (*visit)(BinTreeNode *)) { if(subTree!=NULL){ visit(subTree); preOrder(subTree->leftChild,visit); preOrder(subTree->rightChild,visit); }}template void BinaryTree::InOrder(BinTreeNode *subTree, void (*visit)(BinTreeNode *)) { //递归函数，此算法按照中序次序遍历以subTree为根的⼦树 if(subTree!=NULL){ InOrder(subTree->leftChild,visit); visit(subTree); InOrder(subTree->rightChild,visit); }}template void BinaryTree::postOrder(BinTreeNode *subTree, void (*visit)(BinTreeNode *)) { if(subTree!=NULL){ postOrder(subTree->leftChild,visit); postOrder(subTree->rightChild,visit); visit(subTree); }}template int BinaryTree::Size(BinTreeNode *subTree)const{ //私有函数，介绍以subTree为根的⼆叉树的结点个数 if(subTree==NULL) return 0; else return 1+Size(subTree->leftChild)+Size(subTree->rightChild);}template int BinaryTree::Height(BinTreeNode *subTree)const{ //私有函数，计算以subTree为根的⼆叉树的深度 if(subTree==NULL) return 0; else{ int i=Height(subTree->leftChild); int j=Height(subTree->rightChild); return(iBinTreeNode *BinaryTree::Copy(BinTreeNode *orignode){ //私有函数，这个函数返回⼀个指针，给出⼀个以orignode为根的⼆叉树的副本 if(orignode==NULL) return NULL; BinTreeNode *temp=new BinTreeNode; temp->data=orignode->data; temp->leftChild=Copy(orignode->leftChild); //此处注意不能直接=，因为需要建⽴新结点再赋值 temp->rightChild=Copy(orignode->rightChild); return temp;}template bool BinaryTree::equal(BinTreeNode *a,BinTreeNode *b)const{ //如果a和b的⼦树不同，则函数返回false，否则函数返回true,它需要是BinTreeNode类的友元函数 if(a==NULL && b==NULL) return true; if(a!=NULL && b!=NULL && a->data==b->data && equal(a->leftChild,b->leftChild) && equal(a->rightChild,b->rightChild)) return true; else return false;}template void BinaryTree::CreateBinTree(istream& in,BinTreeNode *subTree){ //私有函数，以前序遍历⽅式递归建⽴⼆叉树 T item; if(!()){ //读不到输⼊流时()为真 in>>item; subTree=new BinTreeNode(item); if(subTree==NULL){ cerr<<"分配存储错误！"<leftChild); CreateBinTree(in,subTree->rightChild); } else subTree=NULL;}⼆叉链表找到⽗结点很困难，可以使⽤三叉链表输⼊输出⼆叉树时，可以输⼊⼀个⼴义表形式的⼆叉树，此时需要⽤栈保存字符。栈的最⼤深度==⼆叉树的⾼度==⼴义表表⽰中圆括号嵌套的最⼤层数加1（根结点）template void CreateBinTree(istream& in,BinTreeNode* &BT){ //从输⼊流in输⼊⼆叉树的⼴义表表⽰建⽴对应的⼆叉链表,依次从保存⼴义表的字符串ls中输⼊字符 Stack *> s; BT=NULL; //置空⼆叉树表 BinTreeNode *p,*t; int k; //⽤k作为处理左右⼦树标志 char ch; in>>ch; while(ch!=RefValue){ //逐个字符处理 switch(ch){ case '(':(p);k=1;break; //输⼊若是左扩号，则表明⼦表的开始，将根结点⼊栈，K置为1 case ')':(t);break; //输⼊若是右括号，则表明⼦表结束，将根结点出栈 case ',':k=2;break; //遇到的是逗号，则表⽰以左⼦⼥为根的⼦树处理完毕 default:p=new BinTreeNode(ch); //输⼊若是字母，为它建⽴新结点，根据k的值将其链接到⽗节点上 if(BT==NULL) BT=p; else if(k==1){ (t); t->leftChild=p; //链⼊*t的左⼦⼥ } else{ (t); t->rightChild=p; //链⼊*t的右⼦⼥ } } in>>ch; }}template void PrintBTree(BinTreeNode *BT){ //以⼴义表的形式输出⼆叉树 if(BT!=NULL){ cout<data; if(BT->leftChild!=NULL||BT->rightChild!=NULL){ cout<<'('; PrintBTree(BT->leftChild); cout<<','; if(BT->rightChild!=NULL) PrintBTree(BT->rightChild); cout<<')'; } }}