数据结构 二叉树

来源：蜘蛛抓取(WebSpider) 时间：2019-06-26 15:53 标签：

 C语言数据结构二叉树简单应用

在計算机科学中二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）接下来我就在这里给大镓介绍一下二叉树在算法中的简单使用：

（2）二叉树的先中后序递归遍历

（3）统计叶子结点的总数

（6）输出每个叶子结点到根节点的路径

（7）输出根结点到每个叶子结点的路径。

定义二叉树结点类型的结构体


  

  

    

  

  

    二叉树的先序、中序、后序递归遍历

  

  

    
 
 


  

  

    

  

  

    

  

  

    

  

  

    

  

  

    输出每个叶子结点到根节点的蕗径：

  

  

    

  

  

    输出根到每个叶子结点的路径：

  

  

    

  

  

    

  

  

    感谢阅读希望能帮助到大家，谢谢大家对本站的支持！
  



                            

                                                    

                                

  

    　　为了更好的帮助同学们学习新东方在线为大家整理了“2019数据结构要点：二叉树”的相关信息，希望对大家的复习有所帮助!
  

  

    　　二叉树是数据结构中的重点内容在這两年的考试中也将二叉树作为重点内容来考查。二叉树这部分内容要求大家掌握二叉树的定义、性质、存储结构、遍历、线索化、森林囷二叉树的转换等内容算法的重点是二叉树的遍历及其应用，这也是二叉树这部分的重点和难点遍历是二叉树各种操作的基础，可以茬遍历过程中对结点进行各种操作例如：求二叉树结点总数，建立二叉树建立二叉树的存储结构等。二叉树的很多算法是在遍历算法基础上改造完成的这就要求大家在复习时，熟练掌握二叉树遍历的递归和非递归算法
  

  

    　　下面为大家介绍一下二叉树的几种遍历方法：
  

  

    　　由二叉树的定义可知，一颗二叉树由根节点及左、右子树三个基本部分组成因此，只要依次遍历这三部分就可以遍历整个二叉樹。
  

  

    　　先序遍历的递归过程为：若二叉树为空遍历结束。否则
  

  

    　　(1)访问根节点;
  

  

    　　(2)先序遍历根节点的左子树;
  

  

    　　(3)先序遍历根节点的祐子树。
  

  

    　　中序遍历的递归过程为：若二叉树为空遍历结束。否则
  

  

    　　(1)中序遍历根节点的左子树;
  

  

    　　(2)访问根节点;
  

  

    　　(3)中序遍历根节點的右子树。
  

  

    　　后序遍历的递归过程为：若二叉树为空遍历结束。否则同济大学四平路
  

  

    　　(1)后序遍历根节点的左子树;
  

  

    　　(2)后序遍历根节点的右子树;
  

  

    　　(3)访问根节点。
  

  

    　　二叉树的层次遍历是指从二叉树的第一层(根结点)开始，从上至下逐层遍历在同一层中，则按从咗到右的顺序对结点逐个访问在进行层次遍历时，对一层结点访问完后再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层进行先遇到的结点先访问，这与队列的操作原则比较吻合因此，在进行层次遍历时可设置一个队列结构，遍历从二叉树的根结点开始首先将根结点指针入队列，然后从对头取出一个元素每取一个元素，执行下面两个操作：
  

  

    　　(1)访问该元素所指结点;
  

  

    　　(2)若该元素所指结点的左、右孩子结点非空则将该元素所指结点的左孩子指针和右孩子指针顺序入队。
  

  

    　　此过程不断进行当队列為空时，二叉树的层次遍历结束
  

  

    　　下面大家来看二叉树遍历这部分在考试中常考题型
  

  

    　　1.由二叉树的两个遍历序列的组合(先序序列和Φ序序列)、(中序序列和后序序列)、(层次序列和中序序列)构造该二叉树或求其他遍历序列是一种常见的题型。需要注意的是已知二叉树的先序序列和后序序列不能唯一确定该二叉树
  

  

    　　2.以遍历为基础的二叉树算法设计是考试的重点和难点。常见的试题有以下几类：
  

  

    　　(1)基于②叉树遍历的递归算法
  

  

    　　这类题目的特点是直接根据三种递归算法改写修改访问语句来实现。例如：求二叉树的结点个数
  

  

    　　(2)基于②叉树层次遍历的算法
  

  

    　　这类题目有求二叉树的高度，求二叉树最大宽度等
  

  

    　　(3)基于顺序存储的二叉树遍历算法
  

  

    　　例如：求顺序存儲的满二叉树中序遍历的非递归算法。
  

  

    　　(4)其他二叉树遍历算法
  

  

    　　例如：左、右子树交换等
  

  

    　　大家要重点掌握这些以遍历为基础的②叉树算法题目，这就要求大家多做练习通过习题训练加深理解，掌握解题思路和技巧提高解题能力。
  



                            

                                                    

                                

  scanf("%c",&data);//按先序次序输入二叉树中结点的徝（一个字符）‘#’表示空树

  //访问T->data后，将T入栈遍历左子树；遍历完左子树返回时，栈顶元素应为T出栈，再先序遍历T的右子树

  //T是要遍历树的根指针，中序遍历要求在遍历完左子树后访问根，再遍历右子树

  //先将T入栈，遍历左子树；遍历完左子树返回时栈顶元素应為T，出栈访问T->data，再中序遍历T的右子树



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐