下面是用c语言实现的一些有关栈的基本操作:
1 #include<iostream> 2 using namespace std; 3 #include <stack> 4 #define MAXSIZE 1000 5 typedef int ElemType; 6 7 typedef struct TNode 8 { 9 ElemType data; 10 struct TNode *lchild, *rchild; 11 }TNode, *Tree; 12 13 /*建立一颗二叉树*/ 14 void BuildTree(Tree &root, int &index) 15 { 16 index++; 17 ElemType temp[] = {2,4,5,-1,3,-1,-1,-1,0,7,6,-1,-1,-1,8,-1,-1}; 18 if(temp[index]==-1) 19 { 20 root = NULL; 21 return; 22 } 23 else 24 { 25 root = (TNode *)malloc(sizeof(TNode)); 26 root->data = temp[index]; 27 BuildTree(root->lchild, index); 28 BuildTree(root->rchild, index); 29 } 30 } 31 32 /*递归先序遍历*/ 33 void preOrder(Tree tree) 34 { 35 if(tree == NULL) 36 { 37 return; 38 } 39 else 40 { 41 printf("%d ", tree->data); 42 preOrder(tree->lchild); 43 preOrder(tree->rchild); 44 } 45 } 46 47 /*递归中序遍历*/ 48 void inOrder(Tree tree) 49 { 50 if(tree == NULL) 51 { 52 return; 53 } 54 else 55 { 56 inOrder(tree->lchild); 57 printf("%d ", tree->data); 58 inOrder(tree->rchild); 59 } 60 } 61 /*递归后序遍历*/ 62 void postOrder(Tree tree) 63 { 64 if(tree == NULL) 65 { 66 return ; 67 } 68 else 69 { 70 postOrder(tree->lchild); 71 postOrder(tree->rchild); 72 printf("%d ", tree->data); 73 } 74 } 75 76 /*非递归的进行先序遍历*/ 77 void recurrence_preOrder(Tree tree) 78 { 79 stack<Tree> s; 80 Tree p =tree; 81 while(p||(!s.empty())) 82 { 83 if(p) 84 { 85 cout<<p->data<<" "; 86 s.push(p); 87 p=p->lchild; 88 } 89 else 90 { 91 p=s.top()->rchild; 92 s.pop(); 93 } 94 } 95 } 96 97 void recurrence_InOrder(Tree tree) 98 { 99 stack<Tree> s; 100 TNode *p = tree; 101 while(p||!s.empty()) 102 { 103 while(p) 104 { 105 s.push(p); 106 p = p->lchild; 107 } 108 if(!s.empty()) 109 { 110 p = s.top(); 111 cout<<p->data<<" "; 112 s.pop(); 113 p = p->rchild; 114 } 115 } 116 cout<<endl; 117 } 118 int main() 119 { 120 Tree tree; 121 int index = -1; 122 BuildTree(tree, index); 123 cout<<"构建的树:"<<endl 124 <<"1 2 "<<endl 125 <<"2 4 0 "<<endl 126 <<"3 5 -1 7 8 "<<endl 127 <<"4 -1 3 6 -1 -1 -1 "<<endl 128 <<"5 -1 -1 -1 -1 "<<endl<<endl; 129 130 /*先序遍历*/ 131 cout<<"递归先序遍历结果为:"<<endl; 132 preOrder(tree); 133 134 /*中序遍历*/ 135 cout<<"\n递归中序遍历结果为:"<<endl; 136 inOrder(tree); 137 138 /*后续遍历*/ 139 cout<<"\n递归后续遍历结果为:"<<endl; 140 postOrder(tree); 141 142 /*非递归先序遍历*/ 143 cout<<"\n非递归先序遍历的结果为:"<<endl; 144 recurrence_preOrder(tree); 145 146 /*非递归中序遍历*/ 147 cout<<"\n非递归中序遍历的结果为:"<<endl; 148 recurrence_InOrder(tree); 149 system("pause"); 150 return 0; 151 }
其中由于非递归后续遍历比较麻烦,所以这里没有编写代码。
有不懂的可以留言,如果这篇文章对你有帮助,请帮忙给个赞!!!!