数据结构入门----二叉树的应用

一. 实验要求 实现二叉树创建算法，在此基础上实现二叉树的先序、后序递归遍历算法、两种非递归中序遍历、层序遍历、求二叉树的深度。注意：在非递归算法中用到栈和队列时，不要调用系统的栈和队列，需要自己实现栈和队列的操作。 二. 实验目的 通过该实验，理解二叉树的链式存储，掌握二叉树的几种遍历算法，并理解递归的含义，掌握C语言编写递归函数的方法和注意事项。 三. 设计思想 1.首先进行先序创建二叉树。从键盘输入字符c，如果c是‘$’则说明该结点是空；否则，为该结点申请一个空间，让数据data等于c，接着利用递归函数创造这个数据c的左孩子和右兄弟。直到没有左右子树可继续递归为止。 2.先序遍历二叉树。如果结点为空，则不输出；否则，输出结点T的数据data。利用递归思想，继续先序遍历结点T的左子树和右子树，直到遍历完为止。 3.后序遍历二叉树。如果结点为空，则不输出；否则，先递归遍历结点T的左子树和右子树，再输出结点T的data值。 4.中序遍历二叉树1。先申请一个栈S，一个栈顶元素指针top，将根结点T先入栈。当栈S不空时，进行while循环：如果栈不为空且结点不为空时，将栈顶元素data值结点的左孩子入栈；否则，让top指向的栈顶元素出栈，输出栈顶元素的data值，并将栈顶元素的右子树入栈。直到栈为空时，结束遍历。 5.中序遍历二叉树2。先申请一个栈S，一个指针p指向遍历的结点T，一个指针top指向栈顶元素的后一个位置。当指针p不指向空并且栈S存在时，进行while循环：如果指针p存在，将指针p所指向的结点值data入栈，让p指向原位置的左孩子；否则，将栈S中的栈顶元素出栈，输出栈顶元素的data值，并让p指向栈顶元素的右孩子。直到栈为空，结束遍历。 6.层序遍历二叉树。申请一个队列Q，一个指针top指像队头元素。将根结点T入队，当队列Q不为空时，进行while循环：当根结点出队后，令其左、右孩子结点入队（空不入队），而左孩子出队时又令它的左右孩子结点入队，……由此便可产生按层次输出的效果。 7.求二叉树的深度。如果T为空树，返回0；否则，利用High函数递归计算根结点T的左子树和右子树的深度，取最大值。 四. 主要源代码

#include "iostream" using namespace std; #define INITIAL 10000 typedef struct Node { char data; Node *left_child, *right_child; }*Bitree,Node; struct Stack { Bitree *base,*top; int length; }; struct Node_q{ Node* data; Node_q* next; }; struct Queue{ Node_q *front,*rear; }; void print(); int max(int a,int b) { if(a>b) { return a; } else { return b; } } void Create(Bitree &T) { char c; cin>>c; if (c == '$') //这个是什么意思？？看不懂 { T = NULL; } else { T = (Bitree)malloc(sizeof(Node)); T->data = c; Create(T->left_child); Create(T->right_child); } } void dlr(Bitree &T) { if(!T) { return; } cout<<T->data<<" "; dlr(T->left_child); dlr(T->right_child); } void lrd(Bitree &T) { if(!T) { return; } lrd(T->left_child); lrd(T->right_child); cout<<T->data<<" "; } void Init(Stack &S) { S.base=(Bitree*)malloc(INITIAL*sizeof(Bitree)); S.top=S.base; S.length=INITIAL; } void Push(Stack &S,Node* e) { if (S.top-S.base>=S.length) { S.top=(Bitree*)realloc(S.base,(S.length+10)*sizeof(Bitree)); S.top=S.base+S.length; S.length+=10; } *S.top=e; S.top++; } int Empty(Stack &S) { if(S.top==S.base) { return true; } else { return false; } } int Pop(Stack &S, Node* &e) { if(Empty(S)) { return -1; } S.top--; e=*S.top; return true; } int Top(Stack S, Node* &e) { if (Empty(S)) { return -1; } e=*(S.top-1); return true; } void ldr_1(Bitree T) { Stack S; Node* top; Init(S); Push(S, T); while(!Empty(S)) { if((Top(S, top) != -1) && top) { Push(S,top->left_child); } else { Pop(S, top); if(!Empty(S)) { Pop(S, top); cout<<top->data<<endl; Push(S,top->right_child); } } } puts(""); } void ldr_2(Bitree T) { Stack S; Init(S); Node *p=T,*top; while (p || !Empty(S)) { if (p) { Push(S, p); p=p->left_child; } else { Pop(S, top); cout<<top->data<<endl; p = top->right_child; } } puts(""); } void Init(Queue &Q) { Q.front = Q.rear = (Node_q*)malloc(sizeof(Node_q)); Q.front->next = Q.rear->next = NULL; } int Empty(Queue Q) { if (Q.front == Q.rear) { return true; } else { return false; } } int Top(Queue Q, Node* &e) { if (Empty(Q)) { return -1; } e = Q.front->next->data; return true; } int Push(Queue &Q, Node* e) { Node_q *p = (Node_q*)malloc(sizeof(Node_q)); p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return true; } int Pop(Queue &Q, Node* &e) { if (Empty(Q)) { return -1; } Node_q *p = Q.front->next; e = p->data; Q.front->next = p->next; if (p == Q.rear) { Q.rear = Q.front; } free(p); return true; } void Level(Bitree T) { Queue Q; Init(Q); Push(Q, T); Node *top; while(!Empty(Q)) { Pop(Q, top); if (!top) { continue; } cout<<top->data<<endl; Push(Q, top->left_child); Push(Q, top->right_child); } puts(""); } int High(Bitree T) { if(!T) { return 0; } return max(High(T->left_child), High(T->right_child)) + 1; } int main() { print(); int t; cin>>t; Bitree T; while (cin >> t) { if (t == 8) { break; } switch(t) { case 1: // 创建 { getchar(); Create(T); break; } case 2: // 先序 { printf("先序: "); dlr(T); puts(""); break; } case 3: // 中序1 { printf("中序1: "); ldr_1(T); break; } case 4: // 中序2 { printf("中序2: "); ldr_2(T); break; } case 5: // 后序 { printf("后序: "); lrd(T); puts(""); break; } case 6: // 层序 { printf("层序: "); Level(T); break; } case 7: // 深度 { printf("深度: %d\n", High(T)); break; } default: { printf("输入序号错误! "); break; } } cout << "请输入你的选择："; } return 0; } void print() { cout << "**************************************************************\n"; cout << "****************** 1.创建二叉树 ******************\n"; cout << "****************** 2.先序遍历二叉树 ******************\n"; cout << "****************** 3.中序遍历二叉树1 ******************\n"; cout << "****************** 4.中序遍历二叉树2 ******************\n"; cout << "****************** 5.后序遍历二叉树 ******************\n"; cout << "****************** 6.层序遍历二叉树 ******************\n"; cout << "****************** 7.求二叉树的深度 ******************\n"; cout << "****************** 8.退出 ******************\n"; cout << "**************************************************************\n"; cout << "请输入你的选择："; }

五. 调试与测试数据