以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。

设二叉树以二叉链表为存储结构，编写一个后序遍历二叉树的非递归算法(要求先用文字写出实现的基本思想，再用C语言写出算法)。【中国海洋大学2006八(15分)】

假设以带双亲指针的二叉链表作为-二叉树的存储结构，其结点结构的类型说明如下所示：

typedef char DataType;

typedef struct node{

DataType data;

struct node*lchild,*rchild; //左右孩子指针

struct node*parent; //指向双亲的指针

}BinTNode;

typedef BinTNode*BinTree;

若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。

1. 就后继的不同情况，简要叙述实现求后继操作的方法；

以二叉链表作为二叉树的存储结构，编写以下算法：

(1)统计二叉树的叶结点个数。

(2)设计二叉树的双序遍历算法(双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树)。

(3)计算二叉树最大的宽度(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。

(4)用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目。

(5)求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。

(6)输出二叉树中从每个叶子结点到根结点的路径。

二叉树以二叉链表存储，写出对二叉树进行先序遍历的非递归算法。

解题思路：二叉树的先序遍历非递归算法利用栈结构，从二又树的根结点开始，输出结点信息，同时将结点指针入栈，然后顺着左子树，依次将其左子树各个结点值输出，同时结点指针入栈，直到左子树为空；然后让栈顶指针出栈，接着处理右子树。

二叉树

实验目的：

(1)熟悉二叉树的各种存储结构及适用范围。

(2)掌握建立二叉树的存储结构的方法。

(3)熟练掌握二叉树的先序、中序、后序遍历的递归算法和非递归算法。

(4)灵活运用递归的遍历算法实现二叉树的其他各种运算。

(5)掌握和理解本实验中出现的一些基本的C语言语句。

(6)体会算法在程序设计中的重要性。

实验内容：

(1)以二叉链表作存储结构，设计求二叉树高度的算法。

(2)以二叉链表作存储结构，编写递归的中序遍历算法。

(3)以二叉链表作存储结构，编写非递归的中序遍历算法。

(4)以二叉链表作存储结构，编写求二叉树中叶子结点的个数算法。

1、求如下（见附件图1）二叉树的先序、中序、后序、层序遍历序列。(20分) 2、已知一棵二叉树的先序和中序遍历的结点序列分别为IJKLMNO及JLKINMO，试画出此二叉树，并给出后序遍历序列结果。（40分） 3、设二叉树以二叉链表为存储结构，结点类型定义如下： typedef struct Node{ int data; struct Node *lchild, *rchild }BiTNode, *BiTree; 请编写一个函数 int Count (BTree T)，其功能是计算T所指的二叉树中结点值为偶数的结点数并返回该值。 （40分）