二叉树的建立与基本操作.

1、15.二叉树的建立与基本操作题目要求：编写程序实爲二叉树的如下操作：1）建立二叉链義2）二叉树的先序.中序、后序遍历3）求解二叉树的叶子结点个数4）将二叉树中所有结点的圭、右子树相互交换 输入：扩展二叉树先序序列：ab#d#ce#。其中#代表空指针。 输出：二叉树的凹入表示二叉树的先序序列、中序序列.后序序列走、右學树相宜妥换后的二叉树的凹入表示宀，左.右子树相互交换后的二叉树的先序序列、中序序列、后序 序列。说明：右子裔输鲜爵蚕叟論黔不裁出根结点然后依次输出左测试用例ab#d#ce#BiTree addm定义二叉树：typedef struct TreeNode cpre_sequence

2、: abdcein.sequence : bdaecQpostsequence : dbecaNumber of leaf: 22 BiTreeswappedchar data;struct TreeNode *left/*right; 左 右孩子指针 TreeNode;2bepre.sequence : acebd insequence :ceadb post_sequence : ecdba1.(重点)第一步：建立二叉链表TreeNode *p;p=CreateTree();TreeNode *CreateTree() TreeNode *pc; char ch; scanf(%c；&am

3、p;ch); if( ch=,#1) return NULL;else pc=(TreeNode*)malloc(sizeof(TreeNode);pc-data=ch;建立(根)备点pc-left=CreateTree();递归构造左子树链表pc-right=CreateTree();递归构造右子树链表return pc;2第二步：二叉树的凹入表示 定义全局变量：int kongge=0;printf(BiTeen); AoruPrint(p); void AoruPrint(TreeNode *p) int j；if(p=NULL) kongge=kongge-4; return; els

4、e for( j=0 ; jdata);kongge=kongge+4; AoruPrint(p-left); kongge=kongge+4;AoruPrint(p-right); kongge=kongge-4; return;重算法见代码3.（重点）第三步：先序遍历中序遍历后序遍历void Pre_sequence(TreeNode *p)先序( _if(pNULL) return;else printf(,%cp-data);Pre_sequence(p-lett);Pre_sequence(p-right); return;void ln_sequence(TreeNode *p)中

5、序 _if(p=NULL) return; else ln_sequence(p-left);printf(M%cM/p-data);ln_sequence(p right);return;void Post_sequence(TreeNode *p)后序 _if(p=NULL) return;else Post_sequence(p-left); Post_sequence(p right); printf(%cl,/p-data);return;4.第二步：二叉树子树变序void SwappedTree(TreeNode *p)TreeNode *pc;if(p=NULL) return;else /*只要有一个孩子子树不是空就交换*/if( p-left!=NULL | |p-right!=NULL ) pc=p-left;p-left=p right; p-right=pc;SwappedTree(p-left);SwappedTree(p-right);return;5.(重点)第五步：计算二叉树的叶子结点个 数int Countleave(TreeNode *p)if(!p) return 0;if( p-l