1.实验题目
1.【功能1】按先序次序建立一棵二叉树，以‘＃’表示空。
2.【功能2】中序遍历二叉树，输出遍历序列。
3.【功能3】后序遍历二叉树，输出遍历序列。
4.【功能4】求出二叉树的深度并输出。
5.【功能5】求出二叉树的叶子数目并输出。
6.【功能6】以栈为辅助存储结构实现二叉树的先序非递归算法，输出二叉树的先序非递归遍历序列。
7.【功能7】以队列为辅助存储结构实现二叉树的层次遍历算法，输出二叉树的层次遍历序列。
8.【功能8】以栈为辅助存储结构实现二叉树的中序非递归算法，输出二叉树的中序非递归遍历序列。
2.实验要求
1、二叉树以二叉链表为存储结构。
2、主程序测试数据
(1)输入以下字符串，先序建立二叉树：ABC##DE#G##F###
(2)输出中序遍历序列应为：CBEGDFA
(3)输出后序遍历序列应为：CGEFDBA
(4)输出二叉树的深度应为：5
(5)输出二叉树的叶子数目应为：3
(6)输出二叉树的先序非递归遍历序列应为：ABCDEGF
(7)输出二叉树的层次遍历序列应为：ABCDEFG
(8)输出二叉树的中序非递归遍历序列应为：CBEGDFA
2、可以在教材定义的基础上，增加你的算法为成员函数。
3.算法思路
1.按先序次序建立一棵二叉树，以‘＃’表示空
利用递归的办法。
首先建立一个根结点。
函数开始时，先检测数据。若数据为#号，则使其左子树和右子树为空。若该数据为正常的字符，则生成左结点和右结点。
输入下一个数据，并以该数据递归地生成左子树。在左子树构建完毕后再输入数据，以该数据递归地生成右子树。至此，以先序次序建立的二叉树完成了。
这样的二叉树有这样几种结点：根结点：可以直接被getroot访问。无效的结点：数据域为#，指针域为空。数据结点：数据域记录了真实数据。但其指针域不为空，可能指向另一个数据结点，也可能指向无效的结点。
4.求二叉树的深度
利用递归的办法。
求子二叉树的深度。在双亲结点上，取最深的子二叉树的深度值，并+1，可得以该结点构建的子二叉树的深度。在叶结点上，二叉树深度值为1.
5.求出二叉树的叶子数目
定义一个属性记录二叉树的叶子数目。利用递归先序遍历的办法。
正常的先序遍历中我们需要访问结点并输出数值。但是，在求叶子结点的过程中，我们只需判断该结点是否为叶子结点。若该结点的左右结点的数据域均为#，则说明该结点就是叶子结点。
6.二叉树的非递归先序遍历
利用栈作为辅助存储结构，实现二叉树的非递归先序遍历。
定义一个栈，并将根结点入栈。定义一个指针。当栈非空且指针指向不为空时，进行循环：先不断访问左结点，并将每个访问到的结点入栈，直到访问到空结点。此时，若栈非空，取栈顶并访问其右结点。将该过程循环，就可以实现二叉树的非递归先序遍历。
8.二叉树的非递归中序遍历
利用栈作为辅助存储结构，实现二叉树的非递归中序遍历。
定义一个栈，并将根结点入栈。定义一个指针。当栈非空且指针指向不为空时，进行循环：先不断访问左结点，并将每个访问到的结点入栈，直到访问到空结点。此时，若找到空结点，将该结点出栈。取栈顶元素，访问其右结点。
3.功能演示
4.总结
附录：源代码
bintree.h
#pragma once #include"bintreenode.h" #include"stack.h" #include"queue.h" #include<iostream> #include<Windows.h> using namespace std; template<class elemtype> class bintree { private: bintreenode<elemtype>* root; mutable int leafnum; mutable int height; public: int getleafnum() { return leafnum; } bintreenode<elemtype>* getroot() { return this->root; } bintree() { root = new bintreenode<elemtype>(); leafnum = 0; height = 0; } void generatebintree(elemtype ch,bintreenode<elemtype> *n) { n->data = ch; if (ch == '#') { n->leftchild = NULL; n->rightchild = NULL; return; }//数据域为#，则没有孩子 n->leftchild = new bintreenode<elemtype>(NULL, NULL, NULL);//数据域不为#，则正常构建孩子结点 n->rightchild = new bintreenode<elemtype>(NULL, NULL, NULL);//构建孩子结点 elemtype newch; cin >> newch; generatebintree(newch, n->leftchild);//先根据数据构建左子树 cin >> newch; generatebintree(newch, n->rightchild);//再根据数据构建右子树 return; } void inorder(bintreenode<elemtype>* r) const { if (r != NULL) { inorder(r->leftchild); if(r->data!='#') cout << r->data; inorder(r->rightchild); } return; } void postorder(bintreenode<elemtype>* r) const { if (r != NULL) { postorder(r->leftchild); postorder(r->rightchild); if(r->data!='#') cout << r->data; } return; } ~bintree() { deletetree(root);//析构函数 } void deletetree(bintreenode<elemtype>* r) { if (r != NULL) { deletetree(r->leftchild); deletetree(r->rightchild); delete r;//后序遍历的办法delete树 } return; } void countleaf(bintreenode<elemtype>* r) const { if (r->data == '#') return; if (r->leftchild->data == '#' && r->rightchild->data == '#') { leafnum++;//如果左右结点都是#，则说明这个结点就是叶结点 return; } if (r != NULL) { countleaf(r->leftchild); countleaf(r->rightchild);//不是叶节点，则递归的计算 } } int countheight(bintreenode<elemtype>* r) const { if (r->data == '#' ) return 0;//空结点不算深度 else return max(countheight(r->leftchild), countheight(r->rightchild)) + 1;//选最深的子树，深度+1 } void stackpreorder() const { stack<bintreenode<elemtype>* > nodestack(100); bintreenode<elemtype>* p=root; while (!nodestack.isempty() || p != NULL) {//当栈非空，p不指向空结点时，继续循环 while (p != NULL) { if (p->data != '#') cout << p->data; nodestack.push(p);//将其入栈 p = p->leftchild;//找到最左的结点 } if (!nodestack.isempty()) { p = nodestack.gettop();//取栈顶，访问栈顶的右子树 nodestack.pop(p); p = p->rightchild; } } } void levelorder() const {//层次遍历 queue<bintreenode<elemtype>*> nodequeue; bintreenode<elemtype>* p; if (root != NULL) nodequeue.enqueue(root); while (!nodequeue.isempty()) {//当队列非空时，继续运行 nodequeue.delqueue(p);//将队头出队 if (p->data != '#') cout << p->data; if (p->leftchild != NULL) nodequeue.enqueue(p->leftchild);//将p左结点入队 if (p->rightchild != NULL) nodequeue.enqueue(p->rightchild);//将p右结点入队 } } void stackinorder()const {//非递归中序遍历 stack<bintreenode<elemtype>*> nodestack; bintreenode<elemtype>* p=root; while (!nodestack.isempty()||p->data!='#') { if (p->data != '#') { nodestack.push(p); p = p->leftchild;//找到最左结点，不断将访问到的结点入栈 } else { nodestack.pop(p);//栈顶出栈，访问右子树 if (p->data != '#') cout << p->data; p = p->rightchild; } } } };
bintreenode.h
#pragma once #include<Windows.h> template<class elemtype> struct bintreenode { public: elemtype data; bintreenode<elemtype>* leftchild; bintreenode<elemtype>* rightchild; bintreenode() { leftchild = NULL; rightchild = NULL; data = NULL; } bintreenode(const elemtype& d, bintreenode<elemtype>* l = NULL, bintreenode<elemtype>* r = NULL) { data = d; leftchild = l; rightchild = r; } };
queue.h
#pragma once #define status int #define SUCCESS 1 #define ERROR 0 #include<Windows.h> template <class elemtype> class queue { protected: int front, rear; int maxsize; elemtype* elems; public: queue(int size=100) { maxsize = size; if (elems != NULL) delete[]elems; elems = new elemtype[maxsize]; rear = front = 0; } ~queue() { delete[]elems; } status enqueue(const elemtype& e) { if ((rear + 1) % maxsize == front) return ERROR; else { elems[rear]= e; rear = (rear + 1) % maxsize; return SUCCESS; } } status delqueue(elemtype& e) { if (!isempty()) { e = elems[front]; front = (front + 1) % maxsize; return SUCCESS; } else return 0; } bool isempty() { return rear == front; }
stack.h
#pragma once #define status int #define ERROR 0 #define SUCCESS 1 #include<Windows.h> template <typename elemtype> class stack { private: int top; int maxsize; elemtype* elems; public: stack(int size = 100) { top = -1; maxsize = size; elems = new elemtype[maxsize]; } ~stack(){ delete []elems; } status push(const elemtype e){ if (top == maxsize) return ERROR; else elems[++top] = e; return SUCCESS; } status pop(elemtype &e){ if (top == -1) return ERROR; else e = elems[top--]; return SUCCESS; } elemtype gettop() { if (isempty()) return NULL; else return elems[top]; } bool isempty(){ return (top == -1); } };
main.cpp
#include<iostream> #include"bintree.h" #include"bintreenode.h" using namespace std; int main() { bintree<char> tree; // tree.root = new bintreenode<char>(); char ch; cout << "请输入你的树:"; cin >> ch; tree.generatebintree(ch, tree.getroot()); cout << "中序遍历："; tree.inorder(tree.getroot()); cout << endl; cout << "后序遍历："; tree.postorder(tree.getroot()); tree.countleaf(tree.getroot()); cout << endl; cout << "叶结点数目"<<tree.getleafnum()<<endl; cout << "二叉树深度：" << tree.countheight(tree.getroot())<< endl; cout << "非递归先序遍历"; tree.stackpreorder(); cout << endl; cout << "非递归层次遍历:"; tree.levelorder(); cout << endl; cout << "非递归中序遍历"; tree.stackinorder(); cout << endl; cout << "运行结束"; }
