二叉排序树(BST)的判定(其实不容易)

供选择的答案： a：①是特殊的树②不是树的特殊形式③是两棵树的总称④是只有二个根结点的树形结构 b：①左子结点②右子结点③左子结点或者没有右子结点 ④兄弟 c～d： ①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟⑤最左的兄弟⑥最右的兄弟e：①o(n)②o(n)③o(log2n)④o(log2n) 15、每一棵树都能唯一地转换为它所对应的二叉树，树的这种二叉树表示对树的运算带来很大的好处。分析从这五条判定方法结构来看，平行四边形定义和前三条判定定理的条件较单一，或相等、或平行，而第四条判定定理是相等与平行二者兼有，如果将它看作是定义和判定（1）中各取条件的一部分而得出的话，那么从定义和前三条判定定理中每两个取其中部分条件是否都能构成平行四边形的判定方法呢。树和森林都可以转换为二叉树，二者的不同是:树转换成的二叉树,其根结点必然无右孩子，而森林转换后的二叉树，其根结点有右孩子。

下面，我们给出正确的程序（该程序没有考虑结点值为INT_MIN的情形）：[cpp]#include<iostream>#defineN7usingnamespacestd;intg_min=INT_MIN;//BST的结点typedefstructnode{intkey;structnode*lChild,*rChild;}Node,*BST;//生成一个结点Node*createNode(inti){Node*q=newNode;q->lChild=NULL;q->rChild=NULL;q->key=i;returnq;}/**下面这棵树并非BST,但程序中的isBST将其判为BST,故isBST函数逻辑有误*该树为：3//根节点为32//3的左孩子结点为2,没有右孩子结点14//2的左孩子结点为1,右孩子结点为4*/Node*createTree(){Node*p1=createNode(1);Node*p2=createNode(2);Node*p3=createNode(3);Node*p4=createNode(4);p3->rChild=NULL;p3->lChild=p2;p2->lChild=p1;p2->rChild=p4;p1->lChild=p1->rChild=NULL;p4->lChild=p4->rChild=NULL;returnp3;}//建立一棵非BST树Node*createNotBST(){Node*p[N]={NULL};inti;for(i=0;i<N;i++)p[i]=createNode(i+1);for(i=0;i<N/2;i++){p[i]->lChild=p[i*2+1];p[i]->rChild=p[i*2+2];}returnp[0];}//在给定的BST插入element,使之称为新的BSTboolBSTInsert(Node*&p,intelement){if(NULL==p)//空树{p=newNode;p->key=element;p->lChild=p->rChild=NULL;returntrue;}if(element==p->key)//BST中不能有相等的值returnfalse;if(element<p->key)//递归returnBSTInsert(p->lChild,element);returnBSTInsert(p->rChild,element);//递归}//建立BSTvoidcreateBST(Node*&T,inta[],intn){T=NULL;inti;for(i=0;i<n;i++){BSTInsert(T,a[i]);}}//判断是否为BSTboolisBST(BSTT){if(NULL!=T){isBST(T->lChild);if(T->key<=g_min)returnfalse;g_min=T->key;isBST(T->rChild);}returntrue;}voidprintJudge(Node*T){if(isBST(T))cout<<"yes"<<endl;elsecout<<"no"<<endl;}intmain(){inta[10]={4,5,2,1,0,9,3,7,6,8};intn=10;BSTT=NULL;g_min=INT_MIN;printJudge(T);//yesT=createTree();g_min=INT_MIN;printJudge(T);//noT=createNotBST();g_min=INT_MIN;printJudge(T);//nocreateBST(T,a,n);g_min=INT_MIN;printJudge(T);//yesreturn0;}上面这个程序的原理是什么呢？怎么感觉有点类似于中序遍历呢？确实如此，其实就是中序遍历，原理是：(1) 空二叉树是BST(2) 对于非空二叉树而言：中序遍历为严格递增数列 《==》该树为BST.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-98653-1.html