// FindTree2.cpp : 定义控制台应用程序的入口点。
//#include "stdafx.h"
#include <iostream>
#include "stdafx.h"
using namespace std;
typedef struct _TreeNode{ char data; _TreeNode* lChild; _TreeNode* rChild;}TreeNode,*PTreeNode; void PreWalk(TreeNode* p) { if(p == NULL) return; cout<< p->data <<endl; if(p->lChild != NULL) cout<< "left of "<<p->data<<endl; PreWalk( p->lChild); if( p->rChild != NULL) cout<< "righ of " <<p->data<<endl; PreWalk(p->rChild); }void InWalk(TreeNode* p)
{ if(p == NULL) return;if(p->lChild != NULL)
cout<< "left of "<<p->data<<endl; InWalk( p->lChild);cout<<p->data<<endl;
if( p->rChild != NULL)
cout<< "righ of " <<p->data<<endl; InWalk(p->rChild); }void PostWalk(TreeNode* p)
{ if(p == NULL) return;if(p->lChild != NULL)
cout<< "left of "<<p->data<<endl; PostWalk( p->lChild);if( p->rChild != NULL)
cout<< "righ of " <<p->data<<endl; PostWalk(p->rChild);cout<<p->data<<endl;
} void InsertFindTree2(char data,TreeNode** pTree) { if( *pTree == NULL ) { TreeNode* pNode = new TreeNode; pNode->data = data; *pTree = pNode; pNode->lChild = pNode->rChild= NULL; } else if( data < (*pTree)->data ) { InsertFindTree2(data,&(*pTree)->lChild); } else { InsertFindTree2(data,&(*pTree)->rChild); } } void CreateFindTree2( TreeNode** pTree) { while(true) { char c; cout<<"Value:\n"<<endl; cin>>c; if( c == '$' ) { break ;//结束 } else { InsertFindTree2( c,pTree); } } }//
TreeNode* FindTreeNode2( char data,TreeNode** pTree) { TreeNode* pRetNode = NULL; if( data == (*pTree)->data ) { pRetNode = *pTree; } else if( data < (*pTree)->data ) { pRetNode = FindTreeNode2(data,&(*pTree)->lChild); } else { pRetNode = FindTreeNode2(data,&(*pTree)->rChild); } return pRetNode; } //寻找前驱结点 TreeNode* FindPreTreeNode2( TreeNode* pNode) { TreeNode* pRetNode = NULL; if( pNode->lChild == NULL ) { return NULL; } else if( pNode->lChild->rChild == NULL) { pRetNode = pNode->lChild; } else { pRetNode = FindPreTreeNode2( pNode->lChild->rChild ); } return pRetNode; } //寻找后继结点 TreeNode* FindPostTreeNode2( TreeNode* pNode) { TreeNode* pRetNode = NULL; if( pNode->rChild == NULL ) { return NULL; } else if( pNode->rChild->lChild == NULL) { pRetNode = pNode->rChild; } else { pRetNode = FindPostTreeNode2( pNode->rChild->lChild ); } return pRetNode; }bool DeleteFindTree2(char data ,TreeNode* parentNode, TreeNode** pTree)
{ bool bDelete = false;if( *pTree == NULL)
return false;if( data == (*pTree)->data )
{ TreeNode* delNode = *pTree; if( parentNode == NULL) { if( ((*pTree)->lChild != NULL) && ((*pTree)->rChild == NULL )) { *pTree = (*pTree)->lChild; } else if( ((*pTree)->rChild != NULL) && ((*pTree)->lChild == NULL )) { *pTree = (*pTree)->rChild; } else if( ((*pTree)->lChild != NULL) && ((*pTree)->rChild != NULL )) { //找*pTree的后继节点(可能是一个叶节点，也可能是没一个没有左孩子的节点) TreeNode *pPostNode = (*pTree)->rChild,*pParentOfPost = NULL; while( pPostNode != NULL) { if( pPostNode->lChild == NULL) break; pParentOfPost = pPostNode; pPostNode = pPostNode->rChild ; }//先把左孩子挂到后继左孩子
pPostNode->lChild = (*pTree)->lChild;//如果后继不是右孩子
if( pPostNode != (*pTree)->rChild ) { //把后继右孩子挂到后继的父节点上(后继一定没有左孩子，其必为父节点的左孩子) pParentOfPost->lChild = pPostNode->rChild; } *pTree = pPostNode; } else { *pTree = NULL; }delete delNode;
} else { if( parentNode->lChild == *pTree ) { if( ((*pTree)->lChild != NULL) && ((*pTree)->rChild == NULL )) { parentNode->lChild = (*pTree)->lChild; } else if( ((*pTree)->rChild != NULL) && ((*pTree)->lChild == NULL )) { parentNode->lChild = (*pTree)->rChild; } else if( ((*pTree)->lChild != NULL) && ((*pTree)->rChild != NULL )) { //找*pTree的后继节点(可能是一个叶节点，也可能是没一个没有左孩子的节点) TreeNode *pPostNode = (*pTree)->rChild,*pParentOfPost = NULL; while( pPostNode != NULL) { if( pPostNode->lChild == NULL) break; pParentOfPost = pPostNode; pPostNode = pPostNode->rChild ; }//先把左孩子挂到后继左孩子
pPostNode->lChild = (*pTree)->lChild;//如果后继不是右孩子
if( pPostNode != (*pTree)->rChild ) { //把后继右孩子挂到后继的父节点上(后继一定没有左孩子，其必为父节点的左孩子) pParentOfPost->lChild = pPostNode->rChild; } parentNode->lChild = pPostNode; } else { parentNode->lChild = NULL; }delete delNode;
} else if( parentNode->rChild == *pTree ) { if( ((*pTree)->lChild != NULL) && ((*pTree)->rChild == NULL )) { parentNode->rChild = (*pTree)->lChild; } else if( ((*pTree)->rChild != NULL) && ((*pTree)->lChild == NULL )) { parentNode->rChild = (*pTree)->rChild; } else if( ((*pTree)->lChild != NULL) && ((*pTree)->rChild != NULL )) { //找*pTree的后继节点(可能是一个叶节点，也可能是没一个没有左孩子的节点) TreeNode *pPostNode = (*pTree)->rChild,*pParentOfPost = NULL; while( pPostNode != NULL) { if( pPostNode->lChild == NULL) break; pParentOfPost = pPostNode; pPostNode = pPostNode->rChild ; }//先把左孩子挂到后继左孩子
pPostNode->lChild = (*pTree)->lChild;//如果后继不是右孩子
if( pPostNode != (*pTree)->rChild ) { //把后继右孩子挂到后继的父节点上(后继一定没有左孩子，其必为父节点的左孩子) pParentOfPost->lChild = pPostNode->rChild; } parentNode->rChild = pPostNode; } else { parentNode->rChild = NULL; } delete delNode; } }bDelete = true;
} else if( data < (*pTree)->data ) { bDelete = DeleteFindTree2(data,*pTree,&(*pTree)->lChild); } else { bDelete = DeleteFindTree2(data,*pTree,&(*pTree)->rChild); }return bDelete;
}int _tmain(int argc, _TCHAR* argv[]){ TreeNode* _root = NULL; CreateFindTree2(&_root);
PreWalk( _root );
if( DeleteFindTree2('3',NULL,&_root))
{ cout<<" delete ok!\n"<<endl; } else { cout<<" can not find this node !\n"<<endl; }PreWalk( _root);
return 0;
}