二叉树基本操作实现（二叉树的链式存储）

  1 #include <iostream>
  2 using namespace std;
  3 typedef struct bintree_node  
  4 {
  5     int data;
  6     bintree_node *lchild;
  7     bintree_node *rchild;
  8 }bintree_node;
  9 
 10 typedef struct stack
 11 {
 12     bintree_node *data[100];
 13     int tag[100];//为栈中每个元素设置标记，用于后序遍历
 14     int top;
 15 }seqstack;
 16 
 17 void push(seqstack *s, bintree_node *p)
 18 {
 19     s->data[++s->top] = p;
 20 }
 21 
 22 bintree_node *pop(seqstack *s)
 23 {
 24     if(s->top != -1)
 25     {
 26         s->top--;
 27         return (s->data[s->top + 1]);
 28     }
 29     else
 30         return NULL;
 31 }
 32 
 33 bintree_node *bintree_create()
 34 {
 35     bintree_node *p = (bintree_node *)malloc(sizeof(bintree_node));
 36     if(NULL == p)
 37     {
 38         cout << "alloc memory error!!!" << endl;
 39         return NULL;
 40     }
 41     cin >> (p->data);
 42     if(p->data == -1)
 43     {
 44         return NULL;
 45     }
 46     p->lchild = bintree_create();
 47     p->rchild = bintree_create();
 48     return p;
 49 }
 50 
 51 void prebintree(bintree_node *p)//前序遍历递归实现
 52 {
 53     if(p)
 54     {
 55         cout << p->data << "\t";
 56         prebintree(p->lchild);
 57         prebintree(p->rchild);
 58     }
 59 }
 60 void prebintree1(bintree_node *p)//前序遍历非递归实现
 61 {
 62     seqstack s;
 63     s.top = -1;
 64     while ((p) || (s.top != -1))
 65     {
 66         while (p)
 67         {
 68             cout << p->data << "\t";
 69             s.top++;
 70             s.data[s.top] = p;
 71             p = p->lchild;
 72         }
 73         if(s.top > -1)
 74         {
 75             p = pop(&s);
 76             p = p->rchild;
 77         }
 78     }
 79 }
 80 void levelTraverse(bintree_node *p)
 81 {
 82     bintree_node *queue[20];              
 83     bintree_node *tmp;
 84     int front = 0, rear = 0;//表示队头指针和队尾指针
 85     if(p)
 86     {
 87         tmp = p;//根指针入队
 88         queue[rear] = tmp;
 89         rear = (rear + 1)%20;//队尾指针加一对20取余，可实现循环队列，合理利用空间
 90         while(front != rear)//队不空
 91         {
 92             tmp = queue[front];//出队，将值赋给tmp
 93             cout << tmp->data;
 94             front = (front + 1)%20;
 95             if(tmp -> lchild)//如果tmp有左子树，将左子树入队
 96             {
 97                 queue[rear] = tmp->lchild;
 98                 rear = (rear + 1)%20;
 99             }
100             if(tmp->rchild)//如果tmp有右子树，将右子树入队
101             {
102                 queue[rear] = tmp->rchild;
103                 rear = (rear + 1)%20;
104             }
105         }
106     }
107 }
108 int main()
109 {
110     bintree_node *p = bintree_create();
111     prebintree1(p);
112     levelTraverse(p);
113     cout << endl;
114     return 0;
115 }