412数据结构学习强化——常见数据结构定义和算法总结（五）-阿里云开发者社区

BiTNode *ans(BiTree ROOT, BiTNode *p, BiTNode *q) {
  Stack S, Sp, Sq;  //Sp和Sq分别用来保存p和q的祖先结点
  S.top = -1; //初始化队列
  BiTNode* t = ROOT, *pre = NULL;
  while (t || S.top >= 0) {
    if (t) {  //t结点非空
      S.data[++S.top] = t;  //t结点入队
      t = t->lchild;  //进入t的左子树
    }
    else {  //t结点为空
      t = S.data[S.top];  //查看栈顶元素
            //t的右子树存在，并且上一个访问的并不是其右子树
      if (t->rchild && t->rchild != pre) {  
        t = t->rchild;  //进入右子树
        S.data[++S.top] = t;  //入栈该结点
        t = t->rchild;  //进入左子树
      }
      else {  //右子树不存在，或者存在但是上一个访问的是右子树
        S.top--;  //出栈该结点，并访问
        if (t == p) { //当前结点为p，保存栈中内容，即其所有祖先结点
          for (int i = 0; i < S.top; i++) Sp.data[i] = S.data[i];
          Sp.top = S.top;
        }
        if (t == q) { //当前结点为q，保存栈中内容，即其所有祖先结点
          for (int i = 0; i < S.top; i++) Sq.data[i] = S.data[i];
          Sq.top = S.top;
        }
      }//if
    }//if
  }//while
    //自栈顶到栈顶分别遍历Sp和Sq找到最接近栈顶的相同祖先结点
  for (int i = Sp.top; i >= 0; i--) { 
    for (int j = Sq.top; i >= 0; j--) {
      if (Sp.data[i] == Sq.data[j]) return Sp.data[i];
    }
  }
  return NULL;  //无相同祖先顶点
}

typedef struct Queue{
    BiTNode *data[MAXSIZE];    //足够大的数组
    int front, rear;
}Queue;
int ans(BiTree T){
    if (!T) return 0;    //空树，返回0
    BiTNode *p = T;
    Queue Q;
    InitQueue(Q);    //初始化队列
    EnQueue(Q, p);    //将p入队
    //rear指向当前层的最后一个结点，count记录当前层的结点数，max记录最大结点数
    int last = Q.rear, count = 0, max = INT_MIN;    
    while (!IsEmpty(Q) {
        DeQueue(Q, p);
        count++;    //结点数+1
        if (p->lchild) EnQueue(Q, p->lchild);    //p的左子树存在，左子树入队
        if (p->rchild) EnQueue(Q, p->rchild);    //p的右孩子存在，右孩子入队
        if (last == Q.front) {    //当前结点是本层的最后一个节点
            last = Q.rear;    //last指向下一层的最后一个结点
            if (count > max) max = temp;    //更新最大结点数
            count = 0;    //结点数归零
        }
    }//while
    return max;
}

typedef struct Queue {  //足够大的非循环数组
  BiTNode *data[MAXSIZE]; //结点数组，保存每个结点
  int level[MAXSIZE]; //层数数组，记录每个结点的层数
  int front, rear;  //头尾指针
}Queue;
int ans(BiTree T) {
  BiTNode* p = T;
  Queue Q;
  Q.rear = Q.front = 0; //初始化队列
  if (T) {
    Q.data[Q.rear] = T; //根节点入队
    Q.level[Q.rear] = 1;
    Q.rear++;
    while (Q.front < Q.rear) {
      p = Q.data[Q.front];  //出队队首元素
      int level = Q.level[Q.front]; //保存当前结点的层数
      Q.front++;
      if (p->lchild) {  //左孩子入队
        Q.data[Q.rear] = p->lchild;
        Q.level[Q.rear] = level + 1;
        Q.rear++;
      }
      if (p->rchild) {  //右孩子入队
        Q.data[Q.rear] = p->rchild;
        Q.level[Q.rear] = level + 1;
        Q.rear++;
      }
    }//while
    int max = INT_MIN, i = 0, level = 1;
    while (i <= Q.rear) {
      int count = 0;  //记录当前层的结点数
      while (i <= Q.rear && level == Q.level[i]) {
        count++;
        i++;
      }
      if (count > max) max = count; //更新每层的最大结点数
      level = Q.level[i]; //更新层数，while循环结束时，i指向下一层的第一个结点
    }//while
    return max; //返回最大结点数
  }
  else return 0;  //空树，返回0
}

int Get_Heigh(BiTree T) {
  int front = 0, rear = 0;  //前后指针
  BiTNode* p = T;
  BiTNode *data[MAXSIZE]; //足够大的队列，元素是二叉树结点
  data[rear++] = p; //根节点入队
  int last = rear, level = 0; //rear标记本层最后一个结点, level记录当前层数
  while (front < rear) {  //循环直到队空
    p = data[front++];  //出队队首结点
    if (p->lchild) data[Q.rear++] = p->lchild;  //左右孩子入队
    if (p->rchild) data[Q.rear++] = p->rchild;
    if (last == front) {  //当前结点为本层的最后一个结点
      last = rear;  //标记下层的最后一个结点
      level++;  //层数+1
    }
  }//while
  return level;
}

int Get_High(BiTree T){
    if (!T) return 0;    //空树返回0
    else {
        int hl = Get_High(T->lchild);    //递归求左右子树高度
        int hr = Get_High(T->rchild);
        int maxH = max(hl, hr) + 1;    //树高等于左右子树更高的那个+1
        return maxH;
    }
}

int pre = INT_MIN;  //标记上一个结点的值，初始值为INT类型的最小值
int JudgeBST(BiTree T) {
  if (!T) return 1; //空树，是排序二叉树
  else {
    int l = JudgeBST(T->lchild);  //判断左子树
        //当前值小于等于pre的值，或左子树不满足排序二叉树定义，返回0
    if (T->data <= pre|| l == 0) return 0;
    pre = T->data;  //更新pre为当前结点值
    int r = JudgeBST(T->rchild);  //判断右子树
    return r;
  }
}

int A[n]; //足够大的数组，保存每个节点的值
int count = 0;  //记录结点个数
void InOrder(BiTree T) {
  if (T) {
    InOrder(T->lchild); 
    A[count++] = T->data; //记录当前结点值，并且count+1
    InOrder(T->rchild);
  }
}
bool ans(BiTree T) {
  if (!T) return true;  //空树为排序二叉树
  else if (!T->lchild && !T->rchild) return true; //只有根节点，是排序二叉树
  else {
    InOrder(T); //中序遍历二叉树，并且记录每个结点的值
    for (int i = 0; i < count - 1; i++) {
      if (A[i] >= A[i + 1]) return false; //非排序二叉树
    }
    return true;  //排序二叉树
  }
}

int Get_Height(BiTree T) {
  if (!T) return 0;
  else {
    int hl = Get_Height(T->lchild); //递归求左子树高度
    int hr = Get_Height(T->rchild); //递归求右子树高度
    int maxH = max(hl, hr) + 1; //树高为左右子树更高的那个 + 1
    return maxH;  
  }
}
bool JudgeBalance(BiTree T) {
  if (!T) return true;  //空树为平衡二叉树
  else {
    int hl = Get_Height(T->lchild); //左子树高度
    int hr = Get_Height(T->rchild); //右子树高度
    //当前结点的左右平衡因子小于等于1，递归判断其左右子树是否满足平衡二叉树
    if (abs(hl - hr) <= 1) {
            return JudgeBalance(T->lchild) && JudgeBalance(T->rchild);
        }
    //当前节点左右平衡因子大于1，则已不满足平衡二叉树，无需判断左右子树，返回false
    else return false;
  }
}

bool JudgeComplete(BiTree T) {
  BiTNode* data[MAXSIZE]; //足够大的队列
  int front = 0, rear = 0;  //头尾指针
  BiTNode* p = T; 
  data[rear++] = T; //根节点入队
  while (front < rear) {  //循环直到队空
    p = data[front++];  //出队队首元素
    if (p) {  //p结点存在，入队左右孩子
      data[rear++] = p->lchild;
      data[rear++] = p->rchild;
    }
    else {  //p结点不存在，出队剩余元素
      while (front < rear) {
        p = data[front++];
        if p == NULL return false;  //当前元素为空，则为非完全二叉树
      }
    }
  }
  return true;
}

int WPL = 0;
void InOrder(BiTree T, int deep){
    if (T) {
        if (!T->left && !T->right) {    //叶子结点
            WPL = WPL + T.weight * deep;    //更新WPL
        }
        if (T->left) InOrder(T->left, deep + 1);
        if (T->right) InOrder(T->right, deep + 1);
    }
}
int ans(BiTree T){
    InOrder(T, 0);
    return WPL;
}

int Get_WPL(BiTree root) {
  BiTNode* data[MAXSIZE]; //足够大的非循环数组
  BiTNode* p = root;
  int f = 0, r = 0, level = 0, WPL = 0, last = 0; 
  data[r++] = p;  //根节点入队
  last = r; //last标记本层的最后一个元素
  while (f < r) {
    p = data[f++];  //队首元素出队
        //该结点为叶子结点，计算WPL
    if (!p->lchild && !p->rchild) WPL = WPL + level * p->weight;
    if (p->lchild) data[r++] = p->left; //左右孩子入队
    if (p->rchild) data[r++] = p->right;
    if (last == f) {  //该结点为本层的最后一个结点
      last = r; //更新last和level
      level++;
    }
  }
    return WPL;
}

void InOrder(BiTree T, int deep){
    if (T) {
        if (deep > 1 && (T->lchild || T->rchild)) cout << '(';    //分支节点打印左括号
        if (T->lchild) InOrder(T->lchild, deep + 1);
        cout << T->data;
        if (T->rchild) InOrder(T->rchild, deep + 1);
        if (deep > 1 && (T->lchild || T->rchild)) cout << ')';    //分支节点打印右括号
    }
}
void ans(BiTree T){
    InOrder(T, 1);
}

#define MAXVEX 100
typedef struct Graph {
    int data[MAXVEX];    //一维数组，存放顶点数据
    int edge[MAXVEX][MAXVEX];    //二维数组，存放边数据（权值）
    int vexNum, edgeNum;    //顶点总数和边总数
}Graph;

#define MAXVEX 100
typedef struct edgeNode {    //边
    struct edgeNode *next;    //指向下一条邻接边的指针
    int weight;    //该邻接边权值
    int adjVex;    //该邻接边指向的顶点编号
}edgeNode;
typedef struct vexNode {    //顶点
    edgeNode *firstEdge;    ///指向该顶点的第一条邻接边
    int vexData;    //该顶点数据
}vexNode;
typedef struct Graph {    //图
    int vexNum, edgeNum;    //顶点数，边数
    vexNode vex[MAXVEX];    //vexNode类型的一维数组vex
}Graph;

#define MAXVEX 100
bool visited[MAXVEX];    //visited数组记录该顶点是否被访问过
void DFSTraverse (Graph G) {
    for (int i = 0; i < G.vexNum; i++) {
        visited[i] = false;    //初始化visited数组
    }
    for (int i = 0; i < G.vexNum; i++) {
        if (!visited[i]) DFS (G, i);    //当前顶点未被访问过，则访问
    }
}
void DFS (Graph G, int v) {
    visit (v);    //访问顶点v（具体操作）
    visited[v] = true;    //更新visited数组
    for (int w = FirstNeighbor (G, v); w >= 0; w = NextNeighbor (G, v, w)){
        if (!visited[w]) DFS(G, w);    //递归调用DFS
    }
}

#define MAXVEX 100
Queue Q;
bool visited[MAXVEX];
void BFSTraverse (Graph G) {
    for (int i = 0; i < G.vexNum; i++) {    //初始化visited数组
        visited[i] = false;    
    }
    InitQueue Q;    //初始化队列Q
    for (int i = 0; i < G.vexNum; i++) {    //遍历图
        if (!visited[i]) BFS(G, i);
    }
}
void BFS (Graph G, int v) {
    visit(v);    //访问该顶点（具体操作）
    visited[v] = true;    //更新visited数组
    EnQueue(Q, v);    //将v结点入队
    int w;
    while(!IsEmpty(Q)) {
        DeQueue(Q, v);    //队首元素出队
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
            if (!visited[w]) {    //顶点未被访问过
                visit(w);
                visited[w] = true;
                EnQueue(Q, w);
            }
        }//for
    }//while
}

#define MAXVEX 100
bool visited[MAXVEX];
int dis[MAXVEX];
Queue Q;
void Min_Dis (Graph G, int v) {
    for (int i = 0; i < G.vexNum; i++) {    //初始化visited数组和dis数组
        visited[i] = false;
        dis[i] = INT_MAX;
    }
    visited[v] = true;
    dis[v] = 0;
    InitQueue(Q);
    EnQueue(Q, v);
    int w;
    while (!IsEmpty(Q)) {
        DeQueue(Q, v);
        for (w = FisrtNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w) {
            if (!visited[w]) {
                visited[w] = true;
                dis[w] = dis[v] + 1;
            }
        }//for
    }//while
}

int IsExistEL(MGraph G){
    int count = 0;    //记录该图中度为奇数的顶点个数
    int i, j;
    for (i = 0; i < G.numVertices; i++){    //行遍历邻接矩阵
        int degree = 0;
        for (j = 0; j < G.numVertices; j++){    //列遍历当前行
            if (Edge[i][j] > 0) degree++;    //当前数组元素不为0，则度+1
        }
        if (degree % 2) count++;    //当前顶点的度为奇数，count++
    }
    if (count == 0 || count == 2) return 1;    //奇数顶点个数为0或者2，有EL路径
    else return 0;    //奇数顶点个数不为0或者2，没有EL路径
}

void QSort(int A[], L, R) {    //快速排序
    if (L >= R) return;    //当前数组长度 <= 1，返回
    随机选择数组中一元素和A[L]互换    //快排优化，使得基准元素的选取随机
    int key = A[L], i = L, j = R;
    while (i < j) {
        while (i < j && key < A[j]) j--;
        while (i < j && A[i] <= key) i++;
        if (i < j) swap (A[i], A[j]);    //交换A[i]和A[j]
    }
    swap (A[i], A[L]);
    Qsort (A, L, i - 1);    //递归处理左区间
    Qsort (A, i + 1, R);    //递归处理右区间
}

int Binary_Search (int A, L, R, key) {
    int mid;
    while (L < R) {    //L >= R时，范围错误
        mid = (L + R) / 2;    //选择中间数，向下取整
        if (key <= A[mid]) R = mid;    //更新范围
        else L = mid + 1;
    }
    if (A[mid] == key) return mid;    //查找成功，返回数组下标
    else return -1;    //查找失败，返回-1
}

412数据结构学习强化——常见数据结构定义和算法总结（五）

5.4.5.查找二叉树中两个结点的公共祖先结点

5.4.6.求二叉树的宽度

5.4.7.求二叉树的高度

5.4.8.排序二叉树的判定

5.4.9.平衡二叉树的判定

5.4.10.完全二叉树的判定

5.4.11.真题

6.图

6.1.图的数据结构定义

6.1.1.邻接矩阵

6.1.2.邻接表

6.2.图的遍历

6.2.1.深度优先遍历

6.2.2.广度优先遍历

6.3.单源最短路径

6.4.真题

7.快速排序

8.折半查找

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

412数据结构学习强化——常见数据结构定义和算法总结（五）

5.4.5.查找二叉树中两个结点的公共祖先结点

5.4.6.求二叉树的宽度

5.4.7.求二叉树的高度

5.4.8.排序二叉树的判定

5.4.9.平衡二叉树的判定

5.4.10.完全二叉树的判定

5.4.11.真题

6.图

6.1.图的数据结构定义

6.1.1.邻接矩阵

6.1.2.邻接表

6.2.图的遍历

6.2.1.深度优先遍历

6.2.2.广度优先遍历

6.3.单源最短路径

6.4.真题

7.快速排序

8.折半查找

热门文章

最新文章

相关课程

相关电子书

相关实验场景