遍历二叉树.cpp

这是一个二叉树的算法,主要用C++开发,只写了二叉树的核心代码,该代码已经调试通过可以直接运行.该算法也没有输入功能,为了方便大家看清二叉树的结构,把输入的数据都在源码中用一个数组存放好的

#define MAX_TREE_DEGREE 10
#include<stdio.h>
#include<stdlib.h> //定义杂项函数及内存分配函数
typedef struct BTnode{// 结点结构
	       char data;
	       struct BTnode* lchild;
           struct BTnode* rchild;
           }BTnode,*BTree;
  int   createBTree(BTree* T){
        char ch;
        //输入空格表示表示空子树
        scanf("%c",&ch);
        if(ch == ' ')
               *T = NULL;
        else{
             if(!(*T = (BTnode*)malloc(sizeof(BTnode))))
                return -1;
             (*T)->data = ch;
             createBTree(&(*T)->lchild);
             createBTree(&(*T)->rchild);
             }
        return 1;
}
int print(BTree T)
{
     printf("%c",T->data);
      return 1;
}

      int preOrdTr1(BTree T){
     //T为非空树才进行遍历
        if(T){//以下三个if语句部分，只有每个部分都处理成功才返回1也即遍历成功
             if(print(T))
                 if(preOrdTr1(T->lchild))
                     if(preOrdTr1(T->rchild))
                         return 1;
             return 0;//在返回类型是int的函数中，如果是要停止函数的调用，最好应该为0
     }else
         return 1;
 }

      int preOrdTr2(BTree T){
         int top = 0;//数组索引
         BTree p = T;
         //存放各个已经访问过的接点指针，便于"回溯",用栈来存储指针。
         BTree nodePointer[MAX_TREE_DEGREE];
         //循环建立在非空树或者栈非空的基础上
          while(p || top > 0){
              if(p){
                 print(p);
                 nodePointer[top] = p;
                 ++ top;
                 p = p->lchild;
             }
             //如果栈非空，出栈并且访问该叶子接点的兄弟子树
              else{
                 -- top;
                 p = nodePointer[top];
                 p = p->rchild;
             }//if
         }
         return 1;
 }
 
    int inOrdTr1(BTree T)
	{
          if(T)
		  {//中根递归只是将先根递归的两条语句交换一下位置而已
             if(inOrdTr1(T->lchild))
                 if(print(T))
                     if(inOrdTr1(T->rchild))
                         return 1;
             return 0;
         }else
             return 1;
	}
     
      int inOrdTr2(BTree T)
	  {
         int top = 0;
         BTree p = T;
         //同样需要设置一个栈来存放接点指针，便于以后的回溯
         BTree nodePointer[MAX_TREE_DEGREE];
         //非空指针或者非空栈时候存在循环
          while(p || top > 0)
		  {
              if(p)
			  {
                 nodePointer[top] = p;
                 ++ top;
                 p = p->lchild;
              }
			  else
			  {
                 -- top;
                 p = nodePointer[top];
                 print(p);
                 p = p->rchild;
             }
         }
         return 1;
     }

     int postOrdTr1(BTree T){
          if(T)
		  {//同样是简单交换位置而已，可见递归实现的清楚简洁。
             if(postOrdTr1(T->lchild))
                 if(postOrdTr1(T->rchild))
                     if(print(T))
                         return 1;
             return 0;
         }else
             return 1;
     }



int postOrdTr2(BTree T){
         int top = 0;
         int tags[MAX_TREE_DEGREE];//tag stack
         BTree p = T;
         BTree nodePointer[MAX_TREE_DEGREE];
 
          while(p || top > 0){
              if(p){
                 nodePointer[top] = p;
                 //初始化当前入栈接点指针的初值为0
                 tags[top] = 0;
                 ++ top;
                 p = p->lchild;
             }
              else if( tags[--top] == 0){//访问右子树并且设置tag为1
                 tags[top] = 1;
                 p = nodePointer[top];
                 p = p->rchild;
                 //下面的自增运算表示是"copy"而不是"pop"接点指针
                 ++ top;
              }else{//出栈 No "++top"
                 p = nodePointer[top];
                 print(p);
             }
             return 1;
         }//while
     }
 int main(){
  BTree T;
  printf("请输入所要创建的二叉树（先序）：\n");
  createBTree(&T);
  printf("先序遍历的递归与非递归实现结果：\n");
  preOrdTr1(T);
  printf("\n");
  preOrdTr2(T);
  printf("\n");
  printf("中序遍历的递归与非递归实现结果：\n");
  inOrdTr1(T);
  printf("\n");
  inOrdTr2(T);
  printf("\n");
  printf("后序遍历的递归与非递归实现结果：\n");
  postOrdTr1(T);
  printf("\n");
  postOrdTr2(T);
  return 0;
 }