二叉树的建立和遍历-白红宇

二叉树的建立和遍历

阅读量：6544 次

发布时间：2019-06-24

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

Date：2019-06-28 13:51:23

二叉树的建立

注意一下中序和层序建树

1  2 //给出当前先序序列PreL, PreL+1, ..., Pre(L+numLeft), Pre(L+numLeft+1), ..., PreR 3 //给出当前中序序列InL, InL+1, ..., In(K-1), InK, In(k+1), ..., InR 4 BiTnode* CreatePreIn(int preL, int preR, int inL, int inR) 5 { 6     if(preL > preR) 7         return NULL;    //先序序列长度小于0 8  9     BiTnode *root = new BiTnode;10     root->data = pre[preL];11     int k;12     for(int k=inL; k<=inR; k++)13         if(in[k] == pre[preL])  //在中序序列中找到根节点14             break;15     int numLeft = k - inL;      //由中序序列得到左子树结点的个数16 17     //左子树的先序区间为[preL+1, preL+numLeft], 左子树的中序区间为[inL, k-1];18     root->lchild = CreatePreIn(preL+1, preL+numLeft, inL, k-1);19     //右子树的先序区间为[preL+numLeft+1, preR], 右子树的中序区间为[k+1, inR];20     root->rchild = CreatePreIn(preL+numLeft+1, preR, k+1, inR);21 22     return root;23 }24 25 //给出当前后序序列PostL, PostL+1, ..., Post(L+numLeft-1), Post(L+numLeft), ..., Pre(R-1), PreR26 //给出当前中序序列InL, InL+1, ..., In(k-1), Ink, In(k+1), ..., InR27 BiTnode* CreatePostIn(int postL, int postR, int InL, int inR)28 {29     if(postL > postR)30         return NULL;31 32     BiTnode *root = new BiTnode;33     root->data = post[postR];34     int k;35     for(int k=inL; k<=inR; k++)36         if(In[k] == post[postR])37             break;38     int numleft = k - inL;39 40     root->lchild = CreatePostIn(postL, postL+numLeft-1, inL, k-1);41     root->rchild = CreatePostIn(postL+numLeft, postR-1, k+1, inR);42 43     return root;44 }45 46 //给出当前中序序列InL, ..., In(k-1), Ink, In(k+1), ..., InR47 //给出当前层次序列layerL, ..., layerR48 BiTnode* CreateLayerIn(int inL, int inR, int layerL, int layerR)49 {50     if(inL > inR)51         return NULL;52     BiTnode *root = new BiTnode;53 54     int i, j;55     for(int i=layerL; i<=layerR; i++)56     {57         int x=0;58         for(int j=inL; j<=inR; j++)59         {60             if(layer[i] = in[j])61             {62                 b = 1;63                 root->data = in[j];64                 break;65             }66         }67         if(b)   break;68     }69     root->lchild = CreateLayerIn(inL, j-1, layerL, layerR);70     root->rchild = CreateLayerIn(j+1, inR, layerL, layerR);71 72     return root;73 }

二叉树的遍历

1 //先序  2 void PreOrder(BiTnode* T)  3 {  4     if(T == NULL)  5         return;  6     //visit(T);  7     PreOrder(T->lchild);  8     PreOrder(T->rchild);  9 } 10  11 //先序非递归 12 #include 
     
       13 using namespace std; 14 void PreOrder(BiTnode* T) 15 { 16     stack
      
        s; 17     BiTnode *p = T; 18     while(p || !s.empty()) 19     { 20         if(p) 21         { 22             //visit(p); 23             s.push(p); 24             p = p->lchild; 25         } 26         else 27         { 28             p = s.top(); 29             s.pop(); 30             p = p->rchild; 31         } 32     } 33 } 34  35 //中序 36 void InOrder(BiTnode* T) 37 { 38     if(T == NULL) 39         return 40     InOrder(T->lchild); 41     //visit(T); 42     InOrder(T->rchild); 43 } 44  45 //中序非递归 46 #include 
       
         47 using namespace std; 48 void InOrder2(BiTnode* T) 49 { 50     stack
        
          s; 51     BiTnode *p = T; 52     while(p || !s.empty()) 53     { 54         if(p) 55         { 56             s.push(p); 57             p = p->lchild; 58         } 59 else 60 { 61 p = s.top(); 62 //visit(p); 63 s.pop(); 64 p = p->rchild; 65 } 66 } 67 } 68  69 //后序 70 void PostOrder(BiTnode* T) 71 { 72     if(T == NULL) 73         return; 74     PostOrder(T->lchild); 75     PostOrder(T->rchild); 76     //visit(T); 77 } 78  79 //后序非递归 80 void PostOrder(BiTnode* T) 81 { 82     stack
         
           s; 83     BiTnode *p, *r=NULL; 84     while(p || !s.empty()) 85     { 86         if(p) 87         { 88             s.push(p); 89             p = p->lchild; 90         } 91         else 92         { 93             p = s.top(); 94             if(p->rchild && p->rchild!=r) 95             { 96                 p = p->rchild; 97                 s.push(p); 98                 p = p->lchild; 99             }100             else101             {   //p出栈时，栈内为根节点到p的路径，以此可以求解公共结点等102                 //visit(p);103                 s.pop();104                 r = p;105                 p = NULL;106             }107         }108     }109 }110 111 //层次112 #include 
          
           113 using namespace std;114 void LevelOrder(BiTnode* T)115 {116 queue
           
             q; //队列中存放BiTnode变量的地址，这样就可以通过访问地址去修改原元素117 T->level = 1; //记录结点深度118 q.push(T);119 while(!q.empty())120 {121 BiTnode *p = q.front();122 q.pop();123 //visit(p);124 if(p->lchild)125 {126 p->lchild->level = p->level + 1; //计算各结点深度127 q.push(p->lchild);128 }129 if(p->rchild)130 {131 p->rchild->level = p->level + 1;132 q.push(p->rchild);133 }134 }135 }

多叉树的静态表示

1 //存储结构：孩子表示法 2 #include 
     
       3 using namespace std; 4 const int M = 1e3; 5 struct node 6 { 7     int layer;  //结点深度 8     int data; 9     vector
      
        children;10 }tree[M];11 12 //若结点不涉及数据域，可以简化结点结构13 vector
       
         child[M];14 15 //插入结点16 int index=0;17 int NewNode(int x)18 {19     tree[index].data = x;20     tree[index].children.clear();21     return index++;22 }23 24 //遍历25 void PreOrder(int root)26 {27     printf("%d ", tree[root].data);     //先根遍历28     for(int i=0; i
        
         35 using namespace std;36 void LayerOrder(int root)37 {38     queue
         
           q;39     tree[root].layer = 0;40     q.push(root);41     while(!q.empty())42     {43         root = q.front();44         q.pop();45         printf("%d ", tree[root].data);46         for(int i=0; i