1.二叉树的先中后序遍历
1.1.先中后序遍历的基本概念
- 先序遍历：根→左→右：ABDECFG
- 中序遍历：左→根→右：DBEAFCG
- 后序遍历：左→右→根：DEBFGCA
- 可以先按遍历的顺序写出每次递归的子树的根左右结点，然后依次按结点添加下一次递归的根左右结点，直到访问全部结点（逐层展开）
1.先序遍历：根左右→根（根左右）右→ 根（根左右）（根左右）
2.中序遍历：左根右→（左根右）根→（左根右）根（左根右）
3.后序遍历：左右根→（左右根）右根→（左右根）（左右根）根
1.2.先中后序遍历的代码实现
1.2.1.递归
typedef struct BiTNode{ elemType value; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; //先序遍历 void preOrder(BiTree T){ if(T != NULL){ visit(T); //访问根节点 preOrder(T->lchild); //递归遍历左子树 preOrder(T->rchild); //递归遍历右子树 } } //中序遍历 void inOrder(BiTree T){ if(T != NULL){ inOrder(T->lchild); //递归遍历左子树 visit(T); //访问根节点 inOrder(T->rchild); //递归遍历右子树 } } //后序遍历 void postOrder(BiTree T){ if(T != NULL){ postOrder(T->lchild); //递归遍历左子树 postOrder(T->rchild); //递归遍历右子树 visit(T); //访问根节点 } }
- #126为第126行代码，#127为第127行代码
- preOrder(A)→访问A→preOrder(A)入栈#126，进入preOrder(B)
- 访问B→preOrder(B)入栈#126，进入preOrder(D)
- 访问D→左子树为空→preOrder(D)入栈#127，进入preOrder(G)
- 访问G→左子树空→右子树空→返回preOrder(D)#127→返回preOrder(B)#126→preOrder(B)#127入栈，进入preOrder(E)
- 访问E→左子树为空→右子树为空→返回preOrder(B)#127→返回preOrder(A)#126→preOrder(A)#127入栈，进入preOrder(C)
- 访问C→preOrder(C)#126入栈，进入preOrder(F)
- 访问F→左子树为空→右子树为空→返回preOrder(C)#126→右子树为空→返回preOrder(A)#127→结束遍历
1.2.2.非递归
后序遍历非递归：栈中剩余元素都是栈顶元素的双亲结点，此特性可求根到结点的路径和两个节点的最近公共结点
#define MAXSIZE 100 typedef struct BiTNode{ struct BiTNode *lchild, *rchild; Elemtype value; }BiTNode, *BiTree; typedef struct Stack{ BiTNode data[MAXSIZE]; int top; }Stack; //先序遍历 void PreOrder(BiTree T){ Stack S; InitStack(S); BiTNode *p = T; //当p不存在并且栈空时结束循环 while(p || !(IsEmpty(S)){ if (p) { //先序遍历先访问p再入队 visit(p); push(S, p); p = p->lchild; } else{ pop(S, p); p = p->rchild); } }//while } //中序遍历 void InOrder(BiTree T){ Stack S; InitStack(S); BiTNode *p = T; while(p || !(IsEmpty(S)){ if (p){ push(S, p); p = p->lchild; } else{ //中序遍历出栈后访问p pop(S, p); visit(p); p = p->rchild; } }//while } //后序遍历 void PostOrder(BiTree T){ Stack S; InitStack(S); BiTNode *p = T, *r = NULL; while(p || !(IsEmpty(S)){ //p存在，则入栈p，进入p的左子树 if (p){ push(S, p); p = p->lchild; } //p不存在 else{ //查看栈顶元素 GetTop(S, p); //栈顶元素的右孩子未访问过，则将右孩子入栈，并且进入其左子树 if (p->rchild && p->rchild != r) { p = p->rchild; push(S, p); p = p->lchild; } //栈顶元素的右孩子访问过，则出栈并访问栈顶元素，并用r进行标记 //访问后p置空再次进入else循环 else { pop(S, p); visit(p); r = p; p = NULL; } }//else }//while }
2.二叉树的层次遍历
2.1.算法思想
- 初始化一个队列
- 将根节点入队
- 若队不空，则队头结点出队，访问该节点，并且将其左右孩子入队
- 重复3直至队列为空
2.2.代码实现
typedef struct BiTNode{ elemType value; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; typedef struct linkNode{ //存指针 BiTNode *data; struct linkNode *next; }linkNode; typedeft struct linkQueue{ linkNode *front, *rear; }linkQueue; //层次遍历 void levelOrder(BiTree T){ linkQueue Q; initQueue(Q); //初始化队列 BiTree p; enQueue(Q, T); //T入队 while(!isEmpty(Q)){ deQueue(Q, p); //p出队 visit(p); //访问p if (p->lchild) enQueue(Q, p->lchild); //p的左孩子入队 if (p->rchild) enQueue(Q, p->rchild); //p的右孩子入队 } }
3.由遍历序列构造二叉树
中序+前序/后序/层序可以确定一个二叉树
3.1.前序+中序确定一个二叉树
- 前序序列：D A E F B C H G I
- 中序序列：E A F D H C B G I
- 前序序列第一个访问的是根节点→D是根节点→左（EAF）根（D）右（HCBGI）
- 前序序列中EAF第一个访问的是根节点→A是EAF根节点→左（E）根（A）右（F）
- 前序序列中HCBGI第一个访问的是根节点→B是HCBGI根节点→左（HC）根（B）右（GI）
- 前序序列中HC第一个访问的是根节点→C是HC的根节点→左（H）根（C）
- 前序序列中GI第一个访问的是根节点→G是GI的根节点→根（G）右（I）
3.2.后序+中序确定一个二叉树
- 后序序列：E F A H C I G B D
- 中序序列：E A F D H C B G I
- 后序序列中最后访问的是根节点→D是根节点→左（EAF）根（D）右（HCBGI）
- 后序序列中EAF最后访问的是根节点→A是EAF根节点→左（E）根（A）右（F）
- 后序序列中HCBGI最后访问的是根节点→B是HCBGI根节点→左（HC）根（B）右（GI）
6.后序序列中HC最后访问的是根节点→C是HC根节点→左（H）根（C）
7.后序序列中GI最后访问的是根节点→G是GI根节点→根（I）右（G）
3.3.层序+中序确定一个二叉树
- 层次序列：D A B E F C G H I
- 中序序列：E A F D H C B G I
- 层次序列中第一个访问的是根节点→D是根节点→左（EAF）根（D）右（HCBGI）
- 层次序列中EAF第一个访问的是根节点→A是EAF根节点→左（E）根（A）右（F）
- 层次序列中HCBGI第一个访问的是根节点→B是HCBGI根节点→左（HC）根（B）右（GI）
- 层次序列中HC第一个访问的是根节点→C是HC的根节点→左（H）根（C）
- 层次序列中GI第一个访问的是根节点→G是GI的根节点→根（G）右（I）
4.线索二叉树
4.1.线索二叉树的概念
二叉树使用链式存储时会有n + 1个空指针未使用，可以将其指向该结点的前驱和后继，使得二叉树具有线性特性，从而方便遍历
规定线索二叉树中，相比传统二叉树，多两个标志位——ltag和rtag。tag用来标记指针指向的是左右孩子还是前驱后继
typedef struct threadNode{ elemType data; struct threadNode *lchild, *rchild; int ltag, rtag; }threadNode, *threarTree;
4.2.中序线索化
typedef struct threadNode{ elemType data; struct threadNode *lchild, *rchild; int ltag, rtag; }threadNode, *threadTree; //全局变量pre，指向当前当前结点的前驱结点 threadNode *pre = NULL; void inThread(threadTree &T){ if (T){ inThread(T->lchild); visit(T); inThread(T->rchild); } } void visit(threadNode *q){ //如果p节点左孩子不存在，则左孩子指向该节点的前驱结点 if (!q->lchild) { q->lchild = pre; q->ltag = 1; } //如果pre结点存在并且它的右子树为空 if (pre && !pre.rchild){ pre->rchild = q; pre->rtag = 1; } pre = q; } void createInThread(threadTree T){ pre = NULL; if(T) { inThread(T); //如果最后一个结点的右孩子为空，则改标记位 if (pre->rchild == NULL) pre->rtag = 1; } }
4.3.先序线索化
需要注意，如果不对ltag进行判断，则会进入死循环
typedef struct threadNode{ struct threadNode *lchild, *rchild; elemType data; int ltag, rtag; }threadNode, *threadTree; threadNode pre = NULL; void preThread(threadTree T){ visit(T); //防止进入死循环 if (ltag == 0) preThread(T->lchild); preThread(T->rchild); } void visit(threadTree *p){ if (p->lchild == NULL) { p->lchild = pre; p->ltag = 1; } if (pre && pre->rchild == NULL) { pre->rchild = p; pre->rtag = 1; } pre = p; } void createPreThread(threadTree T){ pre = NULL; if (T){ preThread(T); if (pre->rchild == NULL) pre->rtag = 1; } }
4.4.后序线索化
typedef struct threadNode{ struct threadNode *lchild, *rchild; elemType data; int ltag, rtag; }threadNode, *threadTree; threadNode *pre = NULL; void postThread(threadTree T){ postThread(T->lchild); postThread(T->rchild); visit(T); } void visit(threadNode *p){ if (p->lchild == NULL){ p->lchild = pre; p->ltag = 1; } if (pre && pre->rchild == NULL){ pre->rchild = p; pre->rtag = 1; } pre = p; } void createPostThread(threadTree T){ pre = NULL; if (T) { postThread(T); if (pre->rchild == NULL) pre->rtag = 1; } }
4.5.找前驱/后继
4.5.1.中序线索树找后继
- p->rtag = 1，next = p->rchild
- p->rtag = 0，next = 右子树的最左节点
//找到中序遍历的第一个节点 threadNode *firstNode(threadNode *p){ //找到最左下的结点，并非一定是叶子结点 //有可能是左空右不空 while(p->ltag == 0) p = p->lchild; return p; } //找当前节点的后继结点 threadNode *nextNode(threadNode *p){ //rtag = 0说明有右子树，继续寻找右子树中的最左节点 if (p->rtag == 0) return firstNode(p->rchild); //rtag = 1说明右子树为指向的是后继结点 else return p->rchild; } //中序遍历 void InOrder(ThreadNode *T){ for (threadNode *p = firstNode(T); p != NULL; p = nextNode(p)) visit(p); }
4.5.2.中序线索树找前驱
- p->ltag = 1，pre = p->lchild
- p->ltag = 0，pre = 左子树的最右结点
//找到最后一个结点 ThreadNode *LastNode(ThreadNode *p){ while(p->rtag == 0) p = p->rchild; return p; } //找前驱结点 ThreadNode *PreNode(ThreadNode *p){ if (p->rtag == 0) return LastNode(p->lchild); else return p->rchild; } //中序遍历 void InOrder(ThreadTree T){ for (ThreadNode *p = LastNode(T); p != NULL; p = preNode(p)) visit(p); }
4.5.3.先序搜索树找后继
- p->ltag = 1，next = p->rchild
- p->ltag = 0
- 左子树不空，next = 左孩子
- 左子树空，右子树不空，next = 右孩子
4.5.4.先序搜索树找前驱
- p->ltag = 1，pre = p->lchild
- p->ltag = 0
- 如果没有parent指针，则无法找到前驱
- 有parent指针：
1.p是左孩子：pre = p->parent
2.p是右孩子，但左兄弟为空：pre = p->parent
3.p是右孩子，且有左兄弟：pre = 左兄弟子树的最后一个遍历的结点
4.p是根节点：pre = NULL
4.5.5.后序搜索树找后继
- p->rtag = 1，next = p->rchild
- p->rtag = 0
- 如果没有parent指针，则无法找到后继
- 有parent指针：
1.p是右孩子：next = p->parent
2.p是左孩子，且没有右兄弟：next = p->parent
3.p是左孩子，且有右兄弟：next = 右兄弟子树中第一个被后序遍历的结点
4.p是根节点，p没有后继
4.5.6.后序搜索树找前驱
- p->ltag = 1，pre = p->lchild
- p->ltag = 0，p必有左子树
- p有右子树，pre = p->rchild
- p没有右子树，pre = p->lchild
