文档介绍：该【《特殊二叉树》 】是由【相惜】上传分享，文档一共【63】页，该文档可以免费在线阅读，需要了解更多关于【《特殊二叉树》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。,它或者是一棵空树,或者是具有如下特征的非空二叉树:假设它的左子树非空,那么左子树上所有结点的关键字均小于根结点的关键字;假设它的右子树非空,那么右子树上所有结点的关键字均大于(假设允许具有相同关键字的结点存在,那么大于等于)根结点的关键字;左、右子树本身又各是一棵二叉搜索树。整理ppt526330121523741826526330121523741826一棵二叉排序数对该树中序遍历得到一有序序列:12,15,18,23,26,30,52,63,,其过程为:(1)假设二叉搜索树为空,那么说明查找失败,应返回假(2)假设item等于当前树根结点的值,那么说明查找成功,应由引用参数item带回根结点的完整值并返回真(3)假设item小于当前树根结点的值,那么继续在它的左子树上查找,假设item大于当前树根结点的值,那么继续它的右子树上查找。整理pptboolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;else{if(item==BST->data){item=BST->data;returntrue;}elseif(item<BST->data)returnFind(BST->left,item);elsereturnFind(BST->right,item);}}整理ppt进行二叉排序树查找的非递归算法boolFind1(BTreeNode*BST,ElemType&item){while(BST!=NULL){if(item==BST->data){item=BST->data;returntrue;}elseif(item<BST->data)BST=BST->left;elseBST=BST->right;}returnfalse;},区别在于:在更新算法中查找到待更新元素时,应将item的值赋给该元素,而查找算法中那么是将该元素的值赋给item带回更新算法中item可为变参,也可为值参,在参数说明前可以加或不加const,而在查找算法中item只可为变参,:(1)假设当前二叉树为空,那么由item元素生成的新结点将作为树根结点插入;(2)否那么,假设item小于当前树根结点的值,那么将新结点插入到它的左子树上,假设item大于当前树根结点的值,那么将新结点插入到它的右子树上。整理ppt递归算法描述为:voidInsert(BTreeNode*&BST,constElemtype&item){if(BST==NULL){BTreeNode*p=newBTreeNode;p->data=item;p->left=p->right=NULL;BST=p;}elseif(item<BST->data)Insert(BST->left,item);elseInsert(BST->right,item);}整理ppt非递归算法描述为:voidInsert1(BTreeNode*&BST,constElemtype&item){BTNode*t=BST,*parent=NULL;while(t!=NULL){parent=t;if(item<t->data)t=t->left;elset=t->right;}BTreeNode*p=newBTreeNode;p->data=item;p->left=p->right=NULL;if(parent==NULL)BST=p;elseif(item<parent->data)parent->left=p;elseparent->right=p;}整理ppt