基本数据结构介绍了解


作者:coderxm 小码
公众号:小码之光

数据结构:反应数据之间的关系,物理或逻辑上的关系。

有两个角度看数据结构:逻辑结构和存储结构。逻辑结构是指数据之间的逻辑关系,有没有联系。而存储结构才是重点,数据怎么存?存成什么样?有顺序、链式、散列存储等,不过主要研究顺序和链式存储等方式,并对他们的运算进行了解。什么是顺序和链式?其实不难理解,就是容易忘(滑稽)!两者都要从逻辑和存储上看。

顺序结构:逻辑上是连续的,即可以通过任意一节点元素找到该数据元素;存储上,就是物理地址是也是相邻的,连在一块。比如顺序表。

链式结构:逻辑上同理;但是物理存储地址却不是连在一块的。比如线性链表。

那不是还有线性和非线性结构吗?这个是什么角度呢?从数据的存储方式看,分为线性和非线性。线性结构或者叫线性表,指一个数据结构中的每个节点最多有一个前驱或后继(指向作用),则为线性表,可以看作连续线状结构。非空的线性表有以下特征:

  • 只有一个前节点,或头节点,无前件。
  • 只有一个尾节点,无后件
  • 其他节点只有一个前件和后件

那么常见的线性表有这么几个:数组、栈、队列、线性链表;而相应的非线性线性表有树、二叉树、图等等。

常见数据类型介绍:

数组:这个好理解,连续的嘛!一维数组,可以通过下标找到你,而且定义一个数组,在内存上是相邻的一块,非常符合线性表的概念。

栈:特殊一点,操作都在一端进行,这端或这头叫栈顶top,相反,另一端则为栈底bottom。如果为空的话叫空栈,特点就是:FILO(first in ,last out)

栈

  • 先进后出,后进先出
  • 插入删除操作都是在栈顶进行
  • 不像线性表,插入删除操作不需要移动栈内其他元素

插入栈内为入栈或压栈,退出为出栈或退栈,读取就是将栈顶元素读取。

队列:一端插入,另一端退出删除。遵循FIFO,先进先出。那么哪里是头?哪里是尾呢?想象一下一列火车穿过隧道,火车头先进入隧道,然后尾部(Front)后进入。所以原理类似,在队尾(Rear)进行插入,在队头进行删除。

队列

树:非线性的,是可以分支和划分层次的,由n(n>=0)个结点构成,树的结点应该满足以下条件:

  • 只有一个没前驱的节点为根
  • 其余结点可以构成子树
  • 没有子结点的为叶子结点,其余为分支点或内点

一个结点的前件为父结点,后件为孩子结点,有子节点个数多少为度。结点中最大的度为树的度,最大的层数为树的深度。

二叉树:通常由一个结点和左右子树构成,每一个结点最多有两个子结点。

满二叉树:除最后一层外,每一层上的结点都有两个子节点,从第一层开始数到n层,第k层有2的n减一次方个结点,共2的n次方减一个结点。(国内是这么定义的,国外则不是,国外定义为一棵二叉树的结点要么是叶子结点,要么它有两个子结点)

国内:
满二叉树
国外:
国际二叉树

完全二叉树:一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。 也就是说,满二叉树一定是完全二叉树!
完全二叉树

完全二叉树的判定:

C++代码实现(不是本人亲写):

#include 
#include 
using namespace std;

template 
struct TreeNode
{
    T data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(const T &x) : data(x),
                           left(NULL),
                           right(NULL) {}
};
template 
bool IsComplete(TreeNode *root)
{
    //1.树为空,返回错误
    if (root == NULL) {
        return false;
    }
    //2.树不为空
    queue *> q;
    q.push(root);
    while (!q.empty()){
        TreeNode *top = q.front();
        //2.1如果该节点两个孩子都有,则直接pop
        if (top->left && top->right)  {
            q.pop();
            q.push(top->left);
            q.push(top->right);
        }
        //2.2如果该节点左孩子为空,右孩子不为空,则一定不是完全二叉树
        if (top->left == NULL && top->right   {
            return false;
        }
        //2.3如果该节点左孩子不为空,右孩子为空或者该节点为叶子节点,则该节点之后的所有结点都是叶子节点
        if ((top->left && top->right == NULL) || (top->left == NULL && top->right == NULL)) {
                      if (NULL != top->left && NULL == top->right)   {
                            q.push(top->left);    
                        }
            q.pop(); //则该节点之后的所有结点都是叶子节点
            while (!q.empty()) {
                top = q.front();
               if (top->left == NULL && top->right == NULL)  {
                    q.pop();
                }
                else  {
                    return false;
                }
            }
            return true;
        }                                                
    }                                                            
    return true;
}                                                            
//满二叉树
    //       1
    //   2       3
    // 4    5  6   7
void test1(){
    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3);
    TreeNode *node4 = new TreeNode(4);
    TreeNode *node5 = new TreeNode(5);
    TreeNode *node6 = new TreeNode(6);
    TreeNode *node7 = new TreeNode(7);
    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->left = node6;
    node3->right = node7;
    cout << IsComplete(node1) << endl;
} 
//二叉树为空
void test2(){
    cout << IsComplete(NULL) << endl;
}
//3.二叉树不为空,也不是满二叉树,遇到一个结点左孩子为空,右孩子不为空
void test3(){
    //       1
    //   2       3
    // 4    5      7
    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3);
    TreeNode *node4 = new TreeNode(4);
    TreeNode *node5 = new TreeNode(5);
    TreeNode *node7 = new TreeNode(7);
    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->right = node7;
    cout << IsComplete(node1) << endl;
} 
//4.二叉树不为空,也不是满二叉树,遇到叶子节点,则该叶子节点之后的所有结点都为叶子节点
void test4(){
    //        1
    //    2       3
    // 4    5
    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3);
    TreeNode *node4 = new TreeNode(4);
    TreeNode *node5 = new TreeNode(5);
    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    cout << IsComplete(node1) << endl;
}
//4.二叉树不为空,也不是满二叉树,遇到左孩子不为空,右孩子为空的结点,则该节点之后的所有结点都为叶子节点
void test5(){
    //        1
    //    2       3
    // 4    5   6
    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3);
    TreeNode *node4 = new TreeNode(4);
    TreeNode *node5 = new TreeNode(5);
    TreeNode *node6 = new TreeNode(6);
    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->left = node6;
    cout << IsComplete(node1) << endl;
}
int main(){
    test1();
    /*test2();*/
    /*test3();*/
    /*test4();*/
    /*test5();*/
    return 0;
}

源码连接https://blog.csdn.net/gogogo_sky/article/details/76223384

二叉树通常用链式存储,每一个元素则可以有两个后件,分别可以指向左右子结点,其链式结构又叫二叉链表。

二叉树遍历:

二叉树遍历要求不能重复访问结点,常用的有前序遍历、中序遍历、后序遍历。

  • 前序遍历Data Left Right(DLR):先访问根节点,然后遍历左子树,最后遍历右子树
  • 中序遍历Left Data Right(LDR):先遍历左子树,访问根节点,最后遍历右子树
  • 后序遍历Left Right Data(LRD):先遍历左子树,后遍历右子树,最后访问根节点

相应的文章请到博客园二叉树

公众号:小码之光(文章全部首发)


文章作者: 小码
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 小码 !
评论
 上一篇
java中的内部类 java中的内部类
java中的内部类一、内部类及访问特点1:内部类概述:把类定义在其他类的内部,这个类就被称为内部类。 理解:内部类不需要被其他外部类调用,所以内部类定义在外部类里边,连成一块2:内部类访问特点 a:内部类可以直接访问外部类的成员
2020-07-28
下一篇 
opera、google、firefox浏览器的选择 opera、google、firefox浏览器的选择
作者:coderxm公众号:小码之光 首先介绍:先介绍本人用的最多的浏览器:火狐 Mozilla Firefox,中文俗称“火狐”,是一个自由及开放源代码的浏览器,使用Gecko排版引擎,支持多种操作系统,如Windows、Mac OS及
2020-07-19
  目录