5.4.5.查找二叉树中两个结点的公共祖先结点
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; //无相同祖先顶点 }
5.4.6.求二叉树的宽度
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 }
5.4.7.求二叉树的高度
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; } }
5.4.8.排序二叉树的判定
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; //排序二叉树 } }
5.4.9.平衡二叉树的判定
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; } }
5.4.10.完全二叉树的判定
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; }
5.4.11.真题
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); }
6.图
6.1.图的数据结构定义
6.1.1.邻接矩阵
#define MAXVEX 100 typedef struct Graph { int data[MAXVEX]; //一维数组，存放顶点数据 int edge[MAXVEX][MAXVEX]; //二维数组，存放边数据（权值） int vexNum, edgeNum; //顶点总数和边总数 }Graph;
6.1.2.邻接表
#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;
6.2.图的遍历
6.2.1.深度优先遍历
#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 } }
6.2.2.广度优先遍历
#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 }
6.3.单源最短路径
#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 }
6.4.真题
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路径 }
7.快速排序
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); //递归处理右区间 }
8.折半查找
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 }
