UC知道二叉树的基本运算
来源：百度知道 编辑：UC知道 时间：2024/05/30 21:25:41
1. 按先序序列构造一棵二叉链表表示的二叉树T；
2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；
3. 求二叉树的深度/结点数目/叶结点数目；(选做)
4. 将二叉树每个结点的左右子树交换位置。（选做）
[基本要求]
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），
[测试数据]
如输入：ABCффDEфGффFффф（其中ф表示空格字符）
则输出结果为
先序：ABCDEGF
中序：CBEGDFA
后序：CGEFDBA
层序：ABCDEFG
2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；
3. 求二叉树的深度/结点数目/叶结点数目；(选做)
4. 将二叉树每个结点的左右子树交换位置。（选做）
[基本要求]
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），
[测试数据]
如输入：ABCффDEфGффFффф（其中ф表示空格字符）
则输出结果为
先序：ABCDEGF
中序：CBEGDFA
后序：CGEFDBA
层序：ABCDEFG
楼主自己看哈，有点长
/*文件名:exp7-2.cpp*/
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data; /*数据元素*/
struct node *lchild; /*指向左孩子*/
struct node *rchild; /*指向右孩子*/
} BTNode;
extern void CreateBTNode(BTNode *&b,char *str);
extern void DispBTNode(BTNode *b);
void PreOrder(BTNode *b) /*先序遍历的递归算法*/
{
if (b!=NULL)
{
printf("%c ",b->data); /*访问根结点*/
PreOrder(b->lchild); /*递归访问左子树*/
PreOrder(b->rchild); /*递归访问右子树*/
}
}
void PreOrder1(BTNode *b)
{
BTNode *p;
struct
{
BTNode *pt;
int tag;
} St[MaxSize];
int top=-1;
top++;
St[top].pt=b;St[top].tag=1;
while (top>-1) /*栈不空时循环*/
{
if (St[top].tag==1) /*不能直接访问的情况*/
{
p=St[top].pt;
top--;
if (p!=NULL)