本文介绍了二叉树和二叉搜索树，然后通过PHP代码定义了二叉搜索树的节点，利用递归思想操作向二叉搜索树添加元素，进而实现递归判断一个元素是否包含在二叉查找树中，最终实现二叉查找树的前序遍历、中序遍历、后序遍历。1.二叉树1.1二叉树图1.2二叉树节点定义//二叉树有一个唯一的根节点类Node{$e;//节点元素$left;//左儿子$right;//右儿子}Tips：二叉树的每个节点最多有两个儿子，每个节点至多有一个父亲。1.3二叉树的特点二叉树具有天然的递归结构，每个节点的左儿子或右儿子也是一棵二叉树。二叉树不一定是满的，它可能只有左儿子或者二儿子。节点或NULL也可以看作是二叉树。2.二叉搜索树2.1二叉搜索树的特点二叉搜索树是一棵二叉树。每个节点的元素值必须大于左孩子所有节点的值。每个节点的元素值必须小于右孩子所有节点的值。每个子树也是一个二叉搜索树。二叉搜索树查询很快。存储的元素必须是可比较的。2.2二叉查找树图2.3PHP代码定义节点类Node{public$e;公共$左=空；公共$right=null;/***构造函数初始化节点数据*节点构造函数。*@param$e*/publicfunction__construct($e){$this->e=$e;}}2.4向二叉搜索树添加元素下面展示了利用递归的思想向二叉搜索树添加元素，其中add($e)方法的意思是将元素$e添加到搜索树中，recursionAdd(Node$root,$e)是一个递归函数，即使用递归的方式向二叉搜索树中添加元素：/***向二叉搜索树中添加元素*@param$e*/publicfunctionadd($e){$this->root=$this->recursionAdd($this->root,$e);}/***递归添加元素到二叉搜索树*@paramNode$root*@param$e*/publicfunctionrecursionAdd(Node$root,$e){if($root==null){//If节点为空，添加一个元素并返回当前节点信息$this->size++;$root=新节点($e);}elseif($e<$root->e){//如果元素小于当前节点元素，则向左节点递归添加元素$root->left=$this->recursionAdd($root->left,$e);}elseif($e>$root->e){//如果元素大于当前节点元素，递归向右节点添加元素$root->right=$this->recursionAdd($root->right,$e);}//如果元素等于当前节点元素，什么都不做}Tips：这里的二叉搜索树不包含重复元素，如果要包含重复元素，可以定义每个左孩子的所有元素都少大于等于父节点，或者说每个右子节点的所有元素都大于等于父节点2.5查询二叉搜索树是否包含元素。下面展示的递归思路是用来查询二叉搜索树元素是否包含某个元素的。contains($e)方法表示查询二叉搜索树是否包含元素$e，recursionContains(Node$root,$e)是一个递归函数，表示使用递归查询二叉搜索树元素：/***判断二叉查找树是否包含一个元素*@param$e*@returnbool*/publicfunctioncontains($e):bool{return$this->recursionContains($this->root,$e);}/***递归判断二叉搜索树是否包含一个元素*@param$root*@param$e*@returnbool*/privatefunctionrecursionContains(Node$root,$e):bool{if($root==null){//如果当前节点为空，则没有元素$ereturnfalse;}elseif($e==$root->e){//如果$e等于当前节点元素，则表示该树包含元素$ereturntrue;}elseif($e<$root->e){//如果$e小于当前节点元素，则向左递归查询子树是否包含节点return$this->recursionContains($root->left,$e);}else{//如果$e大于当前节点元素，则去右子树递归查询是否包含节点return$this->recursionContains($root->right,$e);}}Tips：递归时，会比较元素和节点的值。是判断元素是否存在的依据2.6二叉搜索树的前序遍历前序遍历操作是访问所有节点一次。前序遍历是先访问节点，然后递归遍历左子树，再递归遍历右子树：/***前序遍历*/publicfunctionpreTraversal(){$this->recursionPreTraversal($this->根，0）；}/***前序遍历的递归*/publicfunctionrecursionPreTraversal($root,$sign_num){echo$this->getSign($sign_num);//打印深度if($root==null){echo"null
”；返回;}回显$root->e。“
”；//打印当前节点元素$this->recursionPreTraversal($root->left,$sign_num+1);$this->recursionPreTraversal($root->right,$sign_num+1);}下面是打印结果：add(45);$binarySearchTree->add(30);$binarySearchTree->add(55);$binarySearchTree->add(25);$binarySearchTree->add(35);$binarySearchTree->add(50);$binarySearchTree->add(65);$binarySearchTree->add(15);$binarySearchTree->add(27);$binarySearchTree->add(31);$binarySearchTree->add(48);$binarySearchTree->add(60);$binarySearchTree->add(68);//下面是预期的想要的结果/***45*/*3055*//*25355065*////*152731486068**/$binarySearchTree->preTraversal();/**打印输出45-----30------------25----------------15-------------------null----------------null------------27----------------------null--------------------null------------35----------------31--------------------空---------------------null-------------null-----55---------50----------------48--------------------null--------------------null----------------空------------65------------60------------------null--------------------null----------------68--------------------null--------------------null*/Tips:可以看到打印输出结果和期望值一致2.7二叉搜索树的中序遍历遍历操作是访问所有节点一次，后序遍历是先递归遍历右子树，然后访问节点，再递归遍历右子树。最终的序列输出结果是有序的：/***中序遍历*/publicfunctionmidTraversal(){$this->recursionMidTraversal($this->root,0);}/***中序遍历的递归*/publicfunctionrecursionMidTraversal($root,$sign_num){if($root==null){echo$this->getSign($sign_num);//打印深度echo"null
”；返回;}$this->recursionMidTraversal($root->left,$sign_num+1);echo$this->getSign($sign_num);//打印深度echo$root->e.“
”；$this->recursionMidTraversal($root->right,$sign_num+1);这是打印结果：add(45);$binarySearchTree->add(30);$binarySearchTree->add(55);$binarySearchTree->add(25);$binarySearchTree->add(35);$binarySearchTree->add(50);$binarySearchTree->add(65);$binarySearchTree->add(15);$binarySearchTree->add(27);$binarySearchTree->add(31);$binarySearchTree->add(48);$binarySearchTree->add(60);$binarySearchTree->add(68);//下面是预期结果/***45*/*3055*//*25355065*////*152731486068**/$binarySearchTree->midTraversal();/**打印输出------------------null----------------15------------------空------------25-------------------null----------------27--------------------null-----30------------------空----------------31--------------------null------------35----------------null45----------------------null----------------48--------------------null------------50--------------null-----55--------------------null---------------60--------------------null--------65----------------无效的-----------68--------------------null*/Tips:可以看到打印出来的结果和预期一致，但是遍历顺序有此时改变，最后顺序输出的结果是有序的2.8二叉搜索树的后序遍历遍历操作是访问所有节点一次。后序遍历是先递归遍历左子树，再递归遍历右子树，然后访问节点：/***后序遍历*/publicfunctionrearTraversal(){$this->recursionRearTraversal($this->root,0);}/***后序遍历的递归*/publicfunctionrecursionRearTraversal($root,$sign_num){if($root==null){echo$this->getSign($sign_num);//打印深度echo"空
”；返回;}$this->recursionRearTraversal($root->left,$sign_num+1);$this->recursionRearTraversal($root->right,$sign_num+1);echo$this->getSign($sign_num);//打印深度echo$root->e.“
”；}下面是打印结果：add(45);$binarySearchTree->add(30);$binarySearchTree->add(55);$binarySearchTree->add(25);$binarySearchTree->add(35);$binarySearchTree->add(50);$binarySearchTree->add(65);$binarySearchTree->add(15);$binarySearchTree->add(27);$binarySearchTree->add(31);$binarySearchTree->add(48);$binarySearchTree->add(60);$binarySearchTree->add(68);//下面是预期结果/***45*/*3055*//*25355065*////*152731486068**/$binarySearchTree->rearTraversal();/**打印输出--------------------null--------------------null----------------15--------------------空-------------------空----------------27------------25---------------------null--------------------null----------------31----------------null------------35-----30--------------------null-------------------null----------------48----------------null--------50--------------------空------------------空----------------60--------------------空------------------无效的--------68------------65-----5545*/代码仓库：https://gitee.com/love-for-po...扫码关注爱因世贤
