二叉树的应用举例实验报告(燕山大学)(6)

cout<<endl; CountLeaf (T, count); cout<<"此二叉树叶子节点为:"; cout<<count; cout<<endl;

depth=BiTreeDepth ( T);

}

运行结果：

cout<<"此二叉树深度为:"; cout<< depth; cout<<endl;

3.中序线索二叉链表的建立及遍历

输入：字符串序列

输出：结点的相关信息，中序序列

处理方法:

1) 在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。

2) 遍历过程中，附设指针pre, 并始终保持指针pre指向当前访问的指针p所指结点的前驱。

3) 中序线索二叉树结构对称。其中：第一个结点是最左下的结点，最后一个结点是最右下的结点。

4) 在中序线索二叉树上找结点的(直接)后继/前驱方法：

a) 若该结点有右孩子，其后继为其右子树中最左下的结点；

b) 若该结点无右孩子，其后继由rchild指向：其后继为满足以下条件的最小子树的根r：该结点为r的左子树中最右下的结点。

程序：

#include<iostream.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0