【数据结构入门实验】二叉树的建立和遍历完整代码

2024-06-27 00:24| 来源: 网络整理| 查看: 265

实验内容： 1 ．二叉树的建立与遍历（验证性实验）问题描述建立一棵二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。基本要求从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序和后序），将遍历结果打印输出。测试数据 ABC □□ DE □ G □□ F □□□ （其中 □ 表示空格字符），则输出结果为：先序为 ABCDEGF ，中序为 CBEGDFA ， z 后序为 CGBFDBA 。实验分析：

实验要求采用的是先序建立二叉树，在此可以使用一个递归的方式去建立，但是由于指针传递的问题，在此使用二级指针，原因的话可以见我写的另一篇文章：

（极易错）链表指针函数传递问题，含线性表入门实验--约瑟夫环问题c语言代码

三个遍历函数也使用递归，比较简单就不多说了，如果是0基础的话可以简单了解一下三种遍历的大致描述：

先序：规则是若二叉树若为空,则空操作返回,否则先访问根结点,然后遍历左子树,然后再遍历右子树

中序：若树为空,则空操作返回,否则从根结点开始,中序遍历根结点的左子树,然后就是访问根结点,最后中序遍历右子树

后序：若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后是访问根结点

代码： #include #include #include typedef struct BiTree { char data; struct BiTree *lchild; struct BiTree *rchild; }BiTree,*BiTreePtr; bool CreatBiTree(BiTreePtr *T) { char ch; scanf("%c",&ch); if(ch==' ') (*T)=NULL; else { if(!((*T)=(BiTreePtr)malloc(sizeof(BiTree)))) exit(1); (*T)->data=ch; CreatBiTree(&((*T)->lchild)); CreatBiTree(&((*T)->rchild)); } return true; } bool PreOrderTraverse(BiTreePtr T) { if(T) { printf("%c ",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } else return true; return true; } bool InOrderTraverse(BiTreePtr T) { if(T) { InOrderTraverse(T->lchild); printf("%c ",T->data); InOrderTraverse(T->rchild); } else return true; return true; } bool PostOrderTraverse(BiTreePtr T) { if(T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c ",T->data); } else return true; return true; } int main() { BiTreePtr T; printf("输入先序创建二叉树序列："); CreatBiTree(&T); printf("先序遍历序列为："); PreOrderTraverse(T); printf("\n"); printf("中序遍历序列为："); InOrderTraverse(T); printf("\n"); printf("后序遍历序列为："); PostOrderTraverse(T); printf("\n"); return 0; } 效果

【本文地址】

公司简介

联系我们