二叉树的创建+递归遍历+非递归遍历 落日映苍穹つ 2022-05-19 01:58 247阅读 0赞 #include<iostream> #include<stdlib.h> #define MAXSIZE 100 typedef char ElementType; using namespace std; typedef struct BTNode{ ElementType data; struct BTNode *lChild; struct BTNode *rChild; }BTNode; void createBinaryTree(BTNode *&bt) { ElementType data; bt = (BTNode *)malloc(sizeof(BTNode)); cin>>data; if(data == '#') { bt = NULL; } else { bt->data = data; createBinaryTree(bt->lChild); createBinaryTree(bt->rChild); } } void preOrderRecursionVisit(BTNode *bt) { if(bt == NULL) return; else { cout<<bt->data<<" "; preOrderRecursionVisit(bt->lChild); preOrderRecursionVisit(bt->rChild); } } void preOrderNonRecursionVisit(BTNode *bt) { if(bt == NULL) return; BTNode *stack[MAXSIZE], *tNode; int top = -1; stack[++top] = bt; while(top != -1) { tNode = stack[top--]; cout<<tNode->data<<" "; if(tNode->rChild != NULL) stack[++top] = tNode->rChild; if(tNode->lChild != NULL) stack[++top] = tNode->lChild; } cout<<endl; } void inOrderRecursionVisit(BTNode *bt) { if(bt == NULL) return; else { inOrderRecursionVisit(bt->lChild); cout<<bt->data<<" "; inOrderRecursionVisit(bt->rChild); } } void inOrderNonRecursionVisit(BTNode *bt) { if(bt == NULL) return; BTNode *stack[MAXSIZE], *tNode; int top = -1; tNode = bt; while(top != -1 || tNode != NULL) { while(tNode != NULL) { stack[++top] = tNode; tNode = tNode->lChild; } if(top != -1) { tNode = stack[top--]; cout<<tNode->data<<" "; if(tNode->rChild != NULL) tNode = tNode->rChild; else tNode = NULL; } } cout<<endl; } void postOrderRecursionVisit(BTNode *bt) { if(bt == NULL) return; else { postOrderRecursionVisit(bt->lChild); postOrderRecursionVisit(bt->rChild); cout<<bt->data<<" "; } } void postOrderNonRecursionVisit(BTNode *bt) { if(bt == NULL) return; BTNode *tNode, *stack1[MAXSIZE], *stack2[MAXSIZE]; int top1 = -1, top2 = -1; stack1[++top1] = bt; while(top1 != -1) { tNode = stack1[top1--]; stack2[++top2] = tNode; if(tNode->lChild != NULL) stack1[++top1] = tNode->lChild; if(tNode->rChild != NULL) stack1[++top1] = tNode->rChild; } while(top2 != -1) { tNode = stack2[top2--]; cout<<tNode->data<<" "; } cout<<endl; } int main() { BTNode *bt = NULL; //124##57##8##3#69### createBinaryTree(bt); preOrderRecursionVisit(bt); cout<<endl; preOrderNonRecursionVisit(bt); inOrderRecursionVisit(bt); cout<<endl; inOrderNonRecursionVisit(bt); postOrderRecursionVisit(bt); cout<<endl; postOrderNonRecursionVisit(bt); }
还没有评论，来说两句吧...