5.2.二叉树的基本操作
5.2.1.先序遍历
void PreOrder(BiTree T){ if (T) { visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } }
5.2.2.中序遍历
void InOrder(BiTree T){ if (T) { InOrder(T->lchild); visit(T); InOrder(T->rchild); } }
5.2.3.后序遍历
void PostOrder(BiTree T){ if (T) { PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } }
typedef struct Stack{ BiTNode *Node[MAXSIZE]; int top; }Stack; void PostOrder(BiTree T){ Stack S; InitStack(S); BiTNode *p, *pre; while (p || !IsEmpty(S)）{ if (p) { //往左下走到尽头 Push(p); //p入栈 p = p->lchild; //进入其左子树 } else { GetTop(S, p); //查看栈顶元素 //栈顶元素的右孩子存在，并且不是上一个访问的结点 if (p->rchild && p->rchild != pre) { p = p->rchild; //进入栈顶元素的右子树 Push(p); //该结点入栈 p = p->lchild; //进入该结点左子树 } else { //栈顶元素的右孩子被访问过 Pop(S, p); //弹出栈顶元素 visit(p); //访问该结点 pre = p; //用pre标记该结点 p = NULL; //将p置空 }//if }//if }//whil }
5.2.4.层次遍历
void LevelOrder(BiTree T){ InitQueue(Q); EnQueue(Q, T); BiTNode *p; while (!IsEmpty(Q)) { DeQueue(Q, p); visit(p); if (p->lchild) EnQueue(Q, p->lchild); if (p->rchild) EnQueue(Q, p->rchild); } }
5.3.并查集
5.3.1.并查集的定义和初始化
#define MAXSIZE 100 int UFSet[MAXSIZE]; //并查集通过数组表示 void InitSet(int S[]){ for(int i = 0; i < MAXSIZE; i++) S[i] = -1; }
5.3.2.FIND操作
//FIND操作用于查找该结点的所属集合 int Find(int S[], int x) { while (S[x] >= 0) x = S[x]; //递归寻找直到该结点的值为负数（该树的根节点） return x; }
5.3.3.UNION操作
void Union(int S[], root1, root2) { //要求root1和root2是不同的集合 if (root1 == root2) return; //将root2合并到root1中 S[root2] = root1; }
5.3.4.FIND优化——压缩路径
//先找到根节点，然后进行压缩路径 int Find(int S[], x) { int root = x; while (S[root] >= 0) root = S[root]; //循环找到当前结点的根节点 while (x != root) { //循环直到x指向根节点 int temp = S[x]; //用temp保存x的父结点 S[x] = root; //将结点x的父节点修改为根节点 x = temp; //x更新为原父节点 } }
5.3.5.UNION优化——小树合并大树
//数组中根节点的值为其集合中结点的总数 void Union(int S[], root1, root2){ if (root1 == root2) return; if (root1 <= root2) { //root1的结点数更多或者二者相等 S[root1] += S[root2]; //更新root1的结点数为root1和root2的总和 S[root2] = root1; //将root2合并到root1中 } else { //root2的结点数更多 S[root2] += S[root1]; S[root1] = root2; } }
5.4.二叉树算法题
5.4.1.计算二叉树中双分支结点的个数
int count = 0; //双分支结点个数 void PreOrder(BiTree T){ if (T) { //当前结点的左右孩子都存在，count++ if (T->lchild && T->rchild) count++; if (T->lchild) PreOrder(T->lchild); //递归遍历左子树 if (T->rchild) Preorder(T->rchild); //递归遍历右子树 } void ans(BiTree T) { PreOrder(T); //先序遍历该树 cout << count; //输出双分支结点个数 }
5.4.2.交换二叉树中所有左右子树
void PostOrder(BiTree &T){ if (T) { PostOrder(T->lchild); PostOrder(T->rchild); BiTNode *t = T->lchild; T->lchild = T->rchild; T->rchild = t; } } void ans(BiTree &T){ Post(Order(T)); return; }
5.4.3.求先序遍历第k个元素
int t = 0; int res = 0; void PreOrder(BiTree T) { if (T) { t--; if (t == 0) res = T->data; //第k个结点，用res保存当前结点的值 PreOrder(T->lchild); //递归访问左子树 PreOrder(T->rchild); //递归访问右子树 } } void ans(BiTree T, int k) { t = k; PreOrder(T); cout << res; //输出第k个结点的值 }
5.4.4.删去值为x的子树
int k; void Delete(BiTree &T){ //后序遍历的方式删除结点 if (T) { DeleteX(T->lchild); DeleteX(T->rchild); free(T); } } void PreOrder(BiTree &T) { if (T) { BiTNode *t; if (T->lchild->data == k) { //左子树的值为x，删除左子树 t = T->lchild; T->lchild = NULL; Delete(t); } if (T->rchild->data == k) { //右子树的值为x，删除右子树 t = t->rchild; T->rchild = NULL; Delete(t); } if (T->lchild) PreOrder(T->lchild); //递归遍历左子树 if (T->rchild) PreOrder(T->rchild); //递归遍历右子树 }//if } void ans(BiTree &T, int x){ k = x; if (T->data == x) { //根节点的值为x，删除整个树并返回 Delete(T); return; } else PreOrder(T); //先序遍历x }
void Delete(BiTree &T) { //后序遍历，并删除结点 if (T) { Delete(T->lchild); Delete(T->rchild); free(T); } } void LevelOrder(BiTree &T, int x){ if (T->data == x) { //根节点的值为x，删除整个树，并返回 Delete(T); return; } Queue Q; InitQueue(Q); //初始化队列 BiTNode *p = T; EnQueue(Q, p); //根节点入队 while (!IsEmpty(Q)) { DeQueue(Q, p); if (p->lchild) { if (p->lchild->data == x) { BiTNode *q = p->lchild; p->lchild = NULL; //左孩子指针置空 Delete(q); //以q为根节点的子树 } else EnQueue(Q, p); } if (p->rchild) { {} if (p->rchild->data == x) { BiTNode *q = p->rchild; p->rchild = NULL; Delete(q); } else EnQueue(Q, p); } }//while }
