{
recursive_insert(root, x);
}
template<classEntry>
voidBinary_tree<Entry> ::recursive_insert(Binary_node<Entry> * &sub_root,constEntry &x)
/* Pre: sub_root is either NULL or points to a subtree of the Binary_tree.
void MidOrder(tree *b2)//中序遍历函数
void LastOrder(tree *b3)//后序遍历函数
数据结构：给出所使用的基本抽象数据类型，所定义的具体问题的数据类型，以及新定义的抽象数据类型。
源程序：
cpp1.cpp
typedefcharEntry;
template<classEntry>
};
cpp2.cpp
#include"cpp1.cpp"
#include<iostream>
usingnamespacestd;
template<classEntry>
intBinary_tree<Entry> :: height()const
/* Post: The height of the binary tree is returned. */
intsize()const;
voidclear();
intheight()const;
voidinsert(constEntry &);
Binary_tree (constBinary_tree<Entry> &original);
Binary_tree &operator=(constBinary_tree<Entry> &original);
}
template<classEntry>
boolBinary_tree<Entry>::empty()const
/*
Post: A result of true is returned if the binary tree is empty.
Otherwise, false is returned.
*/
{
recursive_inorder(root, visit);
}
template<classEntry>
voidBinary_tree<Entry>::recursive_inorder(Binary_node<Entry> *sub_root,
void(*visit)(Entry &))
/*
重庆大学本科学生课程设计任务书
课程设计题目
二叉树的建立与遍历
学院
软件学院
专业
软件工程
年级
09级
问题描述:
建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。
基本要求：
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。
2.基本运算
void push(stack **top,tree *tree)//树结点入栈
void pop(stack **top,tree **T) //出栈，栈内元素赋值
void getTop(stack*s,tree **t)//获取栈顶元素
3.递归遍历函数
void PreOrder(tree *b1)//前序遍历函数
算法思想：
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
（1）访问结点本身(N)
（2）遍历该结点的左子树(L)
（3）遍历该结点的右子树(R)
以上三种操作有六种执行次序： NLR、LNR、LRN、NRL、RNL、RLN。前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。
else
recursive_insert(sub_root->left, x);
}
template<classEntry>
Binary_tree<Entry>::Binary_tree()
/*
Post: An empty binary tree has been created.
*/
{
root=0;
Pre: sub_root is either NULL or points to a subtree of the Binary_tree.
Post: The subtree has been traversed in inorder sequence.
Uses: The function recursive_inorder recursively
/*
Post: The tree has been traversed in inorder sequence.
Uses: The function recursive_inorder
*/
{
recursive_postorder(root, visit);
}
template<classEntry>
voidBinary_tree<Entry>::recursive_postorder(Binary_node<Entry> *sub_root,
*/
{
returnroot==0;
}
template<classEntry>
voidBinary_tree<Entry>::inorder(void(*visit)(Entry &))
/*
Post: The tree has been traversed in inorder sequence.
Uses: The function recursive_inorder
Post: The subtree has been traversed in preorder sequence.
Uses: The function recursive_preorder recursively
*/
{
if(sub_root != 0) {
(*visit)(sub_root->data);
{
returnrecursive_height(root);
}
template<classEntry>
intBinary_tree<Entry>::recursive_height(Binary_node<Entry> *sub_root)const
/* Post: The height of the subtree rooted at sub_root is returned. */
voidrecursive_postorder(Binary_node<Entry> *sub_root,void(*visit)(Entry &));
voidrecursive_preorder(Binary_node<Entry> *sub_root,void(*visit)(Entry &));
Post: The Entry x has been inserted into the subtree in such a way that the properties of a
binary search tree have been preserved.
Uses: The functions recursive_insert, recursive_height */
Binary_node<Entry>::Binary_node(constEntry &x)
{
data=x;
left=0;
right=0;
}
template<classEntry>
voidBinary_tree<Entry>::insert(constEntry &x)
/* Post: The Entry x is added to the binary tree. */
{
if(sub_root==0)
sub_root=newBinary_node<Entry>(x);
else
if(recursive_height(sub_root->right)<recursive_height(sub_root->left))
recursive_insert(sub_root->right, x);
*/
{
if(sub_root != 0) {
recursive_inorder(sub_root->left, visit);
(*visit)(sub_root->data);
recursive_inorder(sub_root->right, visit);
}
}
template<classEntry>
recursive_preorder(sub_root->left, visit);
recursive_preorder(sub_root->right, visit);
}
}