常用数据结构——树的基本术语

ゝ一纸荒年。 2023-03-01 08:39 16阅读 0赞

### 文章目录 ###

*  数据结构
 *   *  什么是数据结构
     *  数据的逻辑结构
     *  链表
 *  树的概念
 *   *  树的特点
     *  树的基本术语
     *  树的定义
 *  二叉树
 *   *  二叉树的性质
     *  二叉树的定义
     *  二叉树的遍历

# 数据结构 #

## 什么是数据结构 ##

数据结构是计算机存储、组织数据的方式。指相互之间存在一种或多种特定关系的数据元素的集合。

## 数据的逻辑结构 ##

**1线性结构：数据结构中的元素存在一对一的相互关系**  
链表  
数组  
顺序表  
**2树形结构：数据结构中的元素存在一对多的相互关系**  
多叉数  
二叉树  
二叉搜索树  
**3图形结构：数据结构中的元素存在多对多的相互关系**  
有向图  
无向图  
带权图

## 链表 ##

链表的实现

template <typename T>
    class Node{
        
    public:
      T data;
      Node* next;
      Node(T data, Node *next = nullptr) :data(data), next(next){
        }
    };

`vs使用模板的时候，是无法检查出程序之中的逻辑错误的，有错误不会被检测出来`

# 树的概念 #

## 树的特点 ##

1,一种非线性的数据结构  
2,有一个根结点，可以有两个或以上的后继结点  
3,由节点或顶点和边组成的(非线性的)且不存在着任何环的一种数据结构。没有节点的树称为空(null或empty)树。  
4,一棵非空的树包括一个根或多个附加节点，所有节点构成一个多级分层结构。

## 树的基本术语 ##

`节点的度`：一个节点含有的子树的个数称为该节点的度；  
`树的度`：一棵树中，最大的节点的度称为树的度；  
`叶子节点`：度为0的节点称为叶节点；  
`双亲节点(父节点)`：若一个节点含有子节点，则这个节点称为其子节点的父节点；  
`孩子节点(子节点)`：一个节点含有的子树的根节点称为该节点的子节点；  
`兄弟节点`：具有相同父节点的节点互称为兄弟节点；  
`节点的层次`：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；  
`树的高度或深度`：树中节点的最大层次；  
`堂兄弟节点`：双亲在同一层的节点互为堂兄弟；  
`节点的祖先`：从根到该节点所经分支上的所有节点；  
`子孙`:以某节点为根的子树中任一节点都称为该节点的子孙。  
`森林`：多棵互不相交的树的集合称为森林；  
`根节点`:树的第一个节点,叫根节点

## 树的定义 ##

**定义树的节点**

//定义了一颗树
    template <typename T>
    class TreeNode{
        
    public:
      T val;                    //树的数据
      vector<TreeNode*>child;    //树的后继节点
      TreeNode* parent;         //树的父亲节点
      TreeNode(T val):val(val){
        }//树的构造方法
    };

**树的遍历**

void out()
    {
        
        std::stack<TNode<T>*> tmp;      //声明一个栈  后进先出
        tmp.push(root);                 //根节点,入栈
        while (!tmp.empty())            //栈不为空,继续循环
        {
        
            TNode<T>* node= tmp.top();//获取栈顶元素
            tmp.pop();  //出栈
            std::cout << node->getData() << " ";
    
            //遍历子节点
            for (auto n : node->child)
            {
        
                tmp.push(n);//将子节点,入栈
            }
        }
        std::cout << std::endl;
        //结束循环
    }

# 二叉树 #

## 二叉树的性质 ##

每个节点至多拥有两棵子树(即二叉树中不存在度大于2的节点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。  
1,若二叉树的层次从1开始，则在二叉树的第i层至多有2^i个节点(i>=0)  
2,高度为k的二叉树最多有2^k - 1个节点(k>=0)  
3,对任何一棵二叉树，其叶子节点(度为0)数为m, 度为2的节点数为n, 则m = n + 1  
4,二叉树一定有左右节点之分

## 二叉树的定义 ##

//定义了一颗二叉树
    template <typename T>
    class TreeNode{
        
    public:
      T val;
      TreeNode* left;           //树的左孩子
      TreeNode* right;          //树的右孩子
      TreeNode(T val):val(val){
        }//树的构造方法
    };

## 二叉树的遍历 ##

**前序遍历**  
NLR前序遍历（preorder Traversal） 先序遍历 Node-left-right  
根左右  
访问根结点。  
前序遍历左子树。  
前序遍历右子树 。  
**中序遍历**  
中序遍历(In-order Traversal) (LNR)Left Node Right  
左-根-右  
中序遍历左子树  
访问根结点  
中序遍历右子树  
**后续遍历**  
后序遍历(Postorder Traversal) LRN )Left- Right-Node  
左-右-根  
后序遍历左子树  
后序遍历右子树  
访问根结点  
**层序遍历**  
一层一层的遍历二叉树  
遍历顺序:  
从上往下  
从左到右