Status Preorder (BiTree T, ElemType x, BiTree &p) {
// 若二叉树中存在和 x 相同的元素，则 p 指向该结点并 //返回 OK,// 否则返回 FALSE if (T) {
if (T->data= =x) { p = T; return OK,} else {
if (Preorder(T->lchild, x, p)） return OK; else (Preorder(T->rchild, x, p)) return OK; }//else }//if
else return FALSE; }
（2）计算二叉树中叶子结点的个数
int CountLeaf (BiTree T){
//返回指针T所指二叉树中所有叶子结点个数 if (!T ) return 0;
if (!T->lchild && !T->rchild) return 1; else{
m = CountLeaf( T->lchild); n = CountLeaf( T->rchild); return (m+n);
} //else } // CountLeaf
（3）求二叉树的深度(后序遍历)
int Depth (BiTree T ){ // 返回二叉树的深度 if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild );
depthval = 1 + (depthLeft > depthRight ?
depthLeft : depthRight); }
return depthval; }
（4）按先序遍历序列建立二叉树
Status CreateBiTree (BiTree &T ){ //按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树T scanf (&ch);
if ( ch==‘ ‘ ) T=NULL; else {
if(!T=(BiTNode *)malloc(sizeof(BiTNode)))) exit (OVERFLOW); T->data=ch; //生成根结点
CreateBiTree(T->lchild);//构造左子树 CreateBiTree(T->rchild);//构造右子树} Return OK; }//CreateBiTree 9、遍历二叉树的非递归算法
（1）先序遍历二叉树的非递归算法
void inorder(JD *r)//先序遍历二叉树非递归算法// { int i=0; JD *p,*s[M]; p=r; do {
while(p!=NULL) {
printf(\ if (p->rc!=NULL) s[i++]=p->rc; p=p->lc; }
if ( i > 0) p=s[--i]; }while( i>0 || p!=NULL); } （2）中序遍历二叉树的非递归算法
void inorder(JD *r)//先序遍历二叉树非递归算法// { int i=0; JD *p,*s[M]; p=r; do {
while(p!=NULL) { {s[i++]=p; p=p->lc;} if (i>0) {p=s[--i]; printf(\ p=p->lc;
}
if ( i > 0) p=s[--i]; }while( i>0 || p!=NULL); } （3）后序遍历二叉树的非递归算法
void inorder(JD *r)//先序遍历二叉树非递归算法// { int s2[M],b,i=0; JD *p,*s1[M]; p=r; do {
while(p!=NULL) {
{s1[i-1]=p;s2[i++]=0;p=p->lc;} while (i>0 && (s2[i-1]=1)) {p=s1[--i]; printf(“%d\\t”,p->data ); } if (i>0) {p=s[--i]; printf(\ p=p->lc; } if ( i > 0)
{ s2[i-1]=1; p=s1[i-1]; p=p->rc; } }while( i>0); }
12、 线索二叉树：以二叉链表作为存储结构时，只能找到结点的左
右孩子的信息，而不能在结点的任一序列的前驱与后继信息，这种信息只有在遍历的动态过程中才能得到，为了能保存所需
的信息，可增加标志域;
lchild Ltag data Rtag rchild Ltag=0 ，lchild 域指示结点的左孩子；Ltag=1， lchild 域指示结点的前驱。
Rtag=0，rchild 域指示结点的右孩子；Rtag=1，rchild 域指示结点的后驱。
以这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱与后继的指针叫做线索，加上线索的二叉树称之为线索二叉树。 （1）先序线索二叉树 （2）中序线索二叉树 （3）后序线索二叉树 13、 树的存储结构 1双亲表示法 ○
#define MAX_TREE_SIZE 100 typedef struct PTNode {//结点结构 ElemType data;
int parent; // 双亲位置域 } PTNode;
typedef struct {//树结构
PTNode nodes[MAX_TREE_SIZE];
int r, n; // 根结点的位置和结点个数
数据结构 清华大学出版社 严蔚敏吴伟民编著
