//代码选自明日科技零基础学算法一书
#include <stdio.h> #include <stdlib.h> #define QUEUE_MAXSIZE 50 //队列大小 typedef char DATA; //定义元素类型 typedef struct ChainTree //定义二叉树链式结构 { DATA data; //元素数据 struct ChainTree *left; //左子树节点指针 struct ChainTree *right; //右子树节点指针 }ChainBinTree; ChainBinTree *BinTreeInit(ChainBinTree *node) //初始化二叉树根节点 { if(node!=NULL) // 若二叉树节点不为空 return node; else return NULL; } int BinTreeAddNode(ChainBinTree *bt, ChainBinTree *node, int n) //添加数据到二叉树 //bt为父节点，node为子节点，n=1表示添加左子树，n=2表示添加右子树 { if(NULL==bt) { printf("父节点不存在，先设置父节点\n"); return 0; } switch(n) { case 1: if(bt->left) //添加到左节点 { printf("左子树节点不为空\n"); //左子树不为空 return 0; } else { bt->left = node; } break; case 2: if(bt->right) //添加到右节点 { printf("右子树节点不为空\n"); //右子树不为空 return 0; } else { bt->right =node; } break; default: return 0; } return 1; } ChainBinTree *BinTreeLeft(ChainBinTree *bt) //返回左子节点 { if(bt) { return bt->left; } else return NULL; } ChainBinTree *BinTreeRight(ChainBinTree *bt) //return right child node { if(bt) return bt->right; else return NULL; } int BinTreeIsEmpty(ChainBinTree *bt) //获取二叉树状态 { if(bt) return 0; else return 1; } int BinTreeDepth(ChainBinTree *bt) //求二叉树深度 { int dep1,dep2; if(NULL==bt) return 0; //对于空树，深度为0 else { dep1 = BinTreeDepth(bt->left);//左子树深度 dep2 = BinTreeDepth(bt->right);//右子树深度 if(dep1 > dep2) return dep1+1; else return dep2+1; } } ChainBinTree *BinTreeFind(ChainBinTree *bt,DATA data) //在二叉树中查找值为data的节点 { ChainBinTree *p; if(NULL == bt) return NULL; else { if(bt->data == data) return bt; else //分别向左右子树递归查找 { if(p=BinTreeFind(bt->left,data)) return p; else if(p=BinTreeFind(bt->right,data)) return p; else return NULL; } } } void BinTreeClear(ChainBinTree *bt) { if(bt) { BinTreeClear(bt->left); //清空左子树 BinTreeClear(bt->right); //清空右子树 free(bt); //释放当前节点所占内存 bt =NULL; } return; } void BinTree_DLR(ChainBinTree *bt,void(*oper)(ChainBinTree *p)) //先序遍历 { if(bt) //树不为空 { oper(bt); //处理节点的数据 BinTree_DLR(bt->left,oper); BinTree_DLR(bt->right,oper); } return; } void BinTree_LDR(ChainBinTree *bt,void(*oper)(ChainBinTree *p)) //中序遍历 { if(bt) { BinTree_LDR(bt->left,oper); //中序遍历左子树 oper(bt); BinTree_LDR(bt->right,oper); //中序遍历右子树 } return; } void BinTree_LRD(ChainBinTree *bt,void(*oper)(ChainBinTree *p)) //后序遍历 { if(bt) { BinTree_LRD(bt->left,oper); //后序遍历左子树 BinTree_LRD(bt->right,oper); //后序遍历右子树 oper(bt); //处理节点数据 } return; } void BinTree_Level(ChainBinTree *bt,void(*oper)(ChainBinTree *p)) //按层遍历 { ChainBinTree *p; ChainBinTree *q[QUEUE_MAXSIZE]; //定义一个顺序队列 int head =0,tail =0; //队首、队尾序号 if(bt) { tail = (tail+1)%QUEUE_MAXSIZE; // 计算循环队列队尾序号 q[tail] = bt; //将二叉树根指针进队 } while(head!=tail) { head = (head+1)%QUEUE_MAXSIZE; //计算循环队列队首序号 p=q[head]; //获取队首元素 oper(p); //处理队首元素 if(p->left != NULL) //若左节点有左子树，则左子树指针进队 { tail = (tail+1)%QUEUE_MAXSIZE; //计算循环队列的队尾序号 q[tail] = p->left; //将右子树指针进队 } if(p->right != NULL) //若右节点有右子树，则右子树指针进队 { tail = (tail+1)%QUEUE_MAXSIZE; //计算循环队列的队尾序号 q[tail]=p->right; } } return; } /**************************测试二叉树*************************/ void oper(ChainBinTree *p) //操作二叉树节点数据 { printf("%c ",p->data); //输出数据 return; } ChainBinTree *InitRoot() //初始化二叉树的根 { ChainBinTree *node; if(node =(ChainBinTree*)malloc(sizeof(ChainBinTree))) { printf("\n请输入根节点数据："); scanf("%s",&node->data); getchar(); node->left =NULL; //设置左右子树为空 node->right =NULL; return node; //返回根节点 } else return NULL; } void AddNode(ChainBinTree *bt) //add node { ChainBinTree *node,*parent; DATA data; char select; if(node = (ChainBinTree *)malloc(sizeof(ChainBinTree))) //分配内存 { printf("\n输入二叉树节点数据:"); scanf("%s",&node->data); getchar(); node->left = NULL; node->right = NULL; printf("\n输入父节点数据:"); scanf("%s",&data); getchar(); parent=BinTreeFind(bt,data); //查找指定数据的节点 if(!parent) { printf("未找到父节点\n"); free(node); return; } printf("1.添加到左子树\n2.添加到右子树\n"); do { scanf("%c",&select); getchar(); select-='0'; if(select==1 || select==2) BinTreeAddNode(parent,node,select); //添加节点到二叉树 }while(select!=1 && select!=2); } return; } int main() { ChainBinTree *root =NULL; //root为指向二叉树根节点的指针 char select; void (*oper1)(); //指向函数的指针 oper1 = oper; //指向具体操作的函数 do { printf("输入任意键.."); getchar(); printf("\n"); printf("**************************************************\n"); printf("* 1.设置二叉树根元素 2.添加二叉树节点 *\n"); printf("* 3.先序遍历 4.中序遍历 *\n"); printf("* 5.后序遍历 6.按层遍历 *\n"); printf("* 7.二叉树深度 0.退出 *\n"); printf("**************************************************\n"); //fflush(stdin); scanf("%c",&select); getchar(); switch(select) { case '1': root = InitRoot(); break; case '2': AddNode(root); break; case '3': printf("\n先序遍历结果："); BinTree_DLR(root,oper1); printf("\n"); break; case '4': printf("\n中序遍历结果:"); BinTree_LDR(root,oper1); printf("\n"); break; case '5': printf("\n后序遍历的结果:"); BinTree_LRD(root,oper1); printf("\n"); break; case '6': printf("\n按层遍历的结果："); BinTree_Level(root,oper1); printf("\n"); break; case '7': printf("\n二叉树深度为:%d\n",BinTreeDepth(root)); break; case '0': break; } }while(select!='0'); BinTreeClear(root); //清空二叉树 root = NULL; return 0; }
费老大劲将书上代码照抄后运行，设置二叉树数据内容如下，以小写n代表空：
观察程序，发现中序遍历采用的时递归算法，由于个人对递归不是太熟练，于是将递归展开后如下：
由于递归函数从最里层开始执行，展开后，最里层函数位于第四层，由内向外写出结果为：4 2 5 1 6 3 7，与程序执行结果相符合。
采用同样方法展开先序遍历、后续遍历，写出结果即为程序执行结果。
按层遍历稍微有点复杂，要用到其他的方法来分析，暂时不写。