中山手机网站设计,谷歌搜索引擎官网,纯文本网站,泉州百度网站快速优化二叉树的遍历分为前序遍历#xff0c;中序遍历#xff0c;后序遍历#xff0c;层序遍历#xff0c;在本文中#xff0c;前三种由递归实现#xff0c;层序遍历由队列实现。
#include stdio.h
#include stdlib.h
#include windows.h
…二叉树的遍历分为前序遍历中序遍历后序遍历层序遍历在本文中前三种由递归实现层序遍历由队列实现。
#include stdio.h
#include stdlib.h
#include windows.h
typedef struct Node
{char data;struct Node *Left;struct Node *Right;struct Node *Next;
}BT;typedef struct { /* 链队列结构 */BT *rear; /* 指向队尾结点 */BT *front; /* 指向队头结点 */
} LinkQueue;
//入队
LinkQueue* AddQuee(LinkQueue *PtrL,BT* item)
{BT *node;nodePtrL-rear;if (PtrL-frontNULL){BT *q(BT*)malloc(sizeof(BT));q-Leftitem-Left;q-Rightitem-Right;q-NextNULL;q-dataitem-data;PtrL-frontq;PtrL-rearq;return PtrL;}else{BT *q(BT*)malloc(sizeof(BT));q-NextNULL;q-Leftitem-Left;q-Rightitem-Right;q-dataitem-data;node-Nextq;PtrL-rearq;return PtrL;}
}
//出队
BT* DeleteQ ( LinkQueue *PtrQ )
{BT *firstNode;//BT* NodeItem;if (PtrQ-frontNULL){printf(queue is empty);return NULL;}firstNodePtrQ-front;if (PtrQ-frontPtrQ-rear){PtrQ-frontPtrQ-rearNULL;}else{PtrQ-frontPtrQ-front-Next;}//NodeItem-datafirstNode-data;//free(firstNode);return firstNode;
}
//判断是否为空
int isempty(LinkQueue *PtrL)
{if (PtrL-rearNULL){return 1;}else{return 0;}
}BT *CreateBiTree()
{char ch;BT *T;printf(please enter tree node:);scanf(%c,ch);if (ch#){TNULL;}else{T(BT*)malloc(sizeof(BT));T-datach;T-LeftCreateBiTree();T-RightCreateBiTree();}return T;
}//先序遍历
void PreOrderTraversal( BT* tree)
{if (tree){printf(%c ,tree-data);PreOrderTraversal(tree-Left);PreOrderTraversal(tree-Right);}
}//中序遍历
void InOrderTraversal(BT* tree)
{if (tree){PreOrderTraversal(tree-Left);printf(%c ,tree-data);PreOrderTraversal(tree-Right);}
}//后序遍历
void PostOderTraversal(BT *tree)
{if (tree){PostOderTraversal(tree-Left);PostOderTraversal(tree-Right);printf(%c ,tree-data);}
}
//层序遍历
void LevelOrderTraversal(BT *tree)
{BT *bt;LinkQueue *q(LinkQueue*)malloc(sizeof(LinkQueue));q-frontNULL;q-rearNULL;if (!tree){return;}AddQuee(q,tree);while(isempty(q)0){btDeleteQ(q);printf(%c ,bt-data);if (bt-Left) AddQuee(q,bt-Left);if (bt-Right) AddQuee(q,bt-Right);}}int PostOrderGetHeight( BT* tree )
{int HL, HR, MaxH;if( tree ) {HL PostOrderGetHeight(tree-Left); /*求左子树的深度*/HR PostOrderGetHeight(tree-Right); /*求右子树的深度*/MaxH (HL HR)? HL : HR;/*取左右子树较大的深度*/return ( MaxH 1 ); /*返回树的深度*/}else return 0; /* 空树深度为0 */
}void main()
{BT *t;int a;tCreateBiTree();printf(\n1.PreOrderTraversal\n);printf(2.MidOrderTraversal\n);printf(3.PostOrderTraversal\n);printf(4.EXIT\n);printf(5.LevelOrderTraversal\n);printf(6.show the hieght of the tree);while (1){printf(please enter your order:);scanf(%d,a);switch (a){case 1:PreOrderTraversal(t);break;case 2:InOrderTraversal(t);break;case 3:PostOderTraversal(t);break;case 4:exit(0);break;case 5:LevelOrderTraversal(t);break;case 6:printf(%d,PostOrderGetHeight(t));break;default:break;}}
}
运行结果 C实现二叉树的遍历
#include iostream
#include stack
#include queueusing namespace std;//二叉树结点
typedef struct BiTNode{//数据char data;//左右孩子指针struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//按先序序列创建二叉树
int CreateBiTree(BiTree T){char data;//按先序次序输入二叉树中结点的值一个字符‘#’表示空树scanf(%c,data);if(data #){T NULL;}else{T (BiTree)malloc(sizeof(BiTNode));//生成根结点T-data data;//构造左子树CreateBiTree(T-lchild);//构造右子树CreateBiTree(T-rchild);}return 0;
}
//输出
void Visit(BiTree T){if(T-data ! #){printf(%c ,T-data);}
}
//先序遍历
void PreOrder(BiTree T){if(T ! NULL){//访问根节点Visit(T);//访问左子结点PreOrder(T-lchild);//访问右子结点PreOrder(T-rchild);}
}
//中序遍历
void InOrder(BiTree T){ if(T ! NULL){ //访问左子结点 InOrder(T-lchild); //访问根节点 Visit(T); //访问右子结点 InOrder(T-rchild); }
}
//后序遍历
void PostOrder(BiTree T){if(T ! NULL){//访问左子结点PostOrder(T-lchild);//访问右子结点PostOrder(T-rchild);//访问根节点Visit(T);}
}
/* 先序遍历(非递归)思路访问T-data后将T入栈遍历左子树遍历完左子树返回时栈顶元素应为T出栈再先序遍历T的右子树。
*/
void PreOrder2(BiTree T){stackBiTree stack;//p是遍历指针BiTree p T;//栈不空或者p不空时循环while(p || !stack.empty()){if(p ! NULL){//存入栈中stack.push(p);//访问根节点printf(%c ,p-data);//遍历左子树p p-lchild;}else{//退栈p stack.top();stack.pop();//访问右子树p p-rchild;}}//while
}
/* 中序遍历(非递归)思路T是要遍历树的根指针中序遍历要求在遍历完左子树后访问根再遍历右子树。先将T入栈遍历左子树遍历完左子树返回时栈顶元素应为T出栈访问T-data再中序遍历T的右子树。
*/
void InOrder2(BiTree T){stackBiTree stack;//p是遍历指针BiTree p T;//栈不空或者p不空时循环while(p || !stack.empty()){if(p ! NULL){//存入栈中stack.push(p);//遍历左子树p p-lchild;}else{//退栈访问根节点p stack.top();printf(%c ,p-data);stack.pop();//访问右子树p p-rchild;}}//while
}//后序遍历(非递归)
typedef struct BiTNodePost{BiTree biTree;char tag;
}BiTNodePost,*BiTreePost;void PostOrder2(BiTree T){stackBiTreePost stack;//p是遍历指针BiTree p T;BiTreePost BT;//栈不空或者p不空时循环while(p ! NULL || !stack.empty()){//遍历左子树while(p ! NULL){BT (BiTreePost)malloc(sizeof(BiTNodePost));BT-biTree p;//访问过左子树BT-tag L;stack.push(BT);p p-lchild;}//左右子树访问完毕访问根节点while(!stack.empty() (stack.top())-tag R){BT stack.top();//退栈stack.pop();BT-biTree;printf(%c ,BT-biTree-data);}//遍历右子树if(!stack.empty()){BT stack.top();//访问过右子树BT-tag R;p BT-biTree;p p-rchild;}}//while
}
//层次遍历
void LevelOrder(BiTree T){BiTree p T;//队列queueBiTree queue;//根节点入队queue.push(p);//队列不空循环while(!queue.empty()){//对头元素出队p queue.front();//访问p指向的结点printf(%c ,p-data);//退出队列queue.pop();//左子树不空将左子树入队if(p-lchild ! NULL){queue.push(p-lchild);}//右子树不空将右子树入队if(p-rchild ! NULL){queue.push(p-rchild);}}
}
int main()
{BiTree T;CreateBiTree(T);printf(先序遍历\n);PreOrder(T);printf(\n);printf(先序遍历(非递归)\n);PreOrder2(T);printf(\n);printf(中序遍历\n);InOrder(T);printf(\n);printf(中序遍历(非递归)\n);InOrder2(T);printf(\n);printf(后序遍历\n);PostOrder(T);printf(\n);printf(后序遍历(非递归)\n);PostOrder2(T);printf(\n);printf(层次遍历\n);LevelOrder(T);printf(\n);system(pause);return 0;
}
