• 反腐败国际合作"朋友圈"又大了! 2019-07-13
  • 前线 从一面“魔镜” 看苏宁科技集团智能化发展战略 2019-07-13
  • 身份证被盗产生不良记录 网络虚拟账号权属纠纷如何避免 2019-07-07
  • 的确,呆子七窍通了栁窍。[哈哈] 2019-06-20
  • 强国博客首页整合公告 2019-06-08
  • 西海都市报数字报刊平台 2019-05-27
  • 美国反拥枪的孩子很受伤 2019-05-25
  • C罗戴帽单骑救主 葡萄牙33战平西班牙 2019-05-25
  • 证监会去年对外公开监管信息14560条 2019-05-16
  • 中山八路总站调整12公交线 2019-05-16
  • 谢春涛:深刻把握“中国特色社会主义进入新时代”的重大意义 2019-05-09
  • 湖南一博士生举报水利局领导受贿 遭到冒牌纪委约谈 2019-05-09
  • 西安地铁唐风诗韵文化专列将于6月18日首发 2019-04-30
  • 铜梁区旧县街道:全面提升执行力 推动工作落地见效 2019-04-30
  • 上海电影节女性影人大放异彩 中生代女演员不用焦虑 2019-04-29
  • 二叉树的递归算法好难理解,求大神分享感悟

    糖分0325 发布于 07/08 17:03
    阅读 499
    收藏 2

    广东十一选五推荐号 www.qhysp.com 最近一直被困于二叉树的递归算法,例如前中后序遍历,打印一个二叉树的递归算法,一直不知道怎么理解它们,十分苦恼,希望大佬们能分享下感悟。

    加载中
    2
    tcxu
    tcxu

        递归(recursion) 又称递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。

        一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

        构成递归需具备的条件:
    1. 子问题须与原始问题为同样的事,且更为简单;
    2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。

        代码取自美国课本 "Java How to Program "(Deitel & Detel)的练习: 20.25。
    以中序遍历递归方法为例,这里显示的图解,仅诠释开始一小部分递归前进段与递归返回段的交叉过程。通过这一小段的繁琐解释,希望读者可见到二叉树递归遍历的端倪。
     private void inorderHelper( TreeNode node ){
          if ( node == null ) //若节点为空
             return; //无任何操作

          inorderHelper( node.leftNode ); //有序遍历下一级左子树
          System.out.print( node.data + " " ); //输出节点数据
          inorderHelper( node.rightNode );//有序遍历下一级右子树
       }

    插图说明:

    1. 前进段的进程 1 :鉴于以树根 节点 "49" 为参数,调用 inorderHelper(...),开始调用以下一级树根 节点 "28" 为参数 的inorderHelper(...) 方法。
    2. 前进段的进程 2 :鉴于以树根 节点 "28" 为参数,调用 inorderHelper(...),开始调用以下一级树根 节点 "18" 为参数 的 inorderHelper(...) 方法。
    3. 前进段的进程 3 :鉴于以树根 节点 "18" 为参数,调用 inorderHelper(...),开始调用以下一级树根 节点 "11" 为参数 的 inorderHelper(...) 方法。
    4. 节点 "11" 为叶节点,递归前进到终点??计舳祷夭僮?, 输出其数值 11。
    5. 至此,参数为 节点 "11" 的 方法 inorderHelper(...) 执行完毕。返回进程 4 启动下一个 输出:18。
    6. 输出 18 的代码行执行完毕,进入前进段进程 5, 执行接下来一行的代码:调用参数为 节点 "19" 的节点的方法 inorderHelper(...)
    7. 节点 "19" 为叶节点,递归前进到终点??计舳祷夭僮?, 输出其数值 19。
    8. 至此,参数为 节点 "19" 的 方法 inorderHelper(...) 执行完毕。返回进程 6 启动下一个 输出:28。
    9. ..... 

    附录:

    输出:

    源代码:

    // Deitel & Detel, 20.25
    // class TreeNode definition
    class TreeNode {
    
       // public access members
       public TreeNode leftNode;   
       public int data;        
       public TreeNode rightNode;  
    
       // initialize data and make this a leaf node
       public TreeNode( int nodeData )
       { 
          data = nodeData;              
          leftNode = rightNode = null;  // node has no children
       }
    
       // locate insertion point and insert new node; ignore duplicate values
       public synchronized void insert( int insertValue )
       {
          // insert in left subtree
          if ( insertValue < data ) {
    
             // insert new TreeNode
             if ( leftNode == null )
                leftNode = new TreeNode( insertValue );
    
             else // continue traversing left subtree
                leftNode.insert( insertValue ); 
          }
    
          // insert in right subtree
          else if ( insertValue > data ) {
    
             // insert new TreeNode
             if ( rightNode == null )
                rightNode = new TreeNode( insertValue );
    
             else // continue traversing right subtree
                rightNode.insert( insertValue ); 
          }
    
       } // end method insert
    
       // get right child
       public synchronized TreeNode getRight()
       {
          return rightNode;
       }
    
       // get left child
       public synchronized TreeNode getLeft()
       {
          return leftNode;
       }
    
       // return the data
       public synchronized Object getData()
       {
          return new Integer( data );
       }
    
    }  // end class TreeNode
    
    
    
    public class TreeTest {
       private TreeNode root;
    
       public TreeTest() 
       { 
          root = null; 
       }
    
       // insert a new node in the binary search tree
       public synchronized void insertNode( Integer value )
       {
          if ( root == null )
             root = new TreeNode( value.intValue() );
    
          else
             root.insert( value.intValue() );
       }
    
       // begin preorder traversal
       public synchronized void preorderTraversal()
       { 
          preorderHelper( root ); 
       }
    
       // recursive method to perform preorder traversal
       private void preorderHelper( TreeNode node )
       {
          if ( node == null )
             return;
    
          System.out.print( node.data + " " );
          preorderHelper( node.leftNode );
          preorderHelper( node.rightNode );
       }
    
       // begin inorder traversal
       public synchronized void inorderTraversal()
       { 
          inorderHelper( root ); 
       }
    
       // recursive method to perform inorder traversal
       private void inorderHelper( TreeNode node )
       {
          if ( node == null )
             return;
    
          inorderHelper( node.leftNode );
          System.out.print( node.data + " " );
          inorderHelper( node.rightNode );
       }
    
       // begin postorder traversal
       public synchronized void postorderTraversal()
       { 
          postorderHelper( root ); 
       }
    
       // recursive method to perform postorder traversal
       private void postorderHelper( TreeNode node )
       {
          if ( node == null )
             return;
      
          postorderHelper( node.leftNode );
          postorderHelper( node.rightNode );
          System.out.print( node.data + " " );
       }
    
       // begin printing tree
       public void outputTree()
       {
          outputTreeHelper( root, 0 );
       }
    
       // recursive method to print tree
       private void outputTreeHelper( TreeNode currentNode, int spaces )
       {
          // recursively print right branch, then left
          if ( currentNode != null ) {
             outputTreeHelper( currentNode.getRight(), spaces + 5 );
    
             for ( int k = 1; k <= spaces; k++ )
                System.out.print( " " );
    
             System.out.println( currentNode.getData().toString() );
             outputTreeHelper( currentNode.getLeft(), spaces + 5 );
          }
       }
       
         public static void main( String args[] )
       {
          TreeTest tree = new TreeTest();
          int intVal;
    
          System.out.println( "Inserting the following values: " );
    /*
          // create Objects to store in tree
          for ( int i = 1; i <= 10; i++ ) {
             intVal = ( int ) ( Math.random() * 100 );
             System.out.print( intVal + " " );
             tree.insertNode( new Integer( intVal ) );
          }
    */
    
    
    
    tree.insertNode( new Integer( 49) );
    
    tree.insertNode( new Integer( 28 ) );
    tree.insertNode( new Integer( 83 ) );
    tree.insertNode( new Integer( 18 ) );
    tree.insertNode( new Integer( 19) );
    tree.insertNode( new Integer( 11 ) );
    tree.insertNode( new Integer( 40 ) );
    tree.insertNode( new Integer( 32 ) );
    tree.insertNode( new Integer( 44) );
    tree.insertNode( new Integer( 71) );
    tree.insertNode( new Integer( 72) );
    tree.insertNode( new Integer( 69 ) );
    tree.insertNode( new Integer( 97) );
    tree.insertNode( new Integer( 99) );
    
    
          // run three different traversal types
          System.out.println ( "\n\nPreorder traversal" );
          tree.preorderTraversal();
    
          System.out.println ( "\n\nInorder traversal" );
          tree.inorderTraversal();
    
          System.out.println ( "\n\nPostorder traversal" );
          tree.postorderTraversal();
    
          // print a depiction of the tree
          System.out.println( "\n\n" );
          tree.outputTree();
       }
    
    }  // end class TreeTest
    

     

    糖分0325
    糖分0325
    谢谢
    0
    邹海彬
    邹海彬

    实在是很好理解啊,想象你面前有一颗树,你要数清楚这棵树有多少个节点(分叉点+叶子),有三种数法:

     

    数法1:数一个节点,就记一次,叫前序遍历

    有一个根节点,记录下来(输出),然后变成数左边的树和右边的树

    方向上就是:自上而下(根节点在上),再从左至右

     

    数法2:先把左边的数完,再数根,再数右边,这叫中序遍历

    先数到最左边的叶子节点,再数最左边叶子节点的父节点,再数该父节点的右边最左边的叶子

    方向上就是:从左至右

     

    数法3:先数叶子,再数根,这叫后序遍历

    第一个数的是最左边的叶子节点,然后数该节点父节点右边最左边的节点,数完了右边所有节点,再数该父节点

    方向上:从左至右,但不数根节点,数完了再数根节点

     

    递归的思想就是解决相似问题经常用到的:树就是具有相似性的特点,树本身是一棵树,树的左边和右边也分别是一棵树,所有就可以用递归思想来解决。

    0
    前端大师傅
    前端大师傅

    二叉树很简单,楼主可以先从最简单的开始学起,记住三点就可以:

    1.无论B+还是二叉只要是树这种数据结构必然是由节点组成,即一定有NODE这种结构存在。

    2.二叉树的NODE结构必然包含0-2三种情况之一:

    1)NODE 为空,没有节点

    2)NODE 只包含 一个节点 即LEFTNODE或RIGHTNODE,这里可以随意定哪个节点

    3)NODE包含LEFTNODE和RIGHTNODE一个左一个右。综上所述如果存在node struct的话是这样的:

    class Node{
    
        public Node LeftNode;
    
        public Node RightNode;
    
    }

    3.每个节点每个LEFTNODE或RIGHTNODE可能又包含0-2三个节点。而递归的意思是

    通过函数自身调用自身把它们都找出来。

    4.递归的意思非常简单就是在函数的代码里调用这个函数。

    5.树型结构使用递归的原因在于并不清楚子节点(LEFT或RIGHT)节点里是否包含子节点,当然

    可以用循环来做也是可行的。要记住递归解决的,循环也可以。所以不要被递归给弄糊涂了。

    0
    酸萝卜炒鸡蛋
    有个苹果app叫,算法动画图解 你去看看
    0
    tcxu
    tcxu

    根据 动画:二叉树遍历的多种姿势,画出的 中序递归遍历的代码操作顺序 

    void inorderTraversal(Node node){
    	if (node) {
    	inorderTraversal(node.left);
    	System.out.println(node.data);
    	inorder Traversal(node.right);
    	}
    }

    遍历数值为10的节点(总树根)的递归方法 void inorderTraversal(Node root) 的代码操作顺序

    1. 先遍历 总树根的左子树,左子树的树根是数值为 5 的节点。
    2. 打印 数值为4的叶节点*。
    3. 输出 数值为5的节点 (左子树的树根)。
    4. 打印 数值为8的叶节点*。(至此,树根数值为 5 的节点的 左子树 遍历完毕)
    5. 输出 数值为10的节点 (总树根)。
    6. 然后 遍历 总树根的右子树,右子树的树根是数值为 19 的节点。
    7. 打印 数值为13的叶节点*。
    8. 输出 数值为19的节点(右子树的树根)。
    9. 打印 数值为24的叶节点*。(至此,树根数值为 19 的节点的 右子树 遍历完毕。进而,总树根数值为10的节点的二叉查询树 遍历完成。)

    * 调用 树根为 叶节点 的(子)树 的中序递归遍历方法 void inorderTraversal(Node root),由于其左、右子树的树根都为空,故仅输出这个叶节点的数据数值。因此简称:"打印叶节点"。

    先输出左子树,然后输出当前节点10,最后输出右子树;
    对于其左子树来说,同样以这样的顺序,则先输出左子树4,然后输出节点值5,最后输出右子树8;
    对于其右子树,同样以这样的顺序,则先,输出左子树13,然后输出节点值19,最后输出右子树24;
    最终得到中序遍历输出为:4,5,8,10,13,19,24。


     

    返回顶部
    顶部
  • 反腐败国际合作"朋友圈"又大了! 2019-07-13
  • 前线 从一面“魔镜” 看苏宁科技集团智能化发展战略 2019-07-13
  • 身份证被盗产生不良记录 网络虚拟账号权属纠纷如何避免 2019-07-07
  • 的确,呆子七窍通了栁窍。[哈哈] 2019-06-20
  • 强国博客首页整合公告 2019-06-08
  • 西海都市报数字报刊平台 2019-05-27
  • 美国反拥枪的孩子很受伤 2019-05-25
  • C罗戴帽单骑救主 葡萄牙33战平西班牙 2019-05-25
  • 证监会去年对外公开监管信息14560条 2019-05-16
  • 中山八路总站调整12公交线 2019-05-16
  • 谢春涛:深刻把握“中国特色社会主义进入新时代”的重大意义 2019-05-09
  • 湖南一博士生举报水利局领导受贿 遭到冒牌纪委约谈 2019-05-09
  • 西安地铁唐风诗韵文化专列将于6月18日首发 2019-04-30
  • 铜梁区旧县街道:全面提升执行力 推动工作落地见效 2019-04-30
  • 上海电影节女性影人大放异彩 中生代女演员不用焦虑 2019-04-29
  • 体彩新时时彩 山东群英会最新开奖号查询结果 上海快三当前遗漏 天天乐22选5开奖走势 天津时时彩五星走势 贵州十一选五历次开奖查询 秒速时时彩倍投法 黑龙江11选5加盟条件 云南11选5怎么追号 微信可以购买体彩吗 网球比分和淄博 澳洲幸运10开奖结果 新疆11选5任选 幸运农场平台 白小姐六合彩第130