二叉树的遍历和线索二叉树

二叉树的遍历：

先根序遍历：

Status  PreOrderTraverse (BiTree T,  Status (*visit)(TElemType e)){
//递归边界:空树直接返回
//递归关系:非空则归结为访问根、遍历左子树和右子树。左右子树的遍历需要递归
  if(!T) return OK;
  else{ 
     visit(T->data);
     PreOrderTraverse(T->lchild,visit);
     PreOrderTraverse(T->richild,visit);
     return OK;
  }
}
 // 遍历过程： AB^C^^D^EF^^^
 // 遍历序列： ABCDEF

中根序遍历：

Status InOrderTraverse (BiTree T, 
         Status (*visit)(TElemType e) ){
//递归边界:空树直接返回
//递归关系:非空则归结为遍历左子树、根、右子树。左右子树的遍历需要递归
  if(!T) return OK;
  else{ 
     InOrderTraverse (T->lchild,visit);
     visit(T->data);
     InOrderTraverse (T->richild,visit);
     return OK;
  }
}
//中根序遍历过程:^B^C^A^D^F^E^
//中根序遍历序列： BCADFE

后根序遍历：

Status PostOrderTraverse (BiTree T, 
         Status (*visit)(TElemType e) ){
//递归关系:遍历大规模二叉树归结为遍历左子树、右子树、根。左右子树的遍历需要递归
//递归边界:空树直接返回
  if(!T) return OK;
  else{ 
     PostOrderTraverse (T->lchild,visit);
      PostOrderTraverse (T->richild,visit);
     visit(T->data);
     return OK;
  }
}
//后根序遍历过程:^^^CB^^^F^EDA
//后根序遍历序列：CBFEDA

表达式：1 + 2 * (3-4) – 5 / 6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 表达式树：从左向右扫描表达式,找到最后一个优先级最低的运算符，将其放在根节点，左侧子表达式作左子树，右侧子表达式作右子树；直到两个子树均为数字停止递归(括号忽略)? ? ? ? ? ? ? ? ? ? 表达式树的遍历与表达式形式：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 前缀表达式：- + 1 * 2 – 3 4 / 5 6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 中缀表达式： 1 + 2 * 3 – 4 – 5 / 6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 后缀表达式：1 2 3 4 - * + 5 6 / -?

先序序列+中序序列:先序序列中第1个元素X为根,中序序列中唯有遍历完X的左子树后方访问X,故X之前的abc…必构成X的左子树,X之后的def…必构成X的右子树.对于子树类似处理,第1个在先序序列中出现的元素Y为该左子树的根,中序序列中Y左侧的元素构成Y的左子树,右侧构成右子树,依此类推,最终可定? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 中序序列+后序序列:后序序列中最后一个元素为根,中序序列中该结点前的元素为左子树,后的元素为右子树。对于左/右子树,最后一个在后序序列中出现的元素为子树的根结点,再看中序序列,依此类推? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?先序序列+后序序列: 不能确定.如AB和BA

线索二叉树：

typedef enum{ LINK, ?THREAD } PTag;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //LINK 代表指针值是孩子节点地址? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //THREAD代表值是前驱后继节点地址? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //线索二叉树存储结构定义? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? typedef struct BiThrNode {? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?TElemType ? ? ? ?data;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?struct BiThrNode ?*lchild, *rchild;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?PTag ? ? LTag, RTag; // 指针标记位? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? } BiThrNode, *BiThrTree;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 中序线索二叉树的遍历： 找第一个应该遍历的节点,记入p 访问p->data 只要p->RTag为THREAD则令p沿 p-rchild前进，并访问p 若p->RTag为LINK，则令p指向其右子树的根 重复至p指向头结点

void InOrderTraverse_Thr(BiThrTree T, Status (*visit) (TElemType e))? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? {? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? p = T->lchild;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? while (p != T) {? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? while (p->LTag==LINK) p=p->lchild;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if (!visit(p->data)) return ERROR;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? while(p->RTag==THREAD&&p->rchild!=T){? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?p = p->rchild;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?if (!Visit(p->data)) return ERROR;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?p = p->rchild; //非线索时 p指向右子树根? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }//复杂度O(n)，无递归? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?中序线索二叉树的构造： 开辟头结点并赋初值 遍历原二叉树, 根据其有无孩子信息,修改标记,必 时设置线索【该步骤递归完成】 最后一个结点单独处理