|
#include<stack> using namespace std;
typedef int T; // 值类型
// 节点定义 struct node { T val; node *left,*right; node(const T& val):val(val),left(NULL),right(NULL){ } }; typedef node* nodePtr; // 节点指针
// 二叉搜索树实现 class BST { public: BST(nodePtr r=NULL):root(r){ } // 二叉树插入元素 void insert(const T& val) { if(root==NULL) { root=new node(val);return; } //cur为当前节点 pre为cur的 前驱节点 node *cur=root,*pre; //遍历找到合适的插入位置 while(cur) { pre=cur; // 记录前驱节点 cur=cur->val>val?cur->left:cur->right; // 前进 } //根据前驱节点的值 判断插入左还是右 if(pre->val>val) pre->left=new node(val); else pre->right=new node(val); } // 二叉树查找元素 nodePtr find(const T& val) { nodePtr cur=root; while(cur) { if(cur->val==val) return cur; cur=cur->val>val?cur->left:cur->right; // 前进 } return NULL; } // 删除指定元素 void del(const T& val) { //cur为当前节点 pre为cur的 前驱节点 nodePtr cur=root,pre; while(cur) { if(cur->val==val) break; pre=cur; cur=cur->val>val?cur->left:cur->right; // 前进 } // 如果未找到节点 if(!cur) return;
// 如果是叶子节点 直接删除即可并改变前驱节点的指向为空 if(cur->left==NULL&&cur->right==NULL) { if(cur==root) // 如果刚好是根节点 root=NULL; else if(pre->left==cur) // 左叶子 pre->left=NULL; else // 右叶子 pre->right=NULL; delete cur; } // 如果是单儿子节点 接删除即可并改变前驱节点的指向为儿子节点 else if(cur->left==NULL||cur->right==NULL) { if(cur==root) // 根节点 root=cur->left==NULL?cur->right:cur->left; else if(pre->left==cur) // 左儿子 pre->left=cur->left==NULL?cur->right:cur->left; else // 右儿子 pre->right=cur->left==NULL?cur->right:cur->left; delete cur; } // 双儿子节点 else { //找到左儿子中最大值 pre=cur; nodePtr p=pre->left; //最大值在最右边 while(p->right) { pre=p; p=p->right; } cur->val=p->val; if(pre->left==p) pre->left=NULL; else pre->right=NULL; delete p; } } /* 非递归前序遍历 用栈实现 对于任一结点P： 1)访问结点P，并将结点P入栈; 2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P; 3)直到P为NULL并且栈为空，则遍历结束。 */ void PreOrderPrint() const{ if(root==NULL) return; stack<nodePtr> S; nodePtr cur=root; while(cur||!S.empty()) { while(cur) { cout<<cur->val<<","; S.push(cur); cur=cur->left; } if(!S.empty()) { cur=S.top();S.pop(); cur=cur->right; } } cout<<endl; } /* 非递归中序遍历 用栈实现 对于任一结点P， 1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理； 2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子； 3)直到P为NULL并且栈为空则遍历结束 */ void InOrderPrint() const{ if(root==NULL) return; stack<nodePtr> S; nodePtr cur=root; while(cur||!S.empty()) { while(cur) { S.push(cur); cur=cur->left; } if(!S.empty()) { // 访问当前节点并右子树入栈 cur=S.top();S.pop(); cout<<cur->val<<","; cur=cur->right; } } cout<<endl; } /* 非递归 后序遍历 用栈实现 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。 若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。 */ void PostOrderPrint() const { if(root==NULL) return; stack<nodePtr> S; nodePtr cur,pre=NULL; //当前节点和前一次访问的节点 S.push(root); while(!S.empty()) { cur=S.top(); if((cur->left==NULL&&cur->right==NULL)||(pre!=NULL&&(pre==cur->left||pre==cur->right))) { cout<<cur->val<<","; //如果当前结点没有孩子结点或者孩子节点都已被访问过 S.pop(); pre=cur; } else { if(cur->right!=NULL) S.push(cur->right); if(cur->left!=NULL) S.push(cur->left); } } } private : nodePtr root; // 根节点 };
int main(int argc, char* argv[]) { BST bst; bst.insert(12);bst.insert(2);bst.insert(1);bst.insert(122);bst.insert(6); //bst.insert(11);bst.insert(3);bst.insert(66);bst.insert(30); //bst.del(12); bst.InOrderPrint(); bst.PreOrderPrint(); bst.PostOrderPrint(); return 0; } |