数据结构学习小记-树(Data structure learning notes – tree)

1.一种非线性结构,属于图均属于非线性结构。

  • 树是由结点或顶点和边组成的,不存在任何环的结构,没有结点的树称为空,null,一棵非空的树包括一个根节点,还有很多附加结点,所有结点构成一个多级分层结构。
  • 树的定义:n个节点组成的有限集合。n=0,空树;n>0,1个根节点,m个互不相交的有限集,每个子集为根的子树。
  • 节点的度:树中某个节点的子树的个数;树的度:树中各节点的度的最大值;分支节点:度不为零的节点;叶子节点:度为0的节点;路径:i>j;路径长度;路径经过节点数目减一;孩子节点:某节点的后继结点;双亲节点:该节点为其孩子节点的双亲节点(父母节点);兄弟节点:同一双亲的孩子节点;子孙节点:某节点所有子树中的节点;祖先节点:从树节点到该节点的路径上的节点;
  • 节点的层次:根节点为第一层(以此类推);树的高度;树中节点的最大层次;有序树:树中节点子树按次序从左向右安排,次序不能改变;无序树;与之相反;森林:互不相交的树的集合。
  • 树的性质:树的节点树为所有节点度数加1(加根节点);度为m的树中第i层最多有m(i-1)个节点;高度为h的m次树至多有(mh-1)/(m-1)个节点;具有n个节点的m次树的最小高度为logm(n(m-1)+1)向上取整。

二叉树

  • 二叉树是n个节点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组成。每一个节点最多拥有一个左节点和一个右节点,并没有多余的节点;
  • 二叉树的特点:每个节点最多有两棵子树,所以二叉树中不存在度大于2的节点。左子树和右子树是有顺序的,次序不能任意点颠倒;即使树中某节点只有一棵子树,也要区分是左子树还是右子树;
  • 性质:二叉树的第i层上的节点数目最多为2(i-1)个节点;深度为k的二叉树至多有2k -1 个节点;包含n个节点的二叉树的高度至少为log2(n+1);在任意一棵二叉树中,若终端节点的个数为n0,度为2的节点树为n2,则n0 = n2+1;

几种特殊的二叉树

  • 斜树:

    所有的节点都只有左子树的二叉树叫左斜树。所有节点都是只有右子树的二叉树叫右斜树。统称为斜树。

  • 所有的节点都只有左子树的二叉树叫左斜树。所有节点都是只有右子树的二叉树叫右斜树。统称为斜树。
  • 满二叉树:

    在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。所有叶子只能出现在最下一层。出现在其他层就不可能达成平衡;非叶子节点的度一定是2;在同样深度的二叉树中,满二叉树的节点个数最多,叶子树最多;

  • 在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。所有叶子只能出现在最下一层。出现在其他层就不可能达成平衡;非叶子节点的度一定是2;在同样深度的二叉树中,满二叉树的节点个数最多,叶子树最多;
  • 完全二叉树:

    对一颗具有n个节点的二叉树按层编号,如果编号为i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。

  • 对一颗具有n个节点的二叉树按层编号,如果编号为i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。

二叉树的存储

  • 一颗二叉树的结点设计一定要有如下内容:

    结点元素,data域,用来存储数据,其可以是int,char等基本的类型,同时也可以是struct等这些复杂的复合数据类型。

    左孩子结点,left指针,总是用来指向当前结点的下一层的左边结点,其属于一种指针。

    右孩子结点,right指针,总是用来指向当前结点的下一层的右边结点,其属于一种指针。

    父结点(可选),parent指针,总是指向当前结点的前一个结点,简称父亲结点,其不属于必须结点设计,省略掉可以节省内存的效果,而使用则可以更方便进行定向搜索,以上就是一颗二叉树的结点设计,除此之外,我们使用一棵树的时候需要建立一颗树根,由这个“根”,来进行逐步的向下构建。

    typedef struct node{
    int data;
    struct node* left;
    struct node* right;
    } Node;

    //树根
    typedef struct {
    Node* root;
    } Tree;

  • 结点元素,data域,用来存储数据,其可以是int,char等基本的类型,同时也可以是struct等这些复杂的复合数据类型。
  • 左孩子结点,left指针,总是用来指向当前结点的下一层的左边结点,其属于一种指针。
  • 右孩子结点,right指针,总是用来指向当前结点的下一层的右边结点,其属于一种指针。
  • 父结点(可选),parent指针,总是指向当前结点的前一个结点,简称父亲结点,其不属于必须结点设计,省略掉可以节省内存的效果,而使用则可以更方便进行定向搜索,以上就是一颗二叉树的结点设计,除此之外,我们使用一棵树的时候需要建立一颗树根,由这个“根”,来进行逐步的向下构建。
  • 树的创建:

    首先,我们创建一个空的结点再进行连接,首先将这个空的结点中的data域赋予数据,再判断tree中是否是一个空树,如果为空,只需要将整个根指向这一个结点即可,如果不为空,再进行两个判断.

  • 首先,我们创建一个空的结点再进行连接,首先将这个空的结点中的data域赋予数据,再判断tree中是否是一个空树,如果为空,只需要将整个根指向这一个结点即可,如果不为空,再进行两个判断.
  • 树的遍历之先序遍历二叉树:

    树作为非线性数据结构,在我们取出数据时就需要设计遍历,所谓遍历,就是按照一定的规则性,将数据结构中的所有数据全部依次访问,而二叉树本身并不具有天然的全局次序,故为实现遍历,需通过在各节点与其孩子之间约定某种局部次序,间接地定义某种全局次序,这便是我们常规定的先序,中序,后序遍历。

    先序遍历:根左右
    中序遍历:左根右
    后序遍历:左右根

  • 树作为非线性数据结构,在我们取出数据时就需要设计遍历,所谓遍历,就是按照一定的规则性,将数据结构中的所有数据全部依次访问,而二叉树本身并不具有天然的全局次序,故为实现遍历,需通过在各节点与其孩子之间约定某种局部次序,间接地定义某种全局次序,这便是我们常规定的先序,中序,后序遍历。
————————

tree

1. A nonlinear structure, which belongs to the graph and belongs to the nonlinear structure.

  • A tree is composed of nodes or vertices and edges. There is no ring structure. A tree without nodes is called empty and null. A non empty tree includes a root node and many additional nodes. All nodes form a multi-level hierarchical structure.
  • Definition of tree: a finite set of N nodes. N = 0, empty tree; n> 0,1 root nodes, m disjoint finite sets, and each subset is a subtree of the root.
  • Node degree: the number of subtrees of a node in the tree; Degree of tree: the maximum degree of each node in the tree; Branch node: node whose degree is not zero; Leaf node: node with degree 0; Path: I > J; Path length; The number of nodes passed by the path is reduced by one; Child node: the successor node of a node; The node is the parent of the node; Sibling node: the child node of the same parent; Descendant node: nodes in all subtrees of a node; Ancestor node: the node on the path from the tree node to the node;
  • Level of node: the root node is the first level (and so on); The height of the tree; The maximum level of nodes in the tree; Ordered tree: the node subtrees in the tree are arranged from left to right in order, and the order cannot be changed; Disordered tree; On the contrary; Forest: a collection of disjoint trees.
  • Nature of tree: the node tree of the tree is the degree of all nodes plus 1 (plus root node); There are at most M (i-1) nodes in the i-th layer of the tree with degree m; At most (MH-1) / (m-1) nodes can be found in m-trees with height h; The minimum height of m-degree tree with n nodes is logm (n (m-1) + 1), rounded up.

Binary tree

  • A binary tree is a finite set of N nodes, which is either an empty set (called an empty binary tree), or consists of a root node and two disjoint left and right subtrees called root nodes respectively. Each node has at most one left node and one right node, and there are no redundant nodes;
  • Characteristics of binary tree: each node has at most two subtrees, so there are no nodes with a degree greater than 2 in the binary tree. The left subtree and the right subtree are in order, and the order cannot be reversed at any point; Even if a node in the tree has only one subtree, it is necessary to distinguish whether it is a left subtree or a right subtree;
  • Nature: the maximum number of nodes on layer I of binary tree is 2 (i-1) nodes; A binary tree with a depth of K has at most 2K – 1 nodes; The height of a binary tree containing N nodes is at least log2 (n + 1); In any binary tree, if the number of terminal nodes is N0 and the node tree with degree 2 is N2, then N0 = N2 + 1;

Several special binary trees

  • Oblique tree:
    A binary tree in which all nodes have only a left subtree is called a left skew tree. A binary tree whose nodes are all right subtrees is called a right skew tree. Collectively referred to as oblique trees.
  • A binary tree in which all nodes have only a left subtree is called a left skew tree. A binary tree whose nodes are all right subtrees is called a right skew tree. Collectively referred to as oblique trees.
  • Full binary tree:
    In a binary tree, if all branch nodes have left and right subtrees, and all leaves are on the same layer, such a binary tree is called full binary tree. All leaves can only appear in the lowest layer. If it appears in other layers, it is impossible to reach a balance; The degree of non leaf node must be 2; In the same depth binary tree, the full binary tree has the most nodes and the leaf subtree is the most;
  • In a binary tree, if all branch nodes have left and right subtrees, and all leaves are on the same layer, such a binary tree is called full binary tree. All leaves can only appear in the lowest layer. If it appears in other layers, it is impossible to reach a balance; The degree of non leaf node must be 2; In the same depth binary tree, the full binary tree has the most nodes and the leaf subtree is the most;
  • Complete binary tree:
    A binary tree with n nodes is numbered by layer. If the node numbered I (1 < = I < = n) and the node numbered I in the full binary tree with the same depth are in the same position in the binary tree, the binary tree is called a complete binary tree.
  • A binary tree with n nodes is numbered by layer. If the node numbered I (1 < = I < = n) and the node numbered I in the full binary tree with the same depth are in the same position in the binary tree, the binary tree is called a complete binary tree.

Storage of binary tree

  • The node design of a binary tree must include the following contents:
    Node elements and data fields are used to store data. They can be basic types such as int and char, as well as complex composite data types such as struct.
    Left child node, left pointer, is always used to point to the left node of the next layer of the current node. It belongs to a pointer.
    Right child node, a right pointer, is always used to point to the right node of the next layer of the current node. It belongs to a pointer.
    The parent node (optional) and the parent pointer always point to the previous node of the current node, referred to as the parent node for short. It does not belong to the required node design. Omitting the effect of saving memory can make it more convenient for directional search. The above is the node design of a binary tree. In addition, when we use a tree, we need to establish a tree root, which is used to build it step by step.
    typedef struct node{
    int data;
    struct node* left;
    struct node* right;
    } Node;
    //Tree root
    typedef struct {
    Node* root;
    } Tree;
  • Node elements and data fields are used to store data. They can be basic types such as int and char, as well as complex composite data types such as struct.
  • Left child node, left pointer, is always used to point to the left node of the next layer of the current node. It belongs to a pointer.
  • Right child node, a right pointer, is always used to point to the right node of the next layer of the current node. It belongs to a pointer.
  • The parent node (optional) and the parent pointer always point to the previous node of the current node, referred to as the parent node for short. It does not belong to the required node design. Omitting the effect of saving memory can make it more convenient for directional search. The above is the node design of a binary tree. In addition, when we use a tree, we need to establish a tree root, which is used to build it step by step.
  • Tree creation:
    First, we create an empty node and then connect. First, we assign the data field in the empty node to the data, and then judge whether the tree is an empty tree. If it is empty, we only need to point the whole root to this node. If it is not empty, we will make two more judgments
  • First, we create an empty node and then connect. First, we assign the data field in the empty node to the data, and then judge whether the tree is an empty tree. If it is empty, we only need to point the whole root to this node. If it is not empty, we will make two more judgments
  • The first order of tree traversal traverses the binary tree:
    As a nonlinear data structure, the tree needs to be traversed when we take out the data. The so-called traversal is to access all the data in the data structure in turn according to certain rules, while the binary tree itself does not have a natural global order. Therefore, in order to realize traversal, we need to define a global order indirectly by agreeing a local order between each node and its children, which is the order we often specify, Middle order, post order traversal.
    Preorder traversal: about the root
    Middle order traversal: left root right
    Post order traversal: left and right roots
  • As a nonlinear data structure, the tree needs to be traversed when we take out the data. The so-called traversal is to access all the data in the data structure in turn according to certain rules, while the binary tree itself does not have a natural global order. Therefore, in order to realize traversal, we need to define a global order indirectly by agreeing a local order between each node and its children, which is the order we often specify, Middle order, post order traversal.