1 /*  2  * 二叉树  3  *  4  * (将完全二叉树的数组形式改为链表形式)  5  *  6  *                          1  7  *                     2              3  8  *                 4              5       6             7  9  *             8 10  * 11  */ 12 #include <iostream> 13 #define MAX 10 14 using namespace std; 15  16 typedef struct btnode{ 17     int data; 18     struct btnode * lchild; 19     struct btnode * rchild; 20 }btnode; 21  22 int main() { 23     int a[]={0,1,2,3,4,5,6,7,8}; 24     int n=8; 25     btnode * root; 26     btnode * create_bin(int arr[],int n,int i); 27                            //数组先序建立二叉树，并返回根结点指针。下标从1开始 28                 //n是元素个数，i是计数器 29     void trav_bi_preorder(btnode * root);    //先序遍历二叉树 30     void trav_bi_inorder(btnode * root);    //中序遍历二叉树(递归算法) 31     void trav_bi_inorder_nonrecur(btnode *root);       32                                                                //中序遍历二叉树（非递归算法） 33     root=create_bin(a,n,1); 34 //      trav_bi_preorder(root);                    //12485367 35     trav_bi_inorder(root); 36     cout << endl; 37     trav_bi_inorder_nonrecur(root); 38     return 0; 39 } 40  41 //利用数组元素建立完全二叉树 42 btnode * create_bin(int arr[],int n,int i){ 43     btnode * root=(btnode *)malloc(sizeof(btnode)); 44     if(i<=n){ 45         root->data=http://www.mamicode.com/arr[i]; 46         root->lchild=create_bin(arr,n,2*i); 47         root->rchild=create_bin(arr,n,2*i+1); 48         return root; 49     }else{ 50         return NULL; 51     } 52 } 53  54 //先序遍历二叉树(递归算法) 55 void trav_bi_preorder(btnode * root){ 56     if(root!=NULL){ 57         cout << root->data; 58         trav_bi_preorder(root->lchild); 59         trav_bi_preorder(root->rchild); 60     } 61 } 62  63 //中序遍历二叉树（递归算法） 64 void trav_bi_inorder(btnode * root){ 65     if(root!=NULL){ 66         trav_bi_inorder(root->lchild); 67         cout << root->data; 68         trav_bi_inorder(root->rchild); 69     } 70 } 71  72 /* 73  * 中序遍历二叉树（非递归算法） 74  * 75  * 中序遍历就是：从根开始一直沿着左支的方向去走，走到头之后，最左边 76  * 的结点作为第一个结点。然后沿途依次返回，遇到“分叉”的时候，向右边 77  * 转一个结点的位置，然后再一直沿着左支的方向走，走到头之后。。。 78  * 。。。一直到最后一个结点完事 79  * 80  * (这样用栈解决，每一个元素都是一个“中转站”，不断的回退，有中转就 81  * 压入栈中。。。) 82  */ 83 void trav_bi_inorder_nonrecur(btnode *root){ 84     btnode * st[MAX],* p,*q; 85     int top=-1; 86     st[++top]=root; 87     p=root; 88     while(top!=-1){                              89                                        //所有元素都从栈里出，整个大前提就是栈不空 90                                        //从当前结点一路向左 91         while(p!=NULL){                     92             st[++top]=p->lchild; 93             p=p->lchild; 94         } 95         top--;                         96                                 //    上面的while一路向左，最后NULL一定入栈。 97                     //所以要用这句话干掉NULL 98                         //    下面的if，可能弹出元素的右子是NULL，故 99                 //NULL入栈，这时while不会执行，这句就干掉NULL；100                 //若右子不为NULL,就会执行while，所以仍然需要这101                                 //句话干掉NULL102         if(top!=-1){103             p=st[top--];104             cout << p->data;105             st[++top]=p->rchild;106             p=p->rchild;107         }108     }109 }110