《二叉树及二叉树的操作》由会员分享，可在线阅读，更多相关《二叉树及二叉树的操作（4页珍藏版）》请在金锄头文库上搜索。
1、二叉树及二叉树的操作#includeusing namespace std;templateclass BTNodepublic:BTNode() lchild = rchild = NULL;BTNode(const T& X)element = x;lchild = rchild = NULL;BTNode(const T& x,BTNode *l,BTNode *r)element = x;lchild = l;rchild = r;T element;BTNode *lchild,*rchild;templateclass BinaryTreepublic:BinaryTree()ro
2、ot = NULL;BinaryTree();bool IsEmpty() const;void Clear();bool Root(T& x) const;void MakeTree(const T& x,BinaryTree& left,BinaryTree& right);void BreakTree(T& x,BinaryTree& left,BinaryTree& right);void PreOrder(void (*Visit)(T& x)先序遍历void LevelOrder(void (*Visit)(T& x)后续遍历void HierarchyBiTree(BiTree
3、Root)层次遍历protected:BTNode *root;private:void Clear(BTNode *t);void PreOrder(void (*Visit)(T& x),BTNode *t);void LevelOrder(void (*Visit)(T& x),BTNode *t);；templateBinaryTree:BinaryTree()Clear();templatebool IsEmpty()if(!root)return true;elsereturn false;templatevoid BinaryTree:Clear()if(root)delete
4、root;PreOrder(Visit,root-lchild);PreOrder(Visit,root-rchild);root = NULL;templatebool BinaryTree:Root(T& x) const if(root)x = root-element;elsereturn false;templatevoid BinaryTree:MakeTree(const T& x,BinaryTree& left,BinaryTree& right) if(root|&left=&right)return;root = new BTNode(x,left.root,right.
5、root);left.root = right.root = NULL;templatevoid BinaryTree:BreakTree(T& x,BinaryTree& left,BinaryTree& right)if(!root|&left=&right|left.root|right.root)return;x = root-element;left.root = root-lchild;right.root = root-rchild;delete root;root = NULL;templatevoid BinaryTree:PreOrder(void (*Visit)(T&
6、x)PreOrder(Visit,root);templatevoid BinaryTree:PreOrder(void (*Visit)(T& x),BTNode *t)if(t)Visit(t-element);PreOrder(Visit,t-lchild);PreOrder(Visit,t-rchild);void Visit(char& x);int main()BinaryTree a,b,x,y,z; char e=A;y.MakeTree(E,a,b);z.MakeTree(F,a,b);x. MakeTree(C,y,z);y.MakeTree(D,a,b);z.MakeTr
7、ee(B,y,x);z.PreOrder(Visit);z.BreakTree(e,y,x);x. PreOrder(Visit);y.PreOrder(Visit);return 0;templatevoid HierarchyBiTree(BiTree Root)LinkQueue *Q; /保存当前节点的左右孩子的队列if (Root = NULL) return ; /树为空则返回BiNode *p = Root;临时保存树根Root到指针p中Visit(p-data); / 访问根节点if (p-lchild) EnQueue(Q, p-lchild); / 若存在左孩子，左孩子进队列if (p-rchild)EnQueue(Q, p-rchild); / 若存在右孩子，右孩子进队列while (!QueueEmpty(Q) DeQueue(Q, p); / 出队列Visit(p-data);/访问当前节点if (p-lchild) if (p-rchild) EnQueue(Q, p-lchild); /若存在左孩子，左孩子进队列EnQueue(Q, p-rchild); /若存在右孩子，右孩子进队列
