您的位置:威尼斯官方网站 > 威尼斯正规官网 > 中序遍历根节点的左子树

中序遍历根节点的左子树

发布时间:2019-08-05 17:09编辑:威尼斯正规官网浏览(59)

      二叉树遍历,是值从根节点出发,依照某种次序依次会见二叉树中的全部节点,使得各种节点被访问一回且仅被访谈依

    图片 1

     

    图是百度搜的。。。多谢提供图的英勇。。

        前序遍历二叉树:如若二叉树为空则再次回到,若二叉树非空,则先遍历左树,再遍历右树,遍历顺序为ABCDEGF。

        中序遍历二叉树:如果二叉树为空则再次回到,若二叉树非空,则从根节点伊始,中序遍历根节点的左子树,然后是拜望根节点,最终中序遍历右子树,遍历顺序为CBEGDFA。

        后序遍历二叉树:若是二叉树为空则重返,若二叉树非空,则从左到右先叶子后节点的拜谒遍历访谈左右子树,最后是访谈根节点。访问顺序为CGEFDBA。

        层序遍历二叉树:如若二叉树为空则重回,若二叉树非空,则从树的首先层,也正是根节点开头拜见,从上而下逐层遍历,在同一层中,依照从左到右的逐个对节点每一个访问。访谈顺序为ABCDEFG。

     

        今后,大家用PHP代码,来遍历二叉树结构。二叉树是放二个天机组,每一个节点都有八个字段,data表示那一个节点的值,lChild表示这些节点的右侧子节点,rChild表示那个节点的左边子节点。二叉树的布局大家用位置那张图。

     

    二叉树结构代码如下:

    <?php

    //二叉树

    $arr = array(

        'data' => 'A',

        'lChild' => array(

            'data' => 'B',

            'lChild' => array(

                'data' => 'C',

                'lChild' => array(),

                'rChild' => array(),

            ),

            'rChild' => array(

                'data' => 'D',

                'lChild' => array(

                    'data' => 'E',

                    'lChild' => array(),

                    'rChild' => array(

                        'data' => 'G',

                        'lChild' => array(),

                        'rChild' => array(),

                    ),

                ),

                'rChild' => array(

                    'data' => 'F',

                    'lChild' => array(),

                    'rChild' => array(),

                ),

            ),

        ),

        'rChild' => array(),

    );

     

    遍历算法一:前序遍历二叉树

    <?php

    //前序遍历二叉树算法

    echo '前序遍历二叉树算法:';

    PreOrderTraverse($arr);

    echo '<Br>';

    function PreOrderTraverse($node){

        if(empty($node)){

            return;

        }

        //输出值

        print_r($node['data']);

        //左节点

        PreOrderTraverse($node['lChild']);

        //右节点

        PreOrderTraverse($node['rChild']);

    }

     

    遍历算法二:中序遍历二叉树

    <?php

    //中序遍历二叉树算法

    echo '中序遍历二叉树算法:';

    inOrderTraverse($arr);

    echo '<Br>';

    function inOrderTraverse($node){

        if(empty($node)){

            return;

        }

        //左节点

        inOrderTraverse($node['lChild']);

        //输出值

        print_r($node['data']);

        //右节点

        inOrderTraverse($node['rChild']);

    }

     

    遍历算法三:后序遍历二叉树

    <?php

    //后序遍历二叉树算法

    echo '后序遍历二叉树算法:';

    postOrderTraverse($arr);

    echo '<Br>';

    function postOrderTraverse($node){

        if(empty($node)){

            return;

        }

        //左节点

        postOrderTraverse($node['lChild']);

        //右节点

        postOrderTraverse($node['rChild']);

        //输出值

        print_r($node['data']);

    }

    例子

    <?php
    /**
     *二叉树的创办及基本操作
     *
     *1.构造措施,开首化建设构造二叉树
     *2.按先序遍历格局建构二叉树
     *3.按先序遍历二叉树
     *4.先序遍历的非递归算法
     *5.中序遍历二叉树
     *6.中序遍历的非递归算法
     *7.后序遍历二叉树
     *8.后序遍历非递归算法
     *9.档次遍历二叉树
     *10.求二叉树叶子结点的个数
     *11.求二叉树的深度
     *12.判定二叉树是不是为空树
     *13.置空二叉树
     *
     *@author xudianyang<>
     *@version $Id:BinaryTree.class.php,v 1.0 2011/02/13 13:33:00 uw Exp
     *@copyright ©2011,xudianyang
     */
    header('content-type:text/html;charset=gb2312');

    //在PHP数据结构之五 栈的PHP的贯彻和栈的骨干操作 可以找到此类
    include_once("./StackLinked.class.php");

    //在 PHP数据结构之七 队列的链式存款和储蓄和队列的中央操作 能够找到此类
    include_once('./QueueLinked.class.php');
    class BTNode{
     //左子树“指针”
     public $mLchild=null;
     //右子树“指针”
     public $mRchild=null;
     //结点数据域
     public $mData=null; //左标记域,为1时代表mLchild“指向”结点左孩子,为2意味着“指向”结点直接四驱
     public $intLeftTag=null;
     //右标记域,为1时表示m卡宴child“指向”结点右孩子,为2意味着“指向”结点直接后继
     public $intRightTag=null;
    }
    class BinaryTree{
     //根结点
     public $mRoot;
     //依照先序遍历录入的二叉树数据
     public $mPBTdata=null;
     /**
      *构造方法,初始化创建二叉树
      *
      *@param array $btdata 遵照先序遍历录入的二叉树的多寡,一维数组,每七个因素代表二叉树贰个结点值,扩展结点值为''[长度为0的字符串]
      *@return void
      */
     public function __construct($btdata=array()){
      $this->mPBTdata=$btdata;
      $this->mRoot=null;
      $this->getPreorderTraversalCreate($this->mRoot);
     }
     /**
      *按先序遍历格局创设二叉树
      *
      *@param BTNode 二叉树结点,按援引格局传送
      *@return void
      */
     public function getPreorderTraversalCreate(&$btnode){
      $elem=array_shift($this->mPBTdata);
      if($elem === ''){
       $btnode=null;
      }else if($elem === null){
       return;
      }else{
       $btnode=new BTNode();
       $btnode->mData=$elem;
       $this->getPreorderTraversalCreate($btnode->mLchild);
       $this->getPreorderTraversalCreate($btnode->mRchild);
      }
     }
     /**
      *认清二叉树是还是不是为空
      *
      *@return boolean 假诺二叉树不空再次回到true,不然重返false
      **/
     public function getIsEmpty(){
      if($this->mRoot instanceof BTNode){
       return false;
      }else{
       return true;
      }
     }
     /**
      *将二叉树置空
      *
      *@return void
      */
     public function setBinaryTreeNull(){
      $this->mRoot=null;
     }
     /**
      *按先序遍历二叉树
      *
      *@param BTNode $rootnode 遍历进程中的根结点
      *@param array $btarr 接收值的数组变量,按援引格局传送
      *@return void
      */
     public function getPreorderTraversal($rootnode,&$btarr){
      if($rootnode!=null){
       $btarr[]=$rootnode->mData;
       $this->getPreorderTraversal($rootnode->mLchild,$btarr);
       $this->getPreorderTraversal($rootnode->mRchild,$btarr);
      }
     }
     /**
      *先序遍历的非递归算法
      *
      *@param BTNode $objRootNode 二叉树根节点
      *@param array $arrBTdata 接收值的数组变量,按援用格局传递
      *@return void
      */
     public function getPreorderTraversalNoRecursion($objRootNode,&$arrBTdata){
      if($objRootNode instanceof BTNode){
       $objNode=$objRootNode;
       $objStack=new StackLinked();
       do{
        $arrBTdata[]=$objNode->mData;
        $objRNode=$objNode->mRchild;
        if($objRNode !=null){
         $objStack->getPushStack($objRNode);
        }
        $objNode=$objNode->mLchild;
        if($objNode==null){
         $objStack->getPopStack($objNode);
        }
       }while($objNode!=null);
      }else{
       $arrBTdata=array();
      }
     }
     /**
      *中序遍历二叉树
      *
      *@param BTNode $objRootNode 进度中的根节点
      *@param array $arrBTdata 接收值的数组变量,按引用格局传递
      *@return void
      */
     public function getInorderTraversal($objRootNode,&$arrBTdata){
      if($objRootNode!=null){
       $this->getInorderTraversal($objRootNode->mLchild,$arrBTdata);
       $arrBTdata[]=$objRootNode->mData;
       $this->getInorderTraversal($objRootNode->mRchild,$arrBTdata);
      }
     }
     /**
      *中序遍历的非递归算法
      *
      *@param BTNode $objRootNode 二叉树根结点
      *@param array $arrBTdata 接收值的数组变量,按引用情势传送
      *@return void
      */
     public function getInorderTraversalNoRecursion($objRootNode,&$arrBTdata){
      if($objRootNode instanceof BTNode){
       $objNode=$objRootNode;
       $objStack=new StackLinked();
       //中序遍历左子树及访问根节点
       do{
        while($objNode!=null){
         $objStack->getPushStack($objNode);
         $objNode=$objNode->mLchild;
        }
        $objStack->getPopStack($objNode);
        $arrBTdata[]=$objNode->mData;
        $objNode=$objNode->mRchild;
       }while(!$objStack->getIsEmpty());
       //中序遍历右子树
       do{
        while($objNode!=null){
         $objStack->getPushStack($objNode);
         $objNode=$objNode->mLchild;
        }
        $objStack->getPopStack($objNode);
        $arrBTdata[]=$objNode->mData;
        $objNode=$objNode->mRchild;
       }while(!$objStack->getIsEmpty());
      }else{
       $arrBTdata=array();
      }
     }
     /**
      *后序遍历二叉树
      *
      *@param BTNode $objRootNode  遍历进程中的根结点
      *@param array $arrBTdata 接收值的数组变量,引用格局传送
      *@return void
      */
     public function getPostorderTraversal($objRootNode,&$arrBTdata){
      if($objRootNode!=null){
       $this->getPostorderTraversal($objRootNode->mLchild,$arrBTdata);
       $this->getPostorderTraversal($objRootNode->mRchild,$arrBTdata);
       $arrBTdata[]=$objRootNode->mData;
      }
     }
     /**
      *后序遍历非递归算法
      *
     BTNode $objRootNode 二叉树根节点
     array $arrBTdata 接收值的数组变量,按援引格局传送
     void
      */
     public function getPostorderTraversalNoRecursion($objRootNode,&$arrBTdata){
      if($objRootNode instanceof BTNode){
       $objNode=$objRootNode;
       $objStack=new StackLinked();
       $objTagStack=new StackLinked();
       $tag=1;
       do{
        while($objNode!=null){
         $objStack->getPushStack($objNode);
         $objTagStack->getPushStack(1);
         $objNode=$objNode->mLchild;
        }
        $objTagStack->getPopStack($tag);
        $objTagStack->getPushStack($tag);
        if($tag == 1){
         $objStack->getPopStack($objNode);
         $objStack->getPushStack($objNode);
         $objNode=$objNode->mRchild;
         $objTagStack->getPopStack($tag);
         $objTagStack->getPushStack(2);

        }else{
         $objStack->getPopStack($objNode);
         $arrBTdata[]=$objNode->mData;
         $objTagStack->getPopStack($tag);
         $objNode=null;
        }
       }while(!$objStack->getIsEmpty());
      }else{
       $arrBTdata=array();
      }
     }
     /**
      *档期的顺序遍历二叉树
      *
      *@param BTNode $objRootNode二叉树根节点
      *@param array $arrBTdata 接收值的数组变量,按援用格局传送
      *@return void
      */
     public function getLevelorderTraversal($objRootNode,&$arrBTdata){
      if($objRootNode instanceof BTNode){
       $objNode=$objRootNode;
       $objQueue=new QueueLinked();
       $objQueue->getInsertElem($objNode);
       while(!$objQueue->getIsEmpty()){
        $objQueue->getDeleteElem($objNode);
        $arrBTdata[]=$objNode->mData;
        if($objNode->mLchild != null){
         $objQueue->getInsertElem($objNode->mLchild);
        }
        if($objNode->mRchild != null){
         $objQueue->getInsertElem($objNode->mRchild);
        }
       }
      }else{
       $arrBTdata=array();
      }
     }
     /**
      *求二叉树叶子结点的个数
      *
      *@param BTNode $objRootNode 二叉树根节点
      *@return int 参数字传送递错误再次来到-1
      **/
     public function getLeafNodeCount($objRootNode){
      if($objRootNode instanceof BTNode){
       $intLeafNodeCount=0;
       $objNode=$objRootNode;
       $objStack=new StackLinked();
       do{
        if($objNode->mLchild == null && $objNode->mRchild == null){
         $intLeafNodeCount ;
        }
        $objRNode=$objNode->mRchild;
        if($objRNode != null){
         $objStack->getPushStack($objRNode);
        }
        $objNode=$objNode->mLchild;
        if($objNode == null){
         $objStack->getPopStack($objNode);
        }
       }while($objNode != null);
       return $intLeafNodeCount;
      }else{
       return -1;
      }
     }
     /**
      *求二叉树的纵深
      *
      *@param BTNode $objRootNode 二叉树根节点
      *@return int 参数字传送递错误重回-1
      */
     public function getBinaryTreeDepth($objRootNode){
      if($objRootNode instanceof BTNode){
       $objNode=$objRootNode;
       $objQueue=new QueueLinked();
       $intBinaryTreeDepth=0;
       $objQueue->getInsertElem($objNode);
       $objLevel=$objNode;
       while(!$objQueue->getIsEmpty()){
        $objQueue->getDeleteElem($objNode);
        if($objNode->mLchild != null){
         $objQueue->getInsertElem($objNode->mLchild);
        }
        if($objNode->mRchild != null){
         $objQueue->getInsertElem($objNode->mRchild);
        }
        if($objLevel == $objNode){
         $intBinaryTreeDepth ;
         $objLevel=@$objQueue->mRear->mElem;
        }
       }
       return $intBinaryTreeDepth;
      }else{
       return -1;
      }
     }
    }
    echo "<pre>";
    $bt=new BinaryTree(array('A','B','D','','','E','','G','','','C','F','','',''));
    echo "二叉树结构:\r\n";
    var_dump($bt);
    $btarr=array();
    echo "先序递归遍历二叉树:\r\n";
    $bt->getPreorderTraversal($bt->mRoot,$btarr);
    var_dump($btarr);
    echo "先序非递归遍历二叉树:\r\n";
    $arrBTdata=array();
    $bt->getPreorderTraversalNoRecursion($bt->mRoot,$arrBTdata);
    var_dump($arrBTdata);
    echo "中序递归遍历二叉树:\r\n";
    $arrBTdata=array();
    $bt->getInorderTraversal($bt->mRoot,$arrBTdata);
    var_dump($arrBTdata);
    echo "中序非递归遍历二叉树:\r\n";
    $arrBTdata=array();
    $bt->getInorderTraversalNoRecursion($bt->mRoot,$arrBTdata);
    var_dump($arrBTdata);
    echo "后序递归遍历二叉树:\r\n";
    $arrBTdata=array();
    $bt->getPostorderTraversal($bt->mRoot,$arrBTdata);
    var_dump($arrBTdata);
    echo "后序非递归遍历二叉树:\r\n";
    $arrBTdata=array();
    $bt->getPostorderTraversalNoRecursion($bt->mRoot,$arrBTdata);
    var_dump($arrBTdata);
    echo "按档次遍历二叉树:\r\n";
    $arrBTdata=array();
    $bt->getLevelorderTraversal($bt->mRoot,$arrBTdata);
    var_dump($arrBTdata);
    echo "叶子结点的个数为:".$bt->getLeafNodeCount($bt->mRoot);
    echo "\r\n";
    echo "二叉树深度为:".$bt->getBinaryTreeDepth($bt->mRoot);
    echo "\r\n";
    echo "判定二叉树是还是不是为空:";
    var_dump($bt->getIsEmpty());
    echo "将二叉树置空后:";
    $bt->setBinaryTreeNull();
    var_dump($bt);
    echo "</pre>";
    ?>

    本文由威尼斯官方网站发布于威尼斯正规官网,转载请注明出处:中序遍历根节点的左子树

    关键词:

上一篇: 代码如下

下一篇:没有了