树和二叉树二叉树遍历线索二叉树二叉搜索树二叉树的计数

树和二叉树二叉树遍历线索二叉树二叉搜索树二叉树的计数内容摘要：

二叉搜索树 45 12 57 8 20 60 3 11 59 50 二叉搜索树的作用： 排序 ， 检索 二叉搜索树 ifndef BINARY_SEARCH_TREE_CLASS define BINARY_SEARCH_TREE_CLASS include include ifndef NULL const int NULL = 0。 endif // NULL include template class T class BinSTree { TreeNodeT *root, *current。 int size。 TreeNodeT *GetTreeNode(const Tamp。 item, TreeNodeT *lptr,TreeNodeT *rptr)。 void FreeTreeNode(TreeNodeT *p)。 TreeNodeT *CopyTree(TreeNodeT *t)。 void DeleteTree(TreeNodeT *t)。 TreeNodeT *FindNode(const Tamp。 item, TreeNodeT* amp。 parent) const。 public: BinSTree(void)。 BinSTree(const BinSTreeTamp。 tree)。 ~BinSTree(void)。 BinSTreeTamp。 operator= (const BinSTreeTamp。 rhs)。 int Find(Tamp。 item)。 void Insert(const Tamp。 item)。 void Delete(const Tamp。 item)。 void ClearList(void)。 int ListEmpty(void) const。 int ListSize(void) const。 void Update(const Tamp。 item)。 TreeNodeT *GetRoot(void) const。 }。 template class T TreeNodeT *BinSTreeT::GetTreeNode(const Tamp。 item,TreeNodeT *lptr,TreeNodeT *rptr) { TreeNodeT *p。 p = new TreeNodeT (item, lptr, rptr)。 if (p == NULL) { cerr Memory allocation failure!\n。 exit(1)。 } return p。 } // delete the storage occupied by a tree node template class T void BinSTreeT::FreeTreeNode(TreeNodeT *p) { delete p。 } template class T TreeNodeT *BinSTreeT::CopyTree(TreeNodeT *t) { TreeNodeT *newlptr, *newrptr, *newNode。 if (t == NULL) return NULL。 if (tleft != NULL) newlptr = CopyTree(tleft)。 else newlptr = NULL。 if (tright != NULL) newrptr = CopyTree(tright)。 else newrptr = NULL。 newNode = GetTreeNode(tdata, newlptr, newrptr)。 return newNode。 } template class T void BinSTreeT::DeleteTree(TreeNodeT *t) { if (t != NULL) { DeleteTree(tleft)。 DeleteTree(tright)。 FreeTreeNode(t)。 } } template class T TreeNodeT *BinSTreeT::FindNode(const Tamp。 item, TreeNodeT* amp。 parent) const { TreeNodeT *t = root。 parent = NULL。 while(t != NULL) { if (item == tdata) break。 else { parent = t。 if (item tdata) t = tleft。 else t = tright。 } } return t。 } template class T BinSTreeT::BinSTree(void): root(NULL),current(NULL),size(0) { } template class T BinSTreeT::BinSTree(const BinSTreeTamp。 tree) { // copy tree to the current object. assign current and size root = CopyTree()。 current = root。 size =。 } template class T BinSTreeT::~BinSTree(void) { // just call ClearList ClearList( )。 } template class T BinSTreeTamp。 BinSTreeT::operator= (const BinSTreeTamp。 rhs) { if (this == amp。 rhs) return *this。 ClearList( )。 root = CopyTree()。 current = root。 size =。 return *this。 } template class T int BinSTreeT::Find(Tamp。 item) { TreeNodeT *parent。 current = FindNode (item, parent)。 if (current != NULL) { item = currentdata。 return 1。 } else return 0。 } template class T void BinSTreeT::Insert(const Tamp。 item) {TreeNodeT *t = root, *parent = NULL, *newNode。 while(t != NULL) { parent = t。 if (item tdata) t = tleft。 else t = tright。 } newNode = GetTreeNode(item,NULL,NULL)。 if (parent == NULL) root = newNode。 else if (item parentdata) parentleft = newNode。 else parentright = newNode。 current = newNode。 size++。 } 二叉搜索树的插入过程 45 12 8 57 60 20 11 59 50 3 45 12 57 8 20 60 3 11 59 50 57 20 8 45 60 59 3 12 50 11 57 20 60 8 45 11 3 12 50 59 二叉搜索树的删除过程 先调用函数 FindNode查到要删除的结点 D(DNodePtr), D的父结点 P(PNodePtr),我们寻找 替换结点 R(RNodePtr). 45 12 57 15 20 60 59 50 1. D是 叶 令 R=NULL。 Pleft=R。 即可。 D P R 二叉搜索树的删除过程 先调用函数 FindNode查到要删除的结点 D(DNodePtr), D的父结点 P(PNodePtr),我们寻找 替换结点 R(RNodePtr). 45 12 57 15 20 60 59 50 1. D是 叶 令 R=NULL。 Pleft=R。 即可。 D P R 2. D只有左子树 令 R=Dleft。 15 R 15 RPright=R。 二叉搜索树的删除过程 先调用函数 FindNode查到要删除的结点 D(DNodePtr), D的父结点 P(PNodePtr),我们寻找 替换结点 R(RNodePtr). 45 12 57 15 20 60 59 50 1. D是 叶 令 R=NULL。 Pleft=R。 即可。 D P 2. D只有左子树 , Dright=NULL 令 R=Dleft。 Pright=R。 3. D只有右子树 , Dleft=NULL 令 R=Dright。 Pleft=R。 R 15 20R 57 20 60 8 45 11 3 12 50 59 二叉搜索树的删除过程 D P R R Q=D。 R=Dleft。 while(Rright){Q=R, R=Rright:} R选择 D的 左 子树中 最大 结点 (或 右 子树中 最小 结点 ) 有两种情况： 1. Q==D Rright=Dright。 2. Q!=D Qright=Rleft。 再用 R代替 D R 1112 R Q Q R 57 20 60 8 45 3 11 50 59 二叉搜索树的删除过程 D P R Q=D。 R=Dleft。 while(Rright){Q=R, R=Rright:} 2. Q!=D Qright=Rleft。 再用 R代替 D : Q 有两种情况： 1. Q==D Rright=Dright。 Rright=Dright。 Rleft=Dleft。 12 R R R 12 最后让 P指向 R 如果 P==NULL 则 R是根，否则 D在 P左 R在左 template class T void BinSTreeT::Delete(const Tamp。 item) {TreeNodeT *DNodePtr, *PNodePtr, *RNodePtr。 if ((DNodePtr = FindNode (item, PNodePtr)) == NULL) return。 if (DNodePtrright == NULL) RNodePtr = DNodePtrleft。 else if (DNodePtrleft == NULL) RNodePtr = DNodePtrright。 else {TreeNodeT *PofRNodePtr = DNodePtr。 RNodePtr = DNodePtrleft。 while(RNodePtrright != NULL) { PofRNodePtr = RNodePtr。 RNodePtr = RNodePtrright。 } if (PofRNodePtr == DNodePtr) RNodePtrright = DNodePtrright。 else{PofRNode。