二叉树的建立和遍历

1、建立和遍历二叉树#include "stdafx.h"#include "stdio.h"#include "malloc.h"#include "string.h"#include "stdlib.h"#define Max 20 /结点的最大个数typedef struct BinTNode char data;struct BinTNode *lchild,*rchild;BinTNode,*BinTree; /自定义二叉树的结点类型/定义二叉树的指针int NodeNum,leaf; /

2、NodeNum为结点数, leaf 为叶子数/=以广义表显示二叉树 =void DisTree(BinTree T if(Tprintf("%c",T->data;if(T->lchild|(T->rchildif(T->lchildprintf("%c",'('DisTree(T->lchild;if(T->rchildprintf("%c",','DisTree(T->rchild;printf("%c",''/=基于先序

3、遍历算法创建二叉树 =/=要 求 输 入 先 序 序 列 , 其 中 加 入 虚 结 点 "#"以 示 空 指 针 的 位 置 =BinTree CreatBinTree(BinTree Tchar ch;scanf("%c",&ch;if(ch='#'T=NULL;elseif(!(T=(BinTNode *malloc(sizeof(BinTNode printf("Error!"T->data=ch;T->lchild=CreatBinTree(T->lchild;T->rchil

4、d=CreatBinTree(T->rchild;return T;/=NLR 先序遍历 = void Preorder(BinTree Tif(Tprintf("%c",T->data;Preorder(T->lchild;Preorder(T->rchild;/=LNR 中序遍历 = void Inorder(BinTree Tif(TInorder(T->lchild;printf("%c",T->data;Inorder(T->rchild;/=LRN 后序遍历 = void Postorder(BinT

5、ree Tif(TPostorder(T->lchild;Postorder(T->rchild;printf("%c",T->data;/=采 用后序遍 历求二叉 树的深度 、结点数及叶 子数的递 归算法 =int TreeDepth(BinTree Tint hl,hr,max;if(Thl=TreeDepth(T->lchild; /求左深度hr=TreeDepth(T->rchild; /求右深度max=hl>hr? hl:hr; /取左右深度的最大值NodeNum=NodeNum+1; /求结点数if(hl=0&&

6、;hr=0leaf=leaf+1; /若左右深度为 0,即为叶子。return(max+1;else return(0;/=利用 " 先进先出 " (FIFO 队列,按层次遍历二叉树 = void Levelorder(BinTree Tint front=0,rear=1;BinTNode *cqMax,*p; /定义结点的指针数组 cqcq1=T; /根入队while(front!=rearfront=(front+1%NodeNum;p=cqfront; /出队printf("%c",p->data; /出队,输出结点的值if(p->l

7、child!=NULLrear=(rear+1%NodeNum;cqrear=p->lchild; /左子树入队if(p->rchild!=NULLrear=(rear+1%NodeNum;cqrear=p->rchild; /右子树入队/=主函数 =void main(BinTree T,root;int i,depth;printf("n"printf("输入完全二叉树的先序序列 :" /输入完全二叉树的先序序列, / 用 #代表虚结点,如 ABD#CE#F# root=CreatBinTree(T; /创建二叉树,返回根结点Dis

8、Tree(root;printf("n"do /从菜单中选择遍历方式,输入序号。printf("t* 菜单 *n"printf("n"printf("t1: 先序遍历 n"printf("t2: 中序遍历 n"printf("t3: 后序遍历 n"printf("t4: 该树的深度 , 结点数 , 叶子数 n"printf("t5: 层次遍历 n" /按层次遍历之前,先选择 4,求出该树的结 点数。printf("t0: 退出

9、 n"printf("t*n"scanf("%d",&i;/输入菜单序号(0-5switch(icase 1: printf("Print Bin_tree Preorder: "Preorder(root; /先序遍历break;case 2: printf("Print Bin_Tree Inorder: "Inorder(root; /中序遍历break;case 3: printf("Print Bin_Tree Postorder: "Postorder(root; /后序遍历break;case 4: depth=TreeDepth(root; /求树的深度及叶子数 printf("树深 =%d 树总结点数 =%d",depth,NodeNum; printf("