完全二叉树的链式存储结构的转化 & 非递归中序遍历二叉树

  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=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                                 //句话干掉NULL
102         if(top!=-1){
103             p=st[top--];
104             cout << p->data;
105             st[++top]=p->rchild;
106             p=p->rchild;
107         }
108     }
109 }
110