一、二叉树的节点结构体定义
typedef struct BiTNode //定义二叉树的存储结构 { char data;struct BiTNode* lchild, * rchild;}BiTNode, * BiTree;
二、二叉树的先序遍历创建
BiTree CreateTree(BiTree& T) //先序遍历创建二叉树，递归实现{char c;c = getchar();if (c == '#'){T = NULL;}else{T = (BiTNode*)malloc(sizeof(BiTNode)); //为节点T分配内存空间T->data = c;CreateTree(T->lchild);CreateTree(T->rchild);}return T;}
三、二叉树的前序遍历功能实现
void FirstOrderTraverse(BiTree T) //先序遍历二叉树，递归实现{if (T == NULL){return;}printf("%c",T->data);FirstOrderTraverse(T->lchild);FirstOrderTraverse(T->rchild);}
四、二叉树的中序遍历功能实现
void MidOrderTraverse(BiTree T) //中序遍历二叉树，递归实现{if (T == NULL){return;}MidOrderTraverse(T->lchild);printf("%c", T->data);MidOrderTraverse(T->rchild);}
五、二叉树的后序遍历功能实现
void LastOrderTraverse(BiTree T) //后序遍历二叉树，递归实现{if (T == NULL){return;}LastOrderTraverse(T->lchild);LastOrderTraverse(T->rchild);printf("%c", T->data);}
六、返回二叉树的深度函数实现
int max(int a, int b){if (a > b)return a;elsereturn b;}int GetTreeDepth(BiTree T) //得到树的深度{if (T == NULL)return 0;elsereturn 1 + max(GetTreeDepth(T->lchild), GetTreeDepth(T->rchild));}
七、完整代码
#include<stdio.h>#include<stdlib.h>#pragma warning(disable : 4996)typedef struct BiTNode //定义二叉树的存储结构 { char data;struct BiTNode* lchild, * rchild;}BiTNode, * BiTree;BiTree CreateTree(BiTree& T) //先序遍历创建二叉树，递归实现{char c;c = getchar();if (c == '#'){T = NULL;}else{T = (BiTNode*)malloc(sizeof(BiTNode)); //为节点T分配内存空间T->data = c;CreateTree(T->lchild);CreateTree(T->rchild);}return T;}void FirstOrderTraverse(BiTree T) //先序遍历二叉树，递归实现{if (T == NULL){return;}printf("%c",T->data);FirstOrderTraverse(T->lchild);FirstOrderTraverse(T->rchild);}void MidOrderTraverse(BiTree T) //中序遍历二叉树，递归实现{if (T == NULL){return;}MidOrderTraverse(T->lchild);printf("%c", T->data);MidOrderTraverse(T->rchild);}void LastOrderTraverse(BiTree T) //后序遍历二叉树，递归实现{if (T == NULL){return;}LastOrderTraverse(T->lchild);LastOrderTraverse(T->rchild);printf("%c", T->data);}int max(int a, int b){if (a > b)return a;elsereturn b;}int GetTreeDepth(BiTree T) //得到树的深度{if (T == NULL)return 0;elsereturn 1 + max(GetTreeDepth(T->lchild), GetTreeDepth(T->rchild));}int main(){BiTree TA;CreateTree(TA);printf("The FirstOrderTraverse is:\n");FirstOrderTraverse(TA);printf("\n");printf("The MidOrderTraverse is:\n");MidOrderTraverse(TA);printf("\n");printf("The LastOrderTraverse is:\n");LastOrderTraverse(TA);printf("\n");printf("The depth is:\n");printf("%d", GetTreeDepth(TA));return 0;}
八、运行结果
九、总结
二叉树难点在于理解遍历过程中递归的应用，其次是结构体指针的用法。
