学步园

    二叉树的非递归算法，采用栈实现，本文给出了从设置栈到利用栈的完整代码，其中二叉树的后序遍历需要采用标志位，这样才可以有序的变非线性的结构为线性结构，二叉树生成的过程没有考虑平衡性的影响。期待下一步实现平衡二叉树遍历的实例。

#include <stdlib.h><br /> #include <stdio.h><br /> #include <conio.h><br /> #define maxsize 30<br /> typedef struct BinaryTree<br /> {<br /> int key;<br /> struct BinaryTree *left;<br /> struct BinaryTree *right;<br /> }Node,*node;<br /> typedef struct<br /> {<br /> Node* data[maxsize];<br /> int top;<br /> }SeqStack;<br /> SeqStack* StackInitialize()<br /> {<br /> SeqStack *s;<br /> s=(SeqStack* )malloc(sizeof(SeqStack));<br /> if(s==NULL)<br /> {<br /> printf("Stack Overflow/n");<br /> return NULL;<br /> }<br /> else<br /> {<br /> s->top=-1;<br /> return s;<br /> }<br /> }<br /> int IsEmpty(SeqStack* s)<br /> {<br /> if(s->top==-1)<br /> return 1;<br /> else return 0;<br /> }<br /> int Push(SeqStack* s,Node* data)<br /> {<br /> if(s->top==maxsize-1)<br /> {<br /> printf("The stack is full!/n");<br /> return 0;<br /> }<br /> else<br /> {<br /> s->top++;<br /> s->data[s->top]=data;<br /> return 1;<br /> }<br /> }<br /> Node* Pop(SeqStack* s)<br /> {<br /> Node* data;<br /> if(IsEmpty(s))<br /> {<br /> printf("The stack is empty!/n");<br /> return NULL;<br /> }<br /> else<br /> {<br /> data=s->data[s->top];<br /> s->top--;<br /> return data;<br /> }<br /> }<br /> Node* gettop(SeqStack* s)<br /> {<br /> Node* data;<br /> data=s->data[s->top];<br /> return data;<br /> }<br /> Node *InsertNode(Node* root,int val)<br /> {<br /> Node* temp;<br /> if (root==NULL)<br /> {<br /> temp=(Node* )malloc(sizeof(Node));<br /> root=temp;<br /> root->key=val;<br /> root->left=NULL;<br /> root->right=NULL;<br /> }<br /> else<br /> {<br /> if(val<=root->key)<br /> root->left=InsertNode(root->left,val);<br /> else<br /> root->right=InsertNode(root->right,val);<br /> }<br /> return(root);<br /> }<br /> void deleteTree(Node *root)<br /> {<br /> if (root->left!=NULL)<br /> deleteTree(root->left);<br /> if(root->right!=NULL)<br /> deleteTree(root->right);<br /> deleteTree(root);<br /> return;<br /> }<br /> void PreOrder(Node *root)<br /> {<br /> SeqStack* s;<br /> Node* p;<br /> p=root;<br /> s=StackInitialize();<br /> if(root=NULL)<br /> printf("The tree is empty!/n");<br /> while(p!=NULL||!IsEmpty(s))<br /> {<br /> if (p!=NULL)<br /> {<br /> Push(s,p);<br /> printf("%d ",p->key);<br /> p=p->left;<br /> }<br /> else<br /> {<br /> p=Pop(s);<br /> p=p->right;<br /> }<br /> }<br /> }<br /> void InOrder(Node* root)<br /> {<br /> SeqStack *s;<br /> Node *p;<br /> p=root;<br /> s=StackInitialize();<br /> if (root==NULL)<br /> printf("The Tree is empty/n");<br /> while(p!=NULL||!IsEmpty(s))<br /> {<br /> if (p!=NULL)<br /> {<br /> Push(s,p);<br /> p=p->left;<br /> }<br /> else<br /> {<br /> p=Pop(s);<br /> printf("%d ",p->key);<br /> p=p->right;<br /> }<br /> }<br /> }<br /> void PostOrder(Node* root)<br /> {<br /> SeqStack *s;<br /> Node *p,*q;<br /> p=root;<br /> int flag[maxsize];<br /> s=StackInitialize();<br /> if (root==NULL)<br /> printf("The Tree is empty/n");<br /> while(p!=NULL||!IsEmpty(s))<br /> {<br /> while (p!=NULL)<br /> {<br /> Push(s,p);<br /> flag[s->top]=0;<br /> p=p->left;<br /> }<br /> while(!IsEmpty(s)&&flag[s->top]==1)<br /> {<br /> p=Pop(s);<br /> printf("%d ",p->key);<br /> }<br /> if (!IsEmpty(s))<br /> {<br /> flag[s->top]=1;<br /> p=gettop(s);<br /> p=p->right;<br /> }<br /> else break;<br /> }<br /> }</p> <p>int main()<br /> {<br /> int val;<br /> Node *tree,*root;<br /> root=NULL;<br /> tree=NULL;<br /> while(1)<br /> {<br /> scanf("%d",&val);<br /> if(val<=0)<br /> break;<br /> else<br /> root=InsertNode(root,val);<br /> }<br /> InOrder(root);<br /> printf("/n");<br /> PreOrder(root);<br /> printf("/n");<br /> PostOrder(root);<br /> deleteTree(root);<br /> return 0;<br /> } 

2010-11-19