完全二叉树

typedef struct Node {

char data;

struct Node * LChild,*RChild; }BiTNode,*BiTree;

void CreateBiTree(BiTree * bt) {

char ch; ch=getchar();

if(ch==10)ch=getchar();//如果为 回车换行 读取下一个字符 if(ch=='.') *bt=NULL; //如果为 . 代表此节点为空 else {

* bt=(BiTree)malloc(sizeof(BiTNode)); (* bt)->data=ch; //赋值

CreateBiTree(&((* bt)->LChild)); CreateBiTree(&((* bt)->RChild)); } }

bool fullBiTree(BiTree b) {

if(b->LChild==NULL && b->RChild==NULL)return true;//如果左右子树为空，返回真

if(b->LChild==NULL || b->RChild==NULL)return false;//如果左右子树只有一个为空，返回假

return fullBiTree(b->LChild) && fullBiTree(b->RChild);//通过递归，返回 交 }

void main() {

printf(\"此二叉树是对字符进行存储\\n\\n\");

printf(\"请依次输入字符（范例\\n不是完全二叉树ABCO..UMJKL.EDC..........\\n完全二叉树ABC..DE..F..G..)\\n\"); BiTree b;

CreateBiTree(&b); //创建二叉树

bool cm=fullBiTree(b);

if(cm)printf(\"此二叉树为完全二叉树\\n\"); else printf(\"此二叉树不是完全二叉树\\n\"); }

1。

创建 并 中序遍历输出

#include #include

typedef enum{Link,Thread} PointerTag; //指针标志 typedef int DataType;

typedef struct BiThreTree{ //定义结点元素 PointerTag LTag,RTag; DataType data;

struct BiThreTree *lchild,*rchild; }BiThreTree;

BiThreTree *pre; //全局变量，用于二叉树的线索化 BiThreTree *CreateTree() //按前序输入建立二叉树 {

BiThreTree *T; DataType e; scanf(\"%d\ if(e==0) T=NULL; else

{T=(BiThreTree *)malloc(sizeof(BiThreTree)); T->data=e;

T->LTag=Link; //初始化时指针标志均为Link T->RTag=Link; T->lchild=CreateTree(); T->rchild=CreateTree(); } return T; }

void InThread(BiThreTree *T) {

BiThreTree *p; p=T; if(p)

{

InThread(p->lchild); if(!p->lchild) { p->LTag=Thread; p->lchild=pre; }

if(!pre->rchild) { pre->RTag=Thread; pre->rchild=p; } pre=p;

InThread(p->rchild); } }

BiThreTree *InOrderThrTree(BiThreTree *T) //中序线索化二叉树 {

BiThreTree *Thre; //Thre为头结点的指针 Thre=(BiThreTree *)malloc(sizeof(BiThreTree)); Thre->lchild=T; Thre->rchild=Thre; pre=Thre; InThread(T); pre->RTag=Thread; pre->rchild=Thre; Thre->rchild=pre; return Thre; }

void InThrTravel(BiThreTree *Thre) //中序遍历二叉树 {

BiThreTree *p; p=Thre->lchild;

while(p!=Thre) //指针回指向头结点时结束 {

while(p->LTag==Link) p=p->lchild;

printf(\"%4d\

while(p->RTag==Thread&&p->rchild!=Thre) {p=p->rchild; printf(\"%4d\ }

p=p->rchild; } } int main()

{

BiThreTree *T,*Thre; T=CreateTree(); Thre=InOrderThrTree(T); InThrTravel(Thre); system(\"pause\"); }

****************************************** 2。 struct node { T value;

node * left, * right; };

//traverse binary tree in pre-order fashion. * pMaxH should be //-1 initially indicating the value of * pMaxH be invalid int Traverse (node * pNode, int H, int * pMaxH, int * pMinH) {

int ret = 0; if (pNode == 0) {

//external node if (* pMaxH == -1) {

//the first external node * pMaxH = H; * pMinH = H - 1; ret = 1; } else {

if (H == * pMaxH) { ret = 1; } else {

if (H == * pMinH) {

* pMaxH = H; ret = 1;

} } } } else {

if ((ret = Traverse (pNode->left, H + 1, pMaxH, pMinH)) == 1) ret = Traverse (pNode->right, H + 1, pMaxH, pMinH); }

return ret; }

*************************************************** 3。

#include \"stdafx.h\" #include \"stdlib.h\"

typedef int Status; typedef int QElemType;

#define OVERFLOW -2 #define OK 1 #define ERROR 0

#define MAX_TREE_DEGREE 10

typedef struct BTnode{//以二叉链表作为存储结构 char data;

struct BTnode* lchild; struct BTnode* rchild; }BTnode,*BTree;

Status CreateBiTree(BTree &T)

{ /* 按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，*/ /* 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。*/ char ch; scanf(\"%c\ if(ch==' ') /* 空 */ T=NULL; else{

if(!(T=(BTnode *)malloc(sizeof(BTnode)))) /* 生成根结点 */ exit(OVERFLOW);

T->data=ch;

CreateBiTree(T->lchild); /* 构造左子树 */ CreateBiTree(T->rchild);/* 构造右子树 */ }

return OK; }

/*单链队列－－队列的链式存储结构 */ typedef struct QNode {

BTree data; struct QNode *next; }QNode,*QueuePtr;

typedef struct {

QueuePtr front,rear; /* 队头、队尾指针 */ }LinkQueue;

int initqueue(LinkQueue Q)//队列初始化 {

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit (OVERFLOW); Q.front->next=NULL; return OK; }

Status enqueue(LinkQueue Q,BTree e)//入队 {

QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode)); if(!p)

exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; }

Status dequeue(LinkQueue Q,BTree e)//出队 {

if(Q.front==Q.rear) return ERROR; QueuePtr p; p=Q.front->next; e=p->data;

Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); return OK; }

Status queueempty(LinkQueue Q)//判断队列是不是空的 {

if(Q.front==Q.rear) return ERROR; else return OK; }

Status iscompletetree(BTree T)//判断是否是完全二叉树、 {

LinkQueue Q; BTree p; p=T; if(!T) return 0; enqueue(Q,p); while(queueempty(Q)) { dequeue(Q,p); if(p) {

enqueue(Q,p->lchild); enqueue(Q,p->rchild); } if(!p) {

while(queueempty(Q)) {

dequeue(Q,p->rchild); if(p) {

printf(\"不是完全二叉树\"); return ERROR; }

} } }

return OK; }

int main(void)//简单测试 {

BTree root; CreateBiTree(root); iscompletetree(root); return ERROR; }