叶老师版数据结构二叉树各种函数.doc

/二叉树类#include BinaryNode.h /二叉树的二叉链表结点类#include SeqStack.h /顺序栈#include LinkedStack.h /链式栈#include SeqQueue.h /顺序循环队列/#include LinkedQueue.h /链式队列 template class BinaryTree /二叉树类 public: BinaryNode *root; /指向根结点 BinaryTree(); /构造空二叉树 BinaryTree(T prelist, int n); /以标明空子树的先根序列构造一棵二叉树 BinaryTree(T prelist, T inlist, int n); /以先根和中根序列构造二叉树 BinaryTree(); /析构函数 bool isEmpty(); /判断是否空二叉树 void preOrder(); /先根次序遍历二叉树 void inOrder(); /中根次序遍历二叉树 void postOrder(); /后根次序遍历二叉树 int count(); /返回二叉树的结点个数 int height(); /返回二叉树的高度 BinaryNode* search(T value); /查找首次出现的值为value的结点 BinaryNode* getParent(BinaryNode *node); /返回node结点的父母结点 BinaryNode* insert(BinaryNode *p, T value, bool leftChild=true); /插入value作为p结点的孩子 void remove(BinaryNode *p, bool leftChild=true); /删除p结点的左或右子树 void printGList(); /以广义表表示输出二叉树 void inOrderTraverse(); /中根次序遍历二叉树的非递归算法 void levelOrder(); /按层次遍历二叉树 private: void preOrder(BinaryNode *p); /先根次序遍历以p结点为根的子树 void inOrder(BinaryNode *p); /中根次序遍历以p结点为根的子树 void postOrder(BinaryNode *p); /后根次序遍历以p结点为根的子树 void destroy(BinaryNode *p); /撤销二叉树 BinaryNode* create(T prelist, int n, int &i); /以标明空子树的先根遍历序列创建子树 BinaryNode* create(T prelist, T inlist, int preStart, int inStart, int n); /以先根和中根序列创建一棵子树 int count(BinaryNode *p); /返回以p结点为根的子树结点个数 int height(BinaryNode *p); /返回以p结点为根的子树高度 BinaryNode* search(BinaryNode *p, T value); /在以p为根的子树中查找首次出现的值为value的结点 BinaryNode* getParent(BinaryNode *p, BinaryNode *node); void printGList(BinaryNode *p); /以广义表表示输出以p结点为根的子树/第6章习题 public: void leaf(); /遍历输出叶子结点 int countLeaf(); /返回二叉树的叶子结点数 bool replace(T old, T value); /将首次出现的值为old结点值替换为value void replaceAll(T old, T value); /将值为old的结点全部替换为value int operator=(BinaryTree &bitree); /比较两棵二叉树是否相等，重载运算符= BinaryTree(BinaryTree &bitree); /由已知的bitree构造二叉树 void preOrderTraverse(); /先根次序遍历二叉树的非递归算法 bool isSorted(); /判断一棵二叉树是否为二叉排序树 private: void leaf(BinaryNode *p); /输出以p结点为根的子树的所有叶子结点 int countLeaf(BinaryNode *p); /返回以p结点为根的子树的叶子结点个数 void replaceAll(BinaryNode *p, T old, T value); /在以p为根的子树中实现全部替换 bool equals(BinaryNode *p, BinaryNode *q); /判断以p和q结点为根的两棵子树是否相等 BinaryNode* copy(BinaryNode *p); /复制以p根的子二叉树 /第8章习题 bool isSorted(BinaryNode* p);template BinaryTree:BinaryTree() /构造空二叉树 root = NULL;template bool BinaryTree:isEmpty() /判断是否空二叉树 return root=NULL;/3. 二叉树的先根、中根和后根次序遍历算法template void BinaryTree:preOrder() /先根次序遍历二叉树 cout先根次序遍历二叉树: ; preOrder(root); /调用先根次序遍历二叉树的递归函数 coutendl; template void BinaryTree:preOrder(BinaryNode *p) /先根次序遍历以p结点为根的子树，递归函数 if (p!=NULL) /若二叉树不空 coutdataleft); /按先根次序遍历当前结点的左子树，递归调用 preOrder(p-right); /按先根次序遍历当前结点的右子树，递归调用 template void BinaryTree:inOrder() /中根次序遍历二叉树 cout中根次序遍历二叉树: ; inOrder(root); /调用中根次序遍历二叉树的递归函数 coutendl; template void BinaryTree:inOrder(BinaryNode *p) /中根次序遍历以p结点为根的子树，递归函数 if (p!=NULL) inOrder(p-left); coutdataright); template void BinaryTree:postOrder() /后根次序遍历二叉树 cout后根次序遍历二叉树: ; postOrder(root); /调用后根次序遍历二叉树的递归函数 coutendl; template void BinaryTree:postOrder(BinaryNode *p) /后根次序遍历以p结点为根的子树，递归函数 if (p!=NULL) postOrder(p-left); postOrder(p-right); coutdata ; /4. 基于遍历的操作template BinaryTree:BinaryTree() /析构函数 cout撤销二叉树: ; destroy(root); coutendl;template void BinaryTree:destroy(BinaryNode *p) /撤销以p结点为根的子树，后根次序遍历 if (p!=NULL) destroy(p-left); destroy(p-right); coutdata ; /显示撤销结点的次序 delete p; /【例6.1】 构造并遍历二叉树。template int BinaryTree:count() /返回二叉树的结点个数 return count(root);template int BinaryTree:count(BinaryNode *p) /返回以p结点为根的子树结点个数 if (p=NULL) return 0; else return 1+count(p-left)+count(p-right);template int BinaryTree:height() /返回二叉树的高度 return height(root);template int BinaryTree:height(BinaryNode *p) /返回以p结点为根的子树高度，后根次序遍历 if (p!=NULL) int lh = height(p-left); /求左子树的高度 int rh = height(p-right); return (lh=rh) ? lh+1 : rh+1; return 0;template BinaryNode* BinaryTree:search(T value) /查找首次出现的值为value结点 return search(root, value);template BinaryNode* BinaryTree:search(BinaryNode *p, T value) /在以p为根的子树中查找 /先根次序遍历查找值为value的结点，返回首次出现结点指针，若未找到返回NULL BinaryNode *find=NULL; /记载找到结点 if (p!=NULL) if (p-data=value) return p; /查找成功，返回结点指针 find = search(p-left, value); /在左子树中查找，find指向找到结点，递归调用 if (find=NULL) /若在左子树中未找到 find = search(p-right, value); /则继续在右子树中查找，递归调用 return find; /返回查找结果template BinaryNode* BinaryTree:getParent(BinaryNode *node) /返回node结点的父母结点指针 /若空树、未找到或node为根，返回NULL if (root=NULL | node=NULL | node=root) return NULL; return getParent(root, node);template BinaryNode* BinaryTree:getParent(BinaryNode *p, BinaryNode *node) /在以p为根的子树中查找并返回node结点的父母结点指针 BinaryNode *find=NULL; if (p!=NULL) if (p-left=node | p-right=node) return p; find = getParent(p-left, node); if (find=NULL) find = getParent(p-right, node); return find;/5. 构造二叉树template BinaryTree:BinaryTree(T prelist, T inlist, int n) /以先根和中根序列构造二叉树 /n指定序列长度 root = create(prelist, inlist, 0, 0, n);template BinaryNode* BinaryTree:create(T prelist, T inlist, int preStart,int inStart, int n) /以先根和中根序列创建一棵子树，子树根结点是prelisti，返回根结点指针 BinaryNode *p=NULL; if (n0) T elem=prelistpreStart; /根结点值 p = new BinaryNode(elem); /创建结点 int i=0; while (ileft = create(prelist, inlist, preStart+1, inStart, i); /创建左子树 p-right = create(prelist, inlist, preStart+i+1, inStart+i+1, n-1-i);/创建右子树 return p;template BinaryTree:BinaryTree(T prelist, int n) /以标明空子树的先根序列构造二叉树 int i=0; root=create(prelist, n, i);template BinaryNode* BinaryTree:create(T prelist, int n, int &i) /以标明空子树的先根次序遍历序列创建一棵子树，子树根结点是prelisti，返回根结点指针 BinaryNode *p=NULL; if (in) T elem = prelisti; i+; if (elem!=NULL) /不能elem!=，因为T不一定是char p = new BinaryNode(elem); /创建结点 p-left = create(prelist, n, i); /创建左子树 p-right = create(prelist, n, i); /创建右子树 return p;/【例6.2】 输出二叉树中指定结点的所有祖先结点。/【例6.3】 二叉树的广义表表示。template void BinaryTree:printGList() /以广义表表示输出二叉树 printGList(root); coutendl;template void BinaryTree:printGList(BinaryNode *p) /以广义表表示输出以p结点为根的子树 if (p=NULL) cout; else coutdata; if (p-left!=NULL | p-right!=NULL) coutleft); coutright); cout); /6. 二叉树的插入和删除操作template BinaryNode* BinaryTree:insert(BinaryNode *p, T value, bool leftChild) /插入value作为p结点的孩子 /若leftChild=true，插入结点作为左孩子，否则作为右孩子 BinaryNode *q=NULL; if (p!=NULL) if (leftChild) q = new BinaryNode(value, p-left, NULL); p-left = q; else q = new BinaryNode(value, NULL, p-right); p-right = q; return q; template void BinaryTree:remove(BinaryNode *p, bool leftChild) /删除p结点的左或右子树 /若leftChild为true，删除左子树，否则删除右子树 if (p!=NULL) if (leftChild) destroy(p-left); /撤销左子树 p-left = NULL; else destroy(p-right); /撤销右子树 p-right = NULL; /7. 二叉树遍历的非递归算法template void BinaryTree:preOrderTraverse() /先根次序遍历二叉树的非递归算法 cout先根次序遍历（非递归）： ; SeqStackBinaryNode* stack; /创建一个空栈 BinaryNode *p = root; while (p!=NULL | !stack.isEmpty() /p非空或栈非空时 if (p!=NULL) coutdataleft; /进入左子树 else /p为空且栈非空时 p = stack.pop(); /p指向出栈结点 p = p-right; /进入右子树 coutendl; template void BinaryTree:inOrderTraverse() /中根次序遍历二叉树的非递归算法 cout中根次序遍历（非递归）： ; LinkedStackBinaryNode* stack; /创建一个空栈 BinaryNode *p = root; while (p!=NULL | !stack.isEmpty() /p非空或栈非空时 if (p!=NULL) stack.push(p); /p结点入栈 p = p-left; /进入左子树 else /p为空且栈非空时 p = stack.pop(); /p指向出栈结点 coutdataright; /进入右子树 coutendl; /后根次序未写/8. 二叉树的层次遍历template void BinaryTree:levelOrder() /按层次遍历二叉树 cout层次遍历： ; SeqQueueBinaryNode* que; /创建一个空队列/ LinkedQueueBinaryNode* que; /创建一个空队列 BinaryNode *p=root; while (p!=NULL) coutdataleft!=NULL) que.enqueue(p-left); /p的左孩子结点入队 if (p-right!=NULL) que.enqueue(p-right); /p的右孩子结点入队 if (!que.isEmpty() p = que.dequeue(); /p指向出队结点 else p = NULL; coutendl;/第6章习题template void BinaryTree:leaf() /遍历输出叶子结点 leaf(root);template void BinaryTree:leaf(BinaryNode *p) /输出以p结点为根的子树的所有叶子结点 /先根次序遍历算法，中根、后根次序遍历算法也可，结果一样 if (p!=NULL) if (p-left=NULL & p-right=NULL) coutdataleft); leaf(p-right); template int BinaryTree:countLeaf() /返回二叉树的叶子结点数 return countLeaf(root);template int BinaryTree:countLeaf(BinaryNode *p) /返回以p结点为根的子树的叶子结点个数 if (p=NULL) return 0; if (p-left=NULL & p-right=NULL) return 1; return countLeaf(p-left)+countLeaf(p-right);template bool BinaryTree:replace(T old, T value) /将首次出现的值为old结点值替换为value BinaryNode *find = search(old); /查找值为old的结点 if (find!=NULL) find-data = value; /替换结点元素值 return find!=NULL; template void BinaryTree:replaceAll(T old, T value) /将值为old的结点全部替换为value replaceAll(root, old, value);template void BinaryTree:replaceAll(BinaryNode *p, T old, T value) /在以p为根的子树中实现全部替换 if (p!=NULL) if(p-data=old) p-data = value; /替换 replaceAll(p-left, old, value); replaceAll(p-right, old, value); template int BinaryTree:operator=(BinaryTree &bitree) /比较两棵二叉树是否相等，重载运算符= return equals(this