树与二叉树的转换（数据结构与算法-课程设计）.zip

河南工程学院《数据结构与算法》课程设计
成果报告
树与二叉树的转换
题 目
树与二叉树的转换
考核项目
考核内容
得分
平时考核
（30分）出勤情child; //孩子链表头指针
}CTBox;
typedef struct{
CTbox nodes[MAX_TREE_SIZE];
int n,r; //结点数和根的位置
}CTree;

按照顺序存储结构的定义，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，二叉树的顺序存储表示说明如下：
#define MAX_TREE_SIZE 100 //二叉树的最大结点数
typedef TElemType SqBiTree[MAX_TREE_SIZE]; //0号单元存储根结点
SqBiTree bt;

设计不同的结点结构可构成不同形式的链式存储结构。二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成，二叉链表的定义和部分基本操作的函数说明如下：
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild; //右孩子指针
}BiTNode,*BiTree;
//-----基本操作的函数原型说明-----
Status CreateBiTree(BiTree &T);
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示二叉树T。
Status PreOrderTraverse(BiTre T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构，Visit是对结点操作的应用函数。
//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
//一旦Visit（）失败，则操作失败。
Status InOrderTraverse(BiTre T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构，Visit是对结点操作的应用函数。
//中序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
//一旦Visit（）失败，则操作失败。
Status PostOrderTraverse(BiTre T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构，Visit是对结点操作的应用函数。
//后序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
//一旦Visit（）失败，则操作失败。
Status LevelOrderTraverse(BiTre T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构，Visit是对结点操作的应用函数。
//层序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
//一旦Visit（）失败，则操作失败。
算法描述
分别设计二叉树的递归算法、非递归算法层序遍历算法来实现树与二叉树转换的算法。

前序遍历二叉树的递归算法，若二叉树为空，则算法结束，否则（1）访问根结点，（2）前序遍历左子树，（3）前序遍历右子树。
void preorder(BTNode * T)

后序遍历二叉树的递归算法，若二叉树非空，则空操作；否则(1)遍历左子树；(2)遍历右子树；(3)访问根结点。
void inorder(BTNode * T)

前序非递归算法，BTNode根指针，若BTNode!=NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。
void preorder2(PTree T)

后序非递归算法，BTNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
void inorder2(PTree T)

层次序遍历算法，按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。
void level(PTree T)

树与二叉树的转换算法，转换时结点的第一个孩子变为他的左孩子，兄弟结