本文共 3149 字，大约阅读时间需要 10 分钟。

二叉树的递归图：

//数据结构---二叉树基础知识总结（小白专场）---c语言实现//树作为一种基本的数据结构，在学习的过程中，主要要去学习：递归的思想，因为树本身就是递归定义的。//栈，和队列直接用的c++标准库里的（为了简洁）#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef char ElemType;typedef struct BiNode{ ElemType data; struct BiNode *Left; struct BiNode *Right;}BiNode, *BiTree;//先序拓展序列建立二叉树 ，根据前序遍历结果创建二叉树。void create(BiTree &T) //这里是引用。必须要引用~~~。{ ElemType c; scanf("%c", &c); if (c == '#') T = NULL; //如果输入为#，则T=NULL，否则新建节点。这个很容易错误。 else { T = (BiTree)malloc(sizeof(BiNode)); T->data = c; create(T->Left); create(T->Right); }}//递归遍历，三种遍历代码虽短，但是递归的历程自己脑子里一定要走一边，对理解递归有很大帮助。void preorder(BiTree T) //前序。{ if (T) { printf("%c\t", T->data); preorder(T->Left); preorder(T->Right); }}void inorder(BiTree T)//中序{ if (T) { inorder(T->Left); printf("%c\t", T->data); inorder(T->Right); }}void postorder(BiTree T)//后序{ if (T) { postorder(T->Left); postorder(T->Right); printf("%c\t", T->data); }}//非递归遍历,我感觉，写非递归遍历就是在看自己对递归遍历的理解程度！ 根据等下遍历顺序图好好理解！！！void preorder1(BiTree T)//这种是参考下就行！{ stack
         
          S; S.push(T); while (!S.empty()) { T = S.top(); S.pop(); printf("%c\t", T->data); if (T->Right)S.push(T->Right);//先压右 if (T->Left)S.push(T->Left); }}//接下来几种非递归遍历好好理解！！！//前序和中序void preorder2(BiTree T){ stack
          
           S; while (T || !S.empty()) { while (T) //这个循环意味着只要左边有节点就一直走 { S.push(T); printf("%c\t", T->data); //前序，push意味着第一次碰到就直接访问 T = T->Left; } if (!S.empty()) //这个循环意味着从左边上去就要往右边走 一 下， 一 下， 一下 { T = S.top(); S.pop(); // printf("%d\t", T->data); 中序，如果把printf放在这里就是非递归中序遍历了。pop出来的时候第二次碰到！ T = T->Right; } }}//后序//上面的代码并不能通过简单的移动printf的位置来实现后序遍历，因为从右边上来的时候，并没有被记录void postorder1(BiTree T){ stack
           
            S; BiTree Previsited = NULL; while (T || !S.empty()) { while (T) { S.push(T); T = T->Left; } BiTree tmp = S.top(); if (tmp->Right == NULL||tmp->Right == Previsited)//右边为空，或者右边的刚才访问了 { printf("%c\t", tmp->data); Previsited = tmp; S.pop(); } else T = tmp->Right; }}//非递归 完美模拟 递归历程， 通过调换访问（printf）语句就可实现前中后遍历//这个如果不能理解，看上面的递归图会好点~enum State { Start, return_from_left, return_from_right }; //状态量typedef struct { enum State state; BiTree T; }StackElem;void postorder2(BiTree BT){ StackElem item = { Start,BT }; stack
            
             S; while (1) { if (item.T) { if (item.state == Start) { S.push(item); //printf("%c\t", item.T->data); //前序 item.T = item.T->Left; item.state = Start; } else if (item.state == return_from_left)//来自左边 { S.push(item); //printf("%c\t", item.T->data); //中序 item.T = item.T->Right; item.state = Start; } else { //来自右边 printf("%c\t", item.T->data); //后序 if (!S.empty()) { item = S.top(); S.pop(); item.state = (enum State)(item.state + 1); } else break; } } else { if (!S.empty()) { item = S.top(); S.pop(); item.state = (enum State)(item.state + 1); //C++文件不能用自增！~ } else break; } }} //层序遍历void levelorder(BiTree T){ queue
             
              Q; BiTree tmp = T; if (T) { Q.push(tmp); while (!Q.empty()) { tmp = Q.front(); Q.pop(); printf("%c\t", tmp->data); if (tmp->Left)Q.push(tmp->Left); if (tmp->Right)Q.push(tmp->Right); } }}int main(){ //想测哪个函数在这里直接改一下 BiTree T; create(T); preorder(T); printf("\n"); inorder(T); printf("\n"); postorder(T); printf("\n"); system("pause");}//测试数据 abd###c##