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 << "运行结束";
}

数据结构/数据结构与算法实验二二叉树相关算法实现

1.实验题目

2.实验要求

3.算法思路

1.按先序次序建立一棵二叉树，以‘＃’表示空

4.求二叉树的深度

5.求出二叉树的叶子数目

6.二叉树的非递归先序遍历

8.二叉树的非递归中序遍历

3.功能演示

4.总结

附录：源代码

bintree.h

bintreenode.h

queue.h

stack.h

main.cpp

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构/数据结构与算法实验二 二叉树相关算法实现

1.实验题目

2.实验要求

3.算法思路

1.按先序次序建立一棵二叉树，以‘＃’表示空

4.求二叉树的深度

5.求出二叉树的叶子数目

6.二叉树的非递归先序遍历

8.二叉树的非递归中序遍历

3.功能演示

4.总结

附录：源代码

bintree.h

bintreenode.h

queue.h

stack.h

main.cpp

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构/数据结构与算法实验二二叉树相关算法实现