二叉树的链式实现
binaryTree.h
binaryTree.cpp#include"LinkedBinaryTree.h"#include<iostream>#include<stdlib.h>#include"../T3/Stack.h"using namespace std;template<typename T>void BinaryTree<T>::destroy(BinTreeNode<T> *&subTree){ if(subTree!=NULL){ destroy(subTree->leftChild);//递归删除左子树 destroy(subTree->rightChild);//递归删除右子树 delete subTree; }}/* 从subTree向下搜索current的父结点 */template<typename T>BinTreeNode<T>*BinaryTree<T>::Parent(BinTreeNode<T> *subTree, BinTreeNode<T> *current){ if(subTree==NULL) return NULL; if(subTree->leftChild||subTree->rightChild==current) return subTree; BinTreeNode<T> *p; if((p=Parent(subTree->leftChild,current))!=NULL) return p; else return Parent(subTree->rightChild,current);}template<typename T>void BinaryTree<T>::Traverse(BinTreeNode<T> *subTree, ostream &out){ if(subTree!=NULL){ out << subTree->data << ","; Traverse(subTree->leftChild,out); Traverse(subTree->rightChild,out); }}template<typename T>void BinaryTree<T>::createBinTree(istream &in, BinTreeNode<T> *&subTree){ Stack<BinTreeNode<char>*> s; subTree = NULL; BinTreeNode<char> *p,*t; int k; char ch; in >> ch; while(ch!=RefValue){ switch(ch){ case '(': s.Push(p); k=1; break; case ')': s.Pop(t); break; case ',': k=2; break; default: p=new BinTreeNode<char>(ch); if(subTree==NULL) subTree=p; else if(k==1){ s.getTop(t); t->leftChild=p; }else{ s.getTop(t); t->rightChild=p; } } in>>ch; }}template<typename T>void BinaryTree<T>::inOrder(BinTreeNode<T>& subTree, void (*visit)(BinTreeNode<T> *p)){ if(subTree!=NULL){ InOrder(subTree->leftChild,visit); visit(subTree); InOrder(subTree->rightChild,visit); }}template<typename T>void BinaryTree<T>::preOrder(BinTreeNode<T>& subTree, void (*visit)(BinTreeNode<T> *p)){ if(subTree!=NULL){ visit(subTree); PreOrder(subTree->leftChild,visit); PreOrder(subTree->rightChild,visit); }}/* 后序遍历 */template<typename T>void BinaryTree<T>::postOrder(BinTreeNode<T>& subTree, void (*visit)(BinTreeNode<T> *p)){ if(subTree!=NULL){ postOrder(subTree->leftChild,visit); postOrder(subTree->rightChild,visit); visit(subTree); }}template<typename T>int BinaryTree<T>::Size(BinTreeNode<T> *subTree)const{ if(subTree==NULL) return 0; return 1+Size(subTree->leftChild)+Size(subTree->rightChild);}template<typename T>int BinaryTree<T>::Height(BinTreeNode<T> *subTree) const{ if(subTree==NULL) return 0; int leftHeight = Height(subTree->leftChild); int rightHeight = Height(subTree->rightChild); int height = leftHeight>rightHeight?leftHeight:rightHeight; height = height+1; return height;}template<typename T>BinTreeNode<T> *BinaryTree<T>::Copy(BinTreeNode<T> *orignode){ if(orignode==NULL) return NULL; BinTreeNode<T> *temp = new BinTreeNode<T>; temp->data = orignode->data; temp->leftChild = Copy(orignode->leftChild); temp->rightChild = Copy(orignode->rightChild); return temp;}template<typename T>BinaryTree<T>::BinaryTree(BinaryTree<T> &s){ root = Copy(s.root);}//template<typename T>//void BinaryTree<T>::CreateBinTree(ifstream& in,BinTreeNode<T>*& subTree)//{// T item;// if(!in.eof()){// in>>item;// if(item!=RefValue){// subTree = new BinTreeNode<T>(item);// assert(subTree!=NULL);// CreateBinTree(in,subTree->leftChild);// CreateBinTree(in,subTree->rightChild);// }else{// subTree=NULL;// }// }//}template<typename T>void PrintBTree(BinTreeNode<T> *BT){ if(BT!=NULL){ cout << BT->data; if(BT->leftChild!=NULL||BT->rightChild!=NULL){ cout << '('; PrintBTree(BT->leftChild); cout << ','; if(BT->rightChild!=NULL) PrintBTree(BT->rightChild); cout << ')'; } }}
