C++ 数据库二叉树的实现

一、实验目的 1.掌握构造二叉链表树的算法。 2.掌握遍历二叉树的四种（先序、中序、后序、层序）算法（递归和非递归）算法。 3.掌握基于先序遍历构造二叉链表的算法。 4.掌握计算二叉树的结点个数、二叉树的深度、二叉树的叶子结点和二叉树复制算法。 二、实验内容 1、构造基于先序遍历的二叉链表。 要求：按先序遍历规则，从键盘连续输入二叉树的先序序列，若无孩子结点，则用#代替，以示空指针的位置；然后调用构造二叉链表的递归算法，从屏幕显示该二叉链表的先序序列。 2、分别调用先序、中序、后序遍历算法对前面建立好的二叉链表树进行遍历。要求分别显示遍历后的结点序列。（递归和非递归） 3、调用计算二叉树的结点总数、深度、叶子节点个数算法，统计上述二叉链表树的结点总数、深度、叶子节点总数，从屏幕显示。 4、编写按照层次遍历二叉树的算法，并显示遍历后的结点序列。（利用队列） 5、编写算法判定给定二叉树是否为完全二叉树。 6、编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。