数据结构中一棵树根结点的特点

来源：蜘蛛抓取(WebSpider) 时间：2020-12-30 14:51 标签： 

树不同于链表和顺序表是一种非线性的数据结构，在我们的系统中树的结构随处可见，文件目录就是树

树主要用来解决一对多的数据结构，其中图中橘黄色的为树黄色的为图。

结点：树中每个结点都可以有任意数量的子节点。

根结点：没有父结点的结点称之为根结点

父结点：除了根结点外每個结点有且只能有一个父结点。

叶子结点：没有子节点的结点称之为叶子节点

兄弟结点：拥有相同父结点的结点互相称之为兄弟结点。
A 節点就是 B 节点的父节点B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点所以它们之间互称为兄弟节点。我们把没有父节點的节点叫作根节点也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点比如图中的 G、H、I、J、K、L 都是叶子节点。

结點的度：结点拥有的子节点数量就是度数

树的度：树中度数最大的结点对应的度即为树的度。

树的层数：根结点为第一层其余结点层數为双亲结点+1。(可以从0开始计数也可以从1开始计数，但不管是从谁开始计数层数都不会因为计数方法的不同而改变)

树的深度：树中层數最大的结点，从根结点到子节点

树的高度：高度和深度大小相同，但是高度是从子节点开始计算

结点之间没有任何顺序关系，可以隨意交互任意结点交换后还是相同的树。在实际场景基本没有使用

结点之间有顺序换关系，交互结点后树发生改变在编程中最常用嘚有序树是二叉树 


  

每个节点最多含有两个子树的树称为二叉树。我们列举几个常见的二叉树种类


  

    
    
      
        
          
          
          
          
          
          
          
          
          
          
          
          
          
        
        
          
            
          
          
            
          
          
            
          
          
            
          
          
            
          
          
            
          
          
            
          
          
            
          
          
            
          
          
            
          
          
            
              
            
          
          
            
          
          
            
          
        
        
          
            
              
                
              
            
          
          
            
              
                
              
            
          
          
            
              
                
              
            
          
          
            
              
                
              
            
          
          
            
              
                
              
            
          
          
            
              
                
              
            
          
          
            
              
                
              
            
          
          
            
              
                
              
            
          
          
            
              
                
                  

                    除最后一层外其余所有层都已满的二叉樹为完全二叉树，且最后一层所以结点都从左向右有序排列
                  

                
              
            
          
          
            
              
                
                  

                    所以结点都已满的的二叉树为满二叉树因为无法添加和删除元素，满二叉树佷少使用
                  

                
              
            
          
          
            
              
                
              
            
          
          
            
              
                
                  

                    任何节点的两棵子树的高度差不大于1的二叉树防止排序二叉树退出成链表。
                  

                
              
            
          
          
            
              
                
                  

                    用于信息编码和压缩等技术是带权（可以大致理解为使用次数越多权越高）路径最短的二叉树。
                  

                
              
            
          
          
            
              
                
                  

                    一种对读写操作进行优化的自平衡的二叉查找树能够保持数据有序，拥有多余两个子树主要在数据库使用率较高
                  

                
              
            
          
        
      
    
  

  




  

使用顺序存储结构的树虽然方便遍历，但占用空间较大而且在增删改查上都较为麻烦，不利于操作使用率佷少，是一种非主流的二叉树


  

链式存储和双向链表有几分相似，只是左右结点不再是放前后链表而是变成了左右结点。在链式存储中我们只需获得根结点，就可以操作整个树且方便增删改查。

这里的结点可以使用和双向链表相同的结构


  

  

  

在添加树的叶子结点时时我们采用了队列的思维把树同层的内容添加到队列中进行逐个寻找。

"""创建一个新分支"""
  

  

树的遍历相较于线性表来说较为复杂且不知一种方式。变量的主要方向为广度优先变量和深度优先变量其中广度优先变量的方式和我们上述添加结点的过程类似但使用较少，深度优先中又汾为先序遍历、中序遍历、后序遍历这三类


  
    
    
  1. 广度优先：按照层数，从左至右遍历
    
    2. 
    
      
      
    1. 先序遍历：根结点->左子树->右子树，从根结点开始输出之后优先输出左子树，最后输出右子树
      
      2. 
      
    2. 中序遍历：左子树->根结点->右子树，从左子树开始输出之后输出根结点，同样最后输出右子树
      
      3. 
      
    3. 后序遍历：左子树->右子树->根结点：从左子树开始输出，之后输出右子树最后输出根结点。
      
        三种遍历方式主要是根结点的输出位置有所變化
      
      4. 
    
    
  

  

广度优先的代码我们在添加结点的基础上略微修改即可


  

  




  



                            

                                                    

                                

  

    

      格式：PPT ? 页数：47页 ? 上传日期： 02:12:55 ? 浏览次数：4 ? ? 880积分 ? ? 用稻壳阅读器打开
    

  

  

    

      全文阅读已结束如果下载本文需要使用
    

  

  

    

      该用户还上传了这些文档
    

  



                            

                                                    

                                

  

    ?树的基本概念?二叉树?二叉树的存儲表示?二叉树的遍历及其应用?线索二叉树?树与森林?树与森林的遍历及其应用?堆?哈夫曼树及其应用第5 章树本章的主要内容是 转载请标明出处.
  



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐