C语言编程二叉树

实验内容 实验内容 1 编写函数 输入字符序列 建立 二叉树的 二叉链表 2 编写函数 实现二叉树的中序递归遍历算法 最好也能实现前缀和后缀遍 历算法 3 编写函数 实现二叉树的中序非递归遍历算法 4 编写函数 借助队列实现二叉树的层次遍历算法 5 编写函数 求二叉树的高度 6 编写函数 求二叉树的结点个数 7 编写函数 求二叉树的叶子个数 8 编写函数 交换二叉树每个结点的左子树和右子树 9 编写一个主函数 在主函数中设计一个简单的菜单 分别调试上述算法 实验目的及要求 实验目的及要求 1 掌握二叉树的存储实现 2 掌握二 叉树的遍历思想 3 掌握二叉树的 常见算法的程序实现 实验内容 方法与步骤 使用附页填写并附在本页后 实验内容 方法与步骤 使用附页填写并附在本页后 实验结果 实验结果 小结 小结 通过这次实验 我体会到深刻理解数据结构的重要性 只有真正理解定义数据类 型的好处才能用好这样一种数据结构 在一开始定义数据结构时 不够细心 总有问题出现 如数据域与指针域的定义 类型的不同 在输好了结构体之后 我开始一个个编写本实验要求实现功能的子函数 以前总觉得使用递归算法是非常难的事情 很复杂很乱 经常会理解不了而导致 编程出错 但这次的实验中二叉树的中序 先序 后序遍历都使用了递归算法 而且 用起来并不复杂 这使我更进一步地学习和理解了函数的递归调用并得到灵活的运用 还有 再次发现自己对指针的认识还很肤浅 也常常使所设计的程序无法实现需 求功能 所以最后我选择了栈的链式存储结构来实现 通过本实验调试过程中出现的一些问题 我对二叉树的结构有了较为深入的理解 相信以后在更多的尝试之中 自己会不断进步 include include define MAXSIZE 100 typedef char DataType typedef struct BiTNode 二叉链表存储结构二叉链表存储结构 DataType data struct BiTNode lchild rchild BiTree typedef BiTree ElemType 栈中数据元素类型 栈中保存结点指针栈中数据元素类型 栈中保存结点指针 typedef struct ElemType data MAXSIZE int top SeqStack 栈的类型定义 顺序栈栈的类型定义 顺序栈 typedef struct ElemType queue MAXSIZE int front rear SP SeqStack initSeqStack 初始化栈初始化栈 SeqStack s 首先建立栈空间 然后初始化栈顶指针首先建立栈空间 然后初始化栈顶指针 s SeqStack malloc sizeof SeqStack s top 1 return s int push SeqStack s ElemType x if s top MAXSIZE 1 栈满不能入栈栈满不能入栈 printf 栈满栈满 return 0 s top s data s top x return 1 void pop SeqStack s 出栈 假设栈不空出栈 假设栈不空 s top int empty SeqStack s if s top 1 return 1 else return 0 ElemType top SeqStack s 设栈不空设栈不空 return s data s top 递归算法创建二叉链表递归算法创建二叉链表 BiTree createBiTree DataType ch BiTree T ch getchar if ch 0 return NULL else T BiTree malloc sizeof BiTree T data ch T lchild createBiTree T rchild createBiTree return T 中序遍历二叉树的递归算法中序遍历二叉树的递归算法 void InOrder BiTree T if T InOrder T lchild printf c T data InOrder T rchild 前序遍历二叉树的递归算法前序遍历二叉树的递归算法 void PreOrder BiTree T if T printf c T data PreOrder T lchild PreOrder T rchild 后序遍历二叉树的递归算法后序遍历二叉树的递归算法 void PostOrder BiTree T if T PostOrder T lchild PostOrder T rchild printf c T data 中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法 void InOrderFei BiTree p SeqStack s s initSeqStack while 1 while p push s p p p lchild 先将结点指针压栈 待出栈时再访问先将结点指针压栈 待出栈时再访问 if empty s break p top s pop s printf c p data p p rchild 按层次遍历按层次遍历 void LevelOrder BiTree T SP p p SP malloc sizeof SP p front 0 p rear 0 if T NULL p queue p front T p front p front 1 while p front p rear T p queue p rear p rear p rear 1 printf c T data if T lchild NULL p queue p front T lchild 左孩子进队列左孩子进队列 p front p front 1 if T rchild NULL p queue p front T rchild 右孩子进队列右孩子进队列 p front p front 1 求二叉树的高度求二叉树的高度 int height BiTree T int i j if T return 0 i height T lchild 求左子树的高度求左子树的高度 j height T rchild 求右子树的高度求右子树的高度 return i j i 1 j 1 二叉树的高度为左右子树中较高的高度加二叉树的高度为左右子树中较高的高度加 1 求二叉树的所有结点个数求二叉树的所有结点个数 int Nodes BiTree T int n1 n2 if T NULL return 0 else if T lchild NULL else n1 Nodes T lchild n2 Nodes T rchild return n1 n2 1 求二叉树的叶子结点个数求二叉树的叶子结点个数 int leafs BiTree T int num1 num2 if T NULL return 0 else if T lchild NULL num1 leafs T lchild 求左子树中叶子结点数求左子树中叶子结点数 num2 leafs T rchild 求右子树中叶子结点数求右子树中叶子结点数 return num1 num2 交换二叉树的所有左右子树交换二叉树的所有左右子树 void exchange BiTree T BiTree temp NULL if T lchild NULL else temp T lchild T lchild T rchild T rchild temp if T lchild exchange T lchild if T rchild exchange T rchild 交换后二叉树的遍历交换后二叉树的遍历 void Display BiTree T printf t 交换后二叉树按中序遍历输出交换后二叉树按中序遍历输出 InOrder T printf n printf t 交换后二叉树按前序遍历输出交换后二叉树按前序遍历输出 PreOrder T printf n printf t 交换后二叉树按后序遍历输出交换后二叉树按后序遍历输出 PostOrder T printf n void menu printf n printf t t1 递归递归 创建二叉链表创建二叉链表 n printf t t2 递归递归 中序遍历二叉树中序遍历二叉树 n printf t t3 递归递归 前序遍历二叉树前序遍历二叉树 n printf t t4 递归递归 后序遍历二叉树后序遍历二叉树 n printf t t5 非递归非递归 中序遍历二叉树中序遍历二叉树 n printf t t6 层次层次 遍历二叉树遍历二叉树 n printf t t7 二叉树的高度二叉树的高度 n printf t t8 二叉树的结点个数二叉树的结点个数 n printf t t9 二叉树的叶子结点个数二叉树的叶子结点个数 n printf t t10 交换二叉树的所有左右子树交换二叉树的所有左右子树 n printf t t0 退出系统退出系统 n printf n t 请选择请选择 void main BiTree bt bt NULL int n m 1 while m menu scanf d getchar switch n case 1 printf n t 请输入结点的前序序列创建二叉树请输入结点的前序序列创建二叉树 0 表示空表示空 bt createBiTree break 生成二叉树生成二叉树 case 2 printf n t 递归递归 中序遍历二叉树中序遍历二叉树 InOrder bt printf n break case 3 printf n t 递归递归 前序遍历二叉树前序遍历二叉树 PreOrder bt printf n break case 4 printf n t 递归递归 后序遍历二叉树后序遍历二叉树 PostOrder bt printf n break case 5 printf n t 非递归非递归 中序遍历二叉树中序遍历二叉树 InOrderFei bt printf n break case 6 printf n t 按层次遍历二叉树按层次遍历二叉树 LevelOrder bt printf n break case 7 printf n t 二叉树的高度为二叉树的高度为 d n height bt p