题目描述

已知二叉链表类，请实现二叉树的先序、中序、后序递归遍历。
//OJ-1020 binary tree(1)
#include
#include
using namespace std;
//二叉树类，实现二叉树的递归算法：三种遍历
template
struct BiNode //二叉树的结点结构
{
DataType data;
BiNode lchild, rchild;
};
template
class BiTree{
public:
BiTree(); //构造函数，初始化一棵二叉树，其前序序列由键盘输入
~BiTree(); //析构函数，释放二叉链表中各结点的存储空间
void PreOrder(void); //调用私有的递归函数PerOrder
void InOrder(void);
void PostOrder(void);
private:
BiNode root; //指向根结点的头指针
void Creat(BiNode &bt);//被构造函数调用，递归方式生成二叉树
void Release(BiNode &bt); //被析构函数调用
void PreOrder(BiNode bt); //前序遍历二叉树
void InOrder(BiNode bt); //中序遍历二叉树
void PostOrder(BiNode bt); //后序遍历二叉树
};
//定义类中的成员函数
//构造函数:Creat利用创建二叉树
template
BiTree::BiTree()
{
Creat(root);
}
//功 能：递归方法创建一棵二叉树,由构造函数调用
template
void BiTree::Creat(BiNode &bt)
{
DataType ch;
cin>>ch;
if (ch==”#”) bt = nullptr; //创建结点值为字符串的二叉树
else{
bt = new BiNode; //生成一个结点
bt->data=ch;
Creat(bt->lchild); //递归建立左子树
Creat(bt->rchild); //递归建立右子树
}
}
//功 能：析构函数，释放二叉链表中各结点的存储空间
template
BiTree::~BiTree() //析构函数不能带参数
{
Release(root);
}
//功 能：释放二叉树的存储空间，析构函数调用
template
void BiTree::Release(BiNode&bt)
{
if (bt != nullptr){
Release(bt->lchild); //释放左子树
Release(bt->rchild); //释放右子树
delete bt;
}
}
template
void BiTree::PreOrder(void)
{
PreOrder(root);
}
template
void BiTree::InOrder(void)
{
InOrder(root);
}
template
void BiTree::PostOrder(void)
{
PostOrder(root);
}
//请在下面补充实现二叉树的三种递归遍历算法

int main()
{
BiTree mybit;
mybit.PreOrder();
cout<mybit.InOrder();
cout<mybit.PostOrder();
cout<return 0;
}

输入

输出

样例输入

Li Sun # Zhao Zhou # # Wang # # Qian # #

样例输出

Li Sun Zhao Zhou Wang Qian Sun Zhou Zhao Wang Li Qian Zhou Wang Zhao Sun Qian Li

提示

来源

提交

  1. import java.util.Scanner;
  3. class Node {
  4.     public Object data;
  5.     public Node next;
  7.     public Node() {
  8.         this(null,null);
  9.     }
  11.     public Node(Object data) {
  12.         this(data,null);
  13.     }
  15.     public Node(Object data, Node next) {
  16.         this.data = data;
  17.         this.next = next;
  18.     }
  19. }
  20. class LinkStack{
  21.     private Node top; // 栈顶元素的引用
  23.     // 将一个已经存在的栈置成空
  24.     public void clear() {
  25.         top = null;
  26.     }
  28.     // 测试栈是否为空
  29.     public boolean isEmpty() {
  30.         return top == null;
  31.     }
  33.     // 求栈中的数据元素个数并由函数返回其值
  34.     public int length() {
  35.         Node p = top;// 初始化,p指向栈顶结点,length为计数器
  36.         int length = 0;
  37.         while (p != null) {// 从栈顶结点向后查找，直到p指向栈顶结点
  38.             p = p.next;// 指向后继结点
  39.             ++length;// 长度增1
  40.         }
  41.         return length;
  42.     }
  44.     // 查看栈顶对象而不移除它，返回栈顶对象
  45.     public Object peek() {
  46.         if (!isEmpty())
  47.             return top.data;// 返回栈顶元素
  48.         else
  49.             return null;
  50.     }
  52.     // 移除栈顶对象并作为此函数的值返回该对象
  53.     public Object pop() {
  54.         if (!isEmpty()) {
  55.             Node p = top;// p指向栈顶结点
  56.             top = top.next;
  57.             return p.data;
  58.         } else
  59.             return null;
  60.     }
  62.     // 把项压入栈顶
  63.     public void push(Object x) {
  64.         Node p = new Node(x); // 构造一个新的结点
  65.         p.next=top;
  66.         top = p;// 改变栈顶结点
  67.     }
  69.     // 打印函数，打印所有栈中的元素(栈顶到栈底)
  70.     public void display() {
  71.         Node p = top; // p指向栈顶结点，q指向p的下一结点
  72.         while (p != null) {// 打印所有非空的结点
  73.             System.out.print((p.data.toString() + " ")); // 打印
  74.             p = p.next;// 指向p下一元素
  75.         }
  76.     }
  77. }
  79. class LinkQueue{
  80.     private Node front;
  82.     private Node rear;
  85.     public LinkQueue() {
  86.         front = rear = null;
  87.     }
  90.     public void clear() {
  91.         front = rear = null;
  93.     }
  96.     public boolean isEmpty() {
  97.         return front == null;
  98.     }
  100.     public int length() {
  101.         Node p = front;
  102.         int length = 0;
  103.         while (p != null) {
  104.             p = p.next;
  105.             ++length;
  106.         }
  107.         return length;
  108.     }
  111.     public void offer(Object o) {
  112.         Node p = new Node(o);
  113.         if (front != null) {
  114.             rear.next=p;
  115.             rear = p;
  116.         } else
  118.             front = rear = p;
  119.     }
  121.     public Object peek() {
  122.         if (front != null) 
  123.             return front.data;
  124.         else
  125.             return null;
  126.     }
  128.     public Object poll() {
  129.         if (front != null) {
  130.             Node p = front;
  131.             front = front.next;
  132.             if (p==rear)
  133.                 rear=null;
  134.             return p.data;
  135.         } else
  136.             return null;
  137.     }
  140.     public void display() {
  141.         if (!isEmpty()) {
  142.             Node p = front;
  143.             while (p != rear.next) {
  144.                 System.out.print(p.data.toString() + " ");
  145.                 p = p.next;
  146.             }
  147.         } else {
  148.             System.out.println("此队列为空");
  149.         }
  150.     }
  152. }
  154. class BiTreeNode {
  155.     public Object data;// 结点的数据元素
  157.     public BiTreeNode lchild, rchild; // 左右孩子
  159.     public BiTreeNode() {// 构造一个空结点
  160.         this(null);
  161.     }
  163.     public BiTreeNode(Object data) {// 构造一棵左右孩子为空的结点
  164.         this(data, null, null);
  165.     }
  167.     public BiTreeNode(Object data, BiTreeNode lchild, BiTreeNode rchild) {// 构造一棵数据元素和左右孩子都不为空的结点
  168.         this.data = data;
  169.         this.lchild = lchild;
  170.         this.rchild = rchild;
  171.     }
  174. }
  177. class BiTree {
  179.     private BiTreeNode root;// 树的根结点
  181.     public BiTree() {// 构造一棵空树
  182.         this.root = null;
  183.     }
  185.     public BiTree(BiTreeNode root) {// 构造一棵树
  186.         this.root = root;
  187.     }
  189.     // 由先根遍历的数组和中根遍历的数组建立一棵二叉树
  190.     // 其中参数preOrder是整棵树的 先根遍历，inOrder是整棵树的中根遍历，preIndex是
  191.     // 先根遍历从preOrder字符串中的开始位置，inIndex是中根遍历从字符串inOrder中的开始位置，count表示树结点的个数
  192.     public BiTree(String preOrder, String inOrder, int preIndex, int inIndex,
  193.             int count) {
  194.         if (count > 0) {// 先根和中根非空
  195.             char r = preOrder.charAt(preIndex);// 取先根字符串中的第一个元素作为根结点
  196.             int i = 0;
  197.             for (; i < count; i++)
  198.                 // 寻找根结点在中根遍历字符串中的索引
  199.                 if (r == inOrder.charAt(i + inIndex))
  200.                     break;
  202.             root = new BiTreeNode(r);// 建立树的根结点
  203.             root.lchild=new BiTree(preOrder, inOrder, preIndex + 1, inIndex,
  204.                     i).root;// 建立树的左子树
  205.             root.rchild=new BiTree(preOrder, inOrder, preIndex + i + 1,
  206.                     inIndex + i + 1, count - i - 1).root;// 建立树的右子树
  207.         }
  208.     }
  210.     // 由标明空子树的先根遍历序列建立一棵二叉树
  211.     private static int index = 0;// 用于记录preStr的索引值
  213.     public BiTree(String[] preStr) {
  214.         String c = preStr[index++];// 取出字符串索引为index的字符，且index增1
  215.         if (!c.equals("#") ) {// 字符不为#
  216.             root = new BiTreeNode(c);// 建立树的根结点
  217.             root.lchild=new BiTree(preStr).root;// 建立树的左子树
  218.             root.rchild=new BiTree(preStr).root;// 建立树的右子树
  219.         } else
  220.             root = null;
  221.     }
  223.     // 先根遍历二叉树基本操作的递归算法
  224.     public void preRootTraverse(BiTreeNode T) {
  225.         if (T != null) {
  226.             System.out.print(T.data); // 访问根结点
  227.             preRootTraverse(T.lchild);// 访问左子树
  228.             preRootTraverse(T.rchild);// 访问右子树
  229.         }
  230.     }
  232.     // 先根遍历二叉树基本操作的非递归算法
  233.     public void preRootTraverse() {
  234.         BiTreeNode T = root;
  235.         if (T != null) {
  236.             LinkStack S = new LinkStack();// 构造栈
  237.             S.push(T);// 根结点入栈
  238.             while (!S.isEmpty()) {
  239.                 T = (BiTreeNode) S.pop();// 移除栈顶结点，并返回其值
  240.                 System.out.print(T.data +" "); // 访问结点
  241.                 while (T != null) {
  242.                     if (T.lchild != null) // 访问左孩子
  243.                         System.out.print(T.lchild.data +" "); // 访问结点
  245.                     if (T.rchild != null)// 右孩子非空入栈
  246.                         S.push(T.rchild);
  248.                     T = T.lchild;
  249.                 }
  250.             }
  251.         }
  252.     }
  254.     // 中根遍历二叉树基本操作的递归算法
  255.     public void inRootTraverse(BiTreeNode T) {
  256.         if (T != null) {
  257.             inRootTraverse(T.lchild);// 访问左子树
  258.             System.out.print(T.data); // 访问根结点
  259.             inRootTraverse(T.rchild);// 访问右子树
  260.         }
  261.     }
  263.     // 中根遍历二叉树基本操作的非递归算法
  264.     public void inRootTraverse() {
  265.         BiTreeNode T = root;
  266.         if (T != null) {
  267.             LinkStack S = new LinkStack();// 构造链栈
  268.             S.push(T); // 根结点入栈
  269.             while (!S.isEmpty()) {
  270.                 while (S.peek() != null)
  271.                     // 将栈顶结点的所有左孩子结点入栈
  272.                     S.push(((BiTreeNode) S.peek()).lchild);
  273.                 S.pop(); // 空结点退栈
  274.                 if (!S.isEmpty()) {
  275.                     T = (BiTreeNode) S.pop();// 移除栈顶结点，并返回其值
  276.                     System.out.print(T.data +" "); // 访问结点
  277.                     S.push(T.rchild);// 结点的右孩子入栈
  278.                 }
  279.             }
  280.         }
  281.     }
  283.     // 后根遍历二叉树基本操作的递归算法
  284.     public void postRootTraverse(BiTreeNode T) {
  285.         if (T != null) {
  286.             postRootTraverse(T.lchild);// 访问左子树
  287.             postRootTraverse(T.rchild);// 访问右子树
  288.             System.out.print(T.data); // 访问根结点
  289.         }
  290.     }
  292.     // 后根遍历二叉树基本操作的非递归算法
  293.     public void postRootTraverse() {
  294.         BiTreeNode T = root;
  295.         if (T != null) {
  296.             LinkStack S = new LinkStack();// 构造链栈
  297.             S.push(T); // 根结点进栈
  298.             Boolean flag;// 访问标记
  299.             BiTreeNode p = null;// p指向刚被访问的结点
  300.             while (!S.isEmpty()) {
  301.                 while (S.peek() != null)
  302.                     // 将栈顶结点的所有左孩子结点入栈
  303.                     S.push(((BiTreeNode) S.peek()).lchild);
  304.                 S.pop(); // 空结点退栈
  305.                 while (!S.isEmpty()) {
  306.                     T = (BiTreeNode) S.peek();// 查看栈顶元素
  307.                     if (T.rchild == null || T.rchild == p) {
  308.                         System.out.print(T.data +" "); // 访问结点
  309.                         S.pop();// 移除栈顶元素
  310.                         p = T;// p指向刚被访问的结点
  311.                         flag = true;// 设置访问标记
  312.                     } else {
  313.                         S.push(T.rchild);// 右孩子结点入栈
  314.                         flag = false;// 设置未被访问标记
  315.                     }
  316.                     if (!flag)
  317.                         break;
  318.                 }
  319.             }
  320.         }
  321.     }
  323.     // 层次遍历二叉树基本操作的算法(自左向右)
  324.     public void levelTraverse() {
  325.         BiTreeNode T = root;
  326.         if (T != null) {
  327.             LinkQueue L = new LinkQueue();// 构造队列
  328.             L.offer(T);// 根结点入队列
  329.             while (!L.isEmpty()) {
  330.                 T = (BiTreeNode) L.poll();
  331.                 System.out.print(T.data); // 访问结点
  332.                 if (T.lchild != null)// 左孩子非空，入队列
  333.                     L.offer(T.lchild);
  334.                 if (T.rchild != null)// 右孩子非空，入队列
  335.                     L.offer(T.rchild);
  336.             }
  337.         }
  339.     }
  341.     public BiTreeNode getRoot() {
  342.         return root;
  343.     }
  345.     public void setRoot(BiTreeNode root) {
  346.         this.root = root;
  347.     }
  349.     // 统计叶结点数目
  350.     public int countLeafNode(BiTreeNode T) {
  351.         int count = 0;
  352.         if (T != null) {
  353.             if (T.lchild == null && T.rchild == null) {
  354.                 ++count;// 叶结点个数加1
  355.             } else {
  356.                 count += countLeafNode(T.lchild); // 加上左子树上叶结点的个数
  357.                 count += countLeafNode(T.rchild);// 加上右子树上叶结点的个数
  358.             }
  359.         }
  360.         return count;
  361.     }
  363.     // 统计结点的数目
  364.     public int countNode(BiTreeNode T) {
  365.         int count = 0;
  366.         if (T != null) {
  367.             ++count;// 结点的个数加1
  368.             count += countNode(T.lchild); // 加上左子树上结点的个数
  369.             count += countNode(T.rchild);// 加上右子树上结点的个数
  370.         }
  371.         return count;
  372.     }
  374. }
  376. public class Main {
  378.     public static void main(String[] args) {
  379.         // TODO Auto-generated method stub
  380.         Scanner scanner = new Scanner(System.in);
  381.         String s = scanner.nextLine();
  382.         String[] ss = s.split(" ");
  383.         BiTree b = new BiTree(ss);
  384.         b.preRootTraverse();
  385.         System.out.println();
  386.         b.inRootTraverse();
  387.         System.out.println();
  388.         b.postRootTraverse();
  390.     }
  391. }