数据结构:第五章学习小结

Jasmineyaoyao 2020-05-31

思维导图

数据结构:第五章学习小结

算法小结

1.遍历算法

①先序遍历(中序遍历、后序遍历与之类似)

void PreOrderTraverse(BiTree T) 
{ //递归算法
   if(T)//此时树非空  若树空则直接结束
   { 
       cout << T -> data; //访问根结点 
       PreOrderTraverse(T->lchild); //遍历左子树 
       PreOrderTraverse(T->rchild); //遍历右子树 
   } 
}

先序遍历

②层次遍历(利用队列先进先出的特点)

typedef struct biTNode
{ 
    TElemType data; 
    struct biTNode *lchild, *rchild;//左右孩子指针
}BiTNode, *BiTree; //二叉树链表

void fun(BiTree T) 
{ //层次遍历
    queue<BiTNode *> q;
    q.push(T);//根结点入队
    BiTNode *p;
    while (!q.empty()) 
   { //q非空则继续访问队列
        p = q.front(); //取队头元素
        q.pop();
        if (p!=NULL)
       { 
            cout << p->data;
            q.push(p->lchild);//左孩子入队
            q.push(p->rchild); //右孩子入队
       } 
    } 
}

层次遍历(链表)

2.寻找根结点(适用于题目给出孩子结点来创建)

①在定义树的时候打包根结点,方便后续调用;

②利用check数组,将其初始化为false,后续创建树的过程中,将孩子结点的编号作为check数组下标,若出现则变为true,以此找出根结点。

其他知识点小结

1.定义数组

//第一种:在堆申请空间,推荐第一种写法
int n;
cin >> n;
int *a = new int [n];

//第二种:此时n的值可能超过栈空间的大小,c语法正确,c++不支持
int n;
cin >> n;
int a[n];

定义数组

2.动态分配数组

int *data;//定义指向data整型数组的指针
int n;
cin >> n;
data = new int[n];//使用new来申请空间 动态分配 避免浪费
delete[] data;//释放空间

动态分配数组

相关推荐