二叉树的遍历学习心得.docx

二叉树的遍历学习心得

第一篇：二叉树的遍历学习心得二叉树的非递归遍历学习心得对于学习数据结构的新手来说，二叉树应该是遇到的一个比较大的难题。对于二叉树的遍历，如果使用递归的方法，代码非常简单，但是有些程序语言不支持递归，而且递归的执行效率偏低，使许多程序设计人员望而却步下面我将与大家分享我在学习二叉树的非递归遍历的过程中遇到的困惑与解答，以供学习和交流。鉴于有些数据结构资料中没有介绍树的结点的栈的结点的构造，首先向大家介绍结点的构造。typedefstructBitNode{chardata;树的结点的数据域（以字符型数据为树的结点的结构例）structBitNode*lchild,*rchild;树的子树指针}BitNode,*BitTree;typedefstructnode{BitNodestack;栈的数据域类型为树的结点栈的结点结构structnode*next;}LinkStack;遍历的前提当然是二叉树存在，下面为大家介绍树的建立。BitTreeCreat_BitTree(){BitTreebt;树的根结点charx;scanf(“%c”,&x);树的建立的子函数类型为树的指针类型}if(x=='#')bt=NULL;else{}returnbt;如果输入为’#’，则返回空结点bt=(BitTree)malloc(sizeof(BitNode));若输入有效，则申请结点空间bt->data=x;装填结点插入左子树插入右子树bt->lchild=Creat_BitTree();bt->rchild=Creat_BitTree();建立二叉树的过程使用了递归，如果理解不了，可以自己画图助于理解，建立决定了二叉树的形状，一定要弄清楚。如所要建立的二叉树的形状为那么输入应该为ABD##EG###。接下来是栈的一些操作，因为任何一本数据结构的资料都会在栈和队列的章节说得很清楚，下面只是做了一些比较小的改动，请读者自行体会。intInit_Stack(LinkStack**s){}intPush_Stack(LinkStack*s,BitNode*x)*s=(LinkStack*)malloc(sizeof(LinkStack));(*s)->next=NULL;return1;{}intPop_Stack(LinkStack*s,BitNode*e){return0;}}intEmpty_Stack(LinkStack*s){}if(s->next==NULL)return1;return0;LinkStack*p;if(Empty_Stack(s)){printf(“StackisNULLn”);p=s->next;s->next=p->next;*e=p->stack;free(p);return1;LinkStack*p;p=(LinkStack*)malloc(sizeof(LinkStack));p->stack=*x;p->next=s->next;s->next=p;return1;先介绍先序遍历的算法，先建立根结点，再建立左子树再到右子树，遍历是相对于每一棵子树来说的，这一点要格外注意。最重要的是要在脑海里建立模型，在后面的后序遍历中尤显模型的重要性。voidPre_Order(BitTreeT){}以下是主函数。intmain(){BitTreeT;printf(“nt********************欢迎来到二叉LinkStack*s;BitTreep;p=T;Init_Stack(&s);Push_Stack(s,p);while(!Empty_Stack(s)){Pop_Stack(s,p);printf(”t[%c]“,p->data);if(p->rchild)Push_Stack(s,p->rchild);if(p->lchild)Push_Stack(s,p->lchild);}树世界********************n”);printf(“nt请输入二叉树结点，”#“为空树nt”);T=Creat_BitTree();printf(“n”);printf(“t先序遍历二叉树如下：”);printf(“n”);}Pre_Order(T);printf(“nt”);getch();以下是二叉树的中序遍历的算法，先从左子树入栈到底，然后访问栈顶元素，同时栈顶出栈，再检测是否存在右子树，如果存在，从它的右子树的左子树入栈到底，如果不存在，访问栈顶元素，同时栈顶出栈，如此循环，直到栈空。voidIn_Order(BitTreeT){}LinkStack*s;BitTreep,q;q=(BitTree)malloc(sizeof(BitNode));p=T;Init_Stack(&s);