数据结构-考研笔记（二）：二叉树的应用

// 计算二叉树所有结点数 int n = 0; void count(BTNode *p){ if(p!=NULL){ ++n; count(p->lchild); count(p->rchild); } } // 计算叶结点数 int n = 0; void count_0(BTNode *p){ if(p!=NULL){ if(p->lchild=NULL&&p->rchild=NULL) ++n; count_0(p->lchild); count_0(p->rchild); } } // // 利用右孩子指针连接叶结点 // 采用先序遍历模板 void link(NTNode *p, BTNode *&head, BTNode *&tail){ if(p!=NULL){ if(p->lchild!=NULL&&p->rchild!=NULL){ if(head==NULL){ // 如果head=NULL,则当前结点为第一个 head=p; tail=p; } else{ tail->rchild=p; tail=p; } } link(p->lchild,head,tail); link(p->rchild,head,tail); } } // 输出结点到根结点的路径 // 增加一个指向双亲的指针parent // 定义新的数据结构 typedef struct BTNode{ char data; BTNode *lchild; BTNode *rchild; BTNode *parent; } // 给parent赋值 void triBtree(BTNode *p, BTNode *q){ //q指向双亲 if(p!=NULL){ p->parent = q; q = p; // p是其子树的双亲 triBtree(lchild,q); triBtree(rchild,q); } } // 打印路径 void printPath(BTNode *p){ while(*p!=NULL){ cout<<p->data<<'\n'; printPath(p-parent); } } // 打印所有结点的路径, 先序遍历 void allPath(BTNode *p){ if(p!=NULL){ printPath(p); allPath(p->lchild); allPath(p->rchild); } } /// change(pre, L1+1, (L1+1+R1)/2, post, L2,(L2+R2-1)/2); // 已知满二叉树的先序序列， 求后序序列 // 已知pre数组，即先序序列 void change(char pre[], int L1, int R1, char post[], int L2, int R2){ if(L1<=R1){ post[R2] = pre[L1]; change(pre, L1+1, (L1+1+R1)/2, post, L2,(L2+R2-1)/2); change(pre, L1+1, (L1+1+R1)/2, post, L2,(L2+R2-1)/2); change(pre, L1+1, (L1+1+R1)/2, post, L2,(L2+R2-1)/2); } } / // 找出值为b的结点和层数 // 运用重要提示模板 int L=1; void leno(BTNode *p){ if(p!=0){ if(p->data==b) cout<<L<<endl; ++L; leno(p->lchild); leno(p->rchild); --L; } } // // 在中序线索二叉树中，寻找结点t为根的子树上的最后一个结点 // 思路: 沿右子树一直走下去，直到右指针为右线索 TBTNode* inLast(TBTNode *t){ TBTNode *p = t; while(p && !p->rtag){ p = p->rchild; } return p; } // 找中序前驱 TBTNode* inPrior(TBTNode *t){ TBTNode *p=t->lchild; if(p && !t->ltag){ // 如果p不为空，且ltag==0 p=inLast(p); } retunr p; } // 找前序后继（注意，仍然是中序线索二叉树） // 思路列举所有情况 TBTNode* treNext(TBTNode *t){ TBTNode *p; if(!t->ltag) p = t-lchild; else if(!tag->rtag) p = t-rchild; else{ p = t; while(p && p-rtag) // 如果p不为空，且rtag==1 p=p->rchild; if(p) p=p->rchild; } return p; }