数据结构之树(Tree)（一）

标签：BstNode Tree rootPrt 之树二叉树 return 数据结构 data 节点

数据结构之树（Tree）（一）

文章目录

数据结构之树（Tree）（一）
一、什么是树？
- 1、有关树的基本概念和术语
- 2、树的类型（二叉树）
二、二叉树的实现

一、什么是树？

在计算机科学中，树是一种常用的数据结构，用来模拟具有层次关系的数据集合。它由节点（nodes）组成，这些节点通过边（edges）连接在一起。树结构中没有循环，并且除了根节点外，每个节点有且仅有一个父节点。

1、有关树的基本概念和术语

节点 (Node)：树中的一个元素，可以包含一些数据以及指向其子节点的引用。
根 (Root)：树的最顶端节点，没有父节点。
叶子 (Leaf)：没有任何子节点的节点。
父节点 (Parent)：直接位于某个节点之上的节点。
子节点 (Child)：直接位于某个节点之下的节点。
兄弟节点 (Siblings)：拥有同一个父节点的节点。
路径 (Path)：从树的一个节点到另一个节点的序列。
深度 (Deepth)：从根节点到特定节点的路径长度。
高度 (Height)：树中从根节点到最远叶子节点的最长路径长度。

2、树的类型（二叉树）

我们这里只讨论二叉树 (Binary Tree)，即每个节点最多有两个子节点的树。

满二叉树 (Full Binary Tree)：每个节点都有两个子节点或没有子节点。
完全二叉树 (Complete Binary Tree)：除了最后一层外，每一层都是满的；最后一层的所有节点都尽可能地集中在左边。
平衡二叉树 (Balanced Binary Tree)：任何两个叶子节点的高度差不超过1。
二叉搜索树 (Binary Search Tree, BST)：左子树中的所有节点值小于其父节点值，右子树中的所有节点值大于其父节点值。

二、二叉树的实现

1、构建一个二叉树节点

一个基本的二叉树节点包含以下三个属性：

数据(Data)：节点所包含的数据。
左子节点 (left)：指向该节点的左子节点的引用。
右子节点 (right)：指向该节点的右子节点的引用。

下面是一个简单的C++结构体实现树节点：

struct BstNode{
    int data;
    BstNode* left;
    BstNode* right;
};

2、插入（Insert）操作

在二叉树中进行插入操作通常取决于二叉树的具体类型。对于一般的二叉树，插入操作比较灵活，可以自由地选择将新节点放在任何位置。但是，对于某些特殊的二叉树，如二叉搜索树（BST），插入操作必须遵循特定的规则。
二叉搜索树（BST）是一种特殊的二叉树，其中每个节点的值都大于其左子树中的所有节点的值，并且小于其右子树中的所有节点的值。因此，在二叉搜索树中插入新节点时，需要确保新节点满足这一性质。
以下是二叉搜索树（BST）的插入的代码：

BstNode* GetNewNode(int data){
    BstNode* newNode = new BstNode();
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
BstNode* Insert(BstNode* rootPrt,int data){
    if(rootPrt == NULL){//先判断是否有树
        rootPrt = GetNewNode(data);
        return rootPrt;
    }
    else if(data <= rootPrt->data){
        rootPrt->left = Insert(rootPrt->left,data);
    }
    else{
        rootPrt->right = Insert(rootPrt->right,data);
    }
    return rootPrt;//每次返回根节点
}
int main() {
    BstNode* rootPrt = NULL;
    rootPrt = Insert(rootPrt,7);
    rootPrt = Insert(rootPrt,5);
}

3、搜索（Search）操作

因为二叉搜索树的特殊性，我们在二叉树中搜索一个数据的时候,可以选择二分法进行搜索，比如，如果你想找最小的数值，那就一直往树的左下方搜就可以，如果要找最大值，就往树的右下方搜索。

bool Search(BstNode* rootPrt,int data){// 判断某个值是不是在树中
    if(rootPrt == NULL) return false;
    else if(rootPrt->data == data) return true;
    else if(data <= rootPrt->data) return Search(rootPrt->left,data);
    else return Search(rootPrt->right,data);
}
int Findmin(BstNode* rootPrt){//寻找最小值
    if(rootPrt == NULL){
        cout<<"Empty Tree"<<endl;
        return -1;
    }
    BstNode* curr = rootPrt;
    while(curr->left!=NULL) {
        curr = curr->left;
    }
    return curr->data;
}
int Findmax(BstNode* rootPrt){
    if(rootPrt == NULL){
        cout<<"Empty Tree"<<endl;
        return -1;
    }
    BstNode* curr = rootPrt;
    while(curr->right!=NULL) {
        curr = curr->right;
    }
    return curr->data;
}

标签：BstNode,Tree,rootPrt,之树,二叉树,return,数据结构,data,节点
From： https://blog.csdn.net/weixin_74772510/article/details/141474511