//DSW Algorithm
//我先放二叉树的定义上来，代码丑陋，不要见怪。

#ifndef BSTREE_H_ #define BETREE_H_ /////////////////////////////////////////////////////////////// // // File: BSTree.h // // This headfile defines BST class to test BSTree. // // By tankeryang. // // 2015, Dec 2 // /////////////////////////////////////////////////////////////// #include #include #include using namespace std; template class Stack:public stack{}; template class Queue:public queue{ public: T dequeue(){ T tmp = front(); queue::pop(); return tmp; }; void enqueue(T item){ push(item); }; }; class BSTNode{ public: int item; BSTNode *lchild, *rchild; int level; BSTNode(){ lchild = rchild = NULL; }; BSTNode(int i){ item = i; lchild = rchild = NULL; }; }; class BSTree:public BSTNode{ protected: BSTNode *root; int countOfNode; int levelOfTree; public: BSTree(){ root = NULL; countOfNode = 0; levelOfTree = 0; }; ~BSTree(){}; int getLevelOfTree(); void insert(int); void breadthFirst(); //DSW algorithm void rotateRight(BSTNode *); void creatBackbone(); void creatPerfectTree(); //Inorder recurrence algorithm void inOrder(); void inRecurrence(BSTNode *); ////// void visit(BSTNode *node) { std::cout << node->item << ' '; }; }; #endif

//接下来放DSW的三个函数的定义
//调试的时候，会出现死循环，原因是出在rotateRight(BSTNode *)
//函数，可能判断条件有问题，还有下面的creatPerfectTree()也有问
//题，望高手赐教。要是觉得在下代码实现的太烂，希望能详细说说您的
//理解，不胜感激。

// DSW Algorithm void BSTree::rotateRight(BSTNode *pnode){ // Rotate the left node to the right link list. if(pnode->lchild != NULL) { BSTNode *tmp = pnode->lchild; pnode->lchild = tmp->rchild; tmp->rchild = pnode; pnode = tmp; } else if (pnode->lchild == NULL && pnode->rchild->lchild != NULL) { BSTNode *flag = pnode; pnode = pnode->rchild; BSTNode *tmp = pnode->lchild; pnode->lchild = tmp->rchild; tmp->rchild = pnode; flag->rchild = tmp; pnode = flag->rchild; } else pnode = pnode->rchild; }; void BSTree::creatBackbone(){ BSTNode *pnode = root; while(pnode!=NULL) rotateRight(pnode); }; void BSTree::creatPerfectTree(){ BSTNode *tmp1=root, *tmp2=tmp1->rchild->rchild; while(tmp1!=NULL){ if(tmp2!=NULL && tmp2->rchild!=NULL){ tmp1->rchild = tmp1->rchild->lchild; tmp1->rchild->lchild = tmp1; tmp1 = tmp1->rchild; tmp1->rchild = tmp1->rchild->rchild; tmp2->rchild->lchild = tmp2; tmp2->rchild = NULL; tmp2 = tmp1->rchild->rchild; } else break; } };