先序建立二叉树的递归算法 说明: Status Create BiTree(BiTree &T) 1)遍历的第一个和最后一个结点 i char ch; scanf("%c", &ch); 第一个结点: if(ch==)T=NULL 先序:根结点; else if((T=(BiTNode*)malloc(sizeof( BiTNode)) 中序:沿着左链走,找到一 exit(OVERFLOW); 个没有左孩子的结点; 后序:从根结点出发,沿着 Create BiTree(T->lchild); 左链走,找到一个既没有左 Create BiTree(T->rchild); 孩子又没有右孩子的结点。 最后一个结点: return OK: 中序:从根结点出发,沿着 右链走,找到一个没有右孩 二叉树的显示输出 子的结点 void Print BiTree( BiTree T, int n) 后序:根结点。 先序:从根结点出发,沿着 nti; char ch=’ 右链走,找到一个没有右孩 if()i 子的结点;如果该结点有左 Print BiTree(T->rchild, n+1) 孩子,再沿着其左孩子的右 for(i=l; i<=n; ++i)(printf("%5c" ch); 链走,以此类推,直到找到 printf("%cIn", T->data) 个没有孩子的结点 Print BiTree(T->Child, n+1); 求中序的第一个结点的算法 遍历二叉树的应用 printf(P->data) 利用二叉树后序历计算二叉树的深度 求中序的最后一个结点的算法 int Depth( BiTree T) int depl, depr while(P->rchild)P=P->rchild if(D) Printf(P->data) depl=Depth(T->lchild) depr=Depth(T->rchild 复制二叉树 if(depl>=depr)return(depl+l) void Copy Tree(BiTree T, BiTree &Tl) else return(depr+1) f if (T) return o fT1=(BiTree)malloc(sizeof(Bi TNode)); if (T1)i printf("Overflown"); it(1);} 求二叉树结点个数 TI->data=T->data: int Size( Bi Tree T) T1->lchild=T1->rchild=NULI Copy Tree(T-lchild, T1->lchild); if(T-NULL) return 0 Copy Tree(T->rchild,Tl->rchild); else return 1 Size(T->lchild)+ Size( T->rchild);先序建立二叉树的递归算法 Status CreateBiTree(BiTree &T) { char ch;scanf("%c",&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; } 二叉树的显示输出 void PrintBiTree(BiTree T,int n) { int i; char ch=' '; if (T) { PrintBiTree(T->rchild,n+1); for (i=1;i<=n;++i) {printf("%5c",ch);} printf("%c\n", T->data); PrintBiTree(T->lchild,n+1); } } 遍历二叉树的应用 利用二叉树后序遍历计算二叉树的深度 int Depth(BiTree T){ int depl,depr; if (T){ depl=Depth(T->lchild); depr=Depth(T->rchild); if (depl>=depr) return (depl+1); else return (depr+1); } return 0; } 求二叉树结点个数 int Size(BiTree T) { if (T==NULL) return 0; else return 1 + Size (T->lchild ) + Size ( T->rchild); } 说明： 1）遍历的第一个和最后一个结点 第一个结点： ▪ 先序：根结点； ▪ 中序：沿着左链走，找到一 个没有左孩子的结点； ▪ 后序：从根结点出发，沿着 左链走，找到一个既没有左 孩子又没有右孩子的结点。 最后一个结点： ▪ 中序：从根结点出发，沿着 右链走，找到一个没有右孩 子的结点； ▪ 后序：根结点。 先序：从根结点出发，沿着 右链走，找到一个没有右孩 子的结点；如果该结点有左 孩子，再沿着其左孩子的右 链走，以此类推，直到找到 一个没有孩子的结点 求中序的第一个结点的算法： P=T; while (P->lchild) P=P->lchild; printf(P->data); 求中序的最后一个结点的算法： P=T； while(P->rchild) P=P->rchild; Printf(P->data); 复制二叉树 void CopyTree(BiTree T,BiTree &T1) { if (T) { T1=(BiTree)malloc(sizeof(BiTNode)); if (!T1) { printf("Overflow\n"); exit(1); } T1->data=T->data; T1->lchild=T1->rchild=NULL; CopyTree(T->lchild,T1->lchild); CopyTree(T->rchild,T1->rchild); } }