二叉树的应用.doc

二叉树的应用.txt14热情是一种巨大的力量，从心灵内部迸发而出，激励我们发挥出无穷的智慧和活力；热情是一根强大的支柱，无论面临怎样的困境，总能催生我们乐观的斗志和顽强的毅力没有热情，生命的天空就没的色彩。#include#include#includeusing namespace std;#define QUEUE_MAX_SIZE 30#ifndef elemTypetypedef char elemType;#endifint count=0;typedef struct BiTNode / 结点结构 char data; struct BiTNode *lchild, *rchild,*parent; / 左右孩子指针 BiTNode, *BiTree;void InitBiTree(BiTNode *t)/初始化，带头结点 t=new BiTNode; t-lchild=t-rchild=t-parent=NULL;int EmptyBiTree(BiTNode *t)/判断队空 if(t=0) return 1; else return 0;void CreateBiTree(BiTree &T) char ch; scanf(%c,&ch); if(ch= )T=NULL; else if(!(T = (BiTNode * )malloc(sizeof(BiTNode) return; T-data=ch; CreateBiTree(T-lchild);CreateBiTree(T-rchild); /CreatBiTreeint PreOrder(BiTree T)/先序遍历二叉树的递归算法if (!T) return 0;printf(%c ,T-data); / 访问结点 PreOrder(T-lchild); / 遍历左子树 PreOrder(T-rchild);/ 遍历右子树return 1; int InOrder(BiTree T)/中序遍历二叉树的递归算法 if (!T) return 0; InOrder(T-lchild); / 遍历左子树 printf(%c ,T-data); / 访问结点 InOrder(T-rchild);/ 遍历右子树 return 1; int PostOrder(BiTree T)/后序遍历二叉树的递归算法 if (!T) return 0; PostOrder(T-lchild); / 遍历左子树 PostOrder(T-rchild);/ 遍历右子树 printf(%c ,T-data); / 访问结点 return 1; int DepthBiTree(BiTNode *t)/求二叉树的深度 int i,j; if(EmptyBiTree(t) return 0; else i=DepthBiTree(t-lchild); j=DepthBiTree(t-rchild); return (ij?i:j)+1; elemType *FindBiTree(BiTNode *bt, elemType x)if(bt = NULL)return NULL;elseif(bt-data = x)return &(bt-data);else /* 分别向左右子树递归查找 */elemType *p;if(p = FindBiTree(bt-lchild, x)return p;if(p = FindBiTree(bt-rchild, x)return p;return NULL;void PrintBiTree(BiTNode *bt)/* 树为空时结束递归，否则执行如下操作 */if(bt != NULL)printf(%c, bt-data); /* 输出根结点的值 */ if(bt-lchild != NULL | bt-rchild != NULL)printf();PrintBiTree(bt-lchild);if(bt-rchild != NULL)printf(,);PrintBiTree(bt-rchild);printf();void LevelOrder(BiTNode *bt)struct BiTNode *p;struct BiTNode *qQUEUE_MAX_SIZE;int front = 0, rear = 0;/* 将树根指针进队 */if(bt != NULL)rear = (rear + 1) % QUEUE_MAX_SIZE;qrear = bt;while(front != rear) /* 队列非空 */front = (front + 1) % QUEUE_MAX_SIZE; /* 使队首指针指向队首元素 */p = qfront;printf(%c , p-data);/* 若结点存在左孩子，则左孩子结点指针进队 */if(p-lchild != NULL)rear = (rear + 1) % QUEUE_MAX_SIZE;qrear = p-lchild;/* 若结点存在右孩子，则右孩子结点指针进队 */if(p-rchild != NULL)rear = (rear + 1) % QUEUE_MAX_SIZE;qrear = p-rchild;void ClearBiTree(BiTNode * &bt)/清空二叉树，使之成为空树if(bt != NULL)ClearBiTree(bt-lchild);ClearBiTree(bt-rchild);free(bt);bt = NULL;void main()cout输入完要连续输入空格才可以出结果endl;BiTNode *BT=NULL;int d;char x;cout1、初始化.endl;InitBiTree(BT);cout2、创建二叉树:;CreateBiTree(BT);cout3、判断是否为空：;EmptyBiTree(BT);if(BT=0)cout树为空endl;elsecout树不为空endl;cout4、输出二叉树:;PrintBiTree(BT);coutendl;cout5、先序遍历:endl;PreOrder(BT);coutendl;cout6、中序遍历:endl;InOrder(BT);coutendl;cout7、后序遍历:endl;PostOrder(BT);coutendl;cout8、层次遍历:endl;LevelOrder(BT);coutendl;d=0;cout9、计算深度.end