学步园

/* threaded_tree.h -- 线索树头文件 */<br /> #define LINK 0<br /> #define THREAD 1</p> <p>/* 数据类型定义 */</p> <p>typedef int Item ;<br /> typedef struct node<br /> {<br /> Item item ;<br /> struct node * left ;<br /> struct node * right ;<br /> int left_tag ;<br /> int right_tag ;<br /> } Node ;<br /> typedef struct node * Tree ;</p> <p>/* 接口函数声明 */</p> <p>/* 操作: 初始化一棵线索树 */<br /> /* 操作前: ptree 指向一棵线索树 */<br /> /* 操作后: 该树被初始为空树 */<br /> void InitializeTree (Tree * const ptree) ;</p> <p>/* 操作: 确定一棵线索树是否为空 */<br /> /* 操作前: ptree 指向一棵已初始化的线索树 */<br /> /* 操作后: 如果该树为空, 返回1; 否则返回0 */<br /> int TreeIsEmpty (const Tree * const ptree) ;</p> <p>/* 操作: 向线索树中添加元素 */<br /> /* 操作前: ptree 指向一棵已初始化的线索树, pitem 指向被添加的指定数据 */<br /> /* 操作后: 如果可能, 将拥有 pitem 指向的数据的结点添加到树中, 返回1; 否则返回0 */<br /> int Insert (Tree * const ptree, const Item * const pitem) ;</p> <p>/* 操作: 获得指向树中最小数据所在结点的指针 */<br /> /* 操作前: ptree 指向一棵已初始化的线索树 */<br /> /* 操作后: 返回指向树中最小数据所在结点的指针 */<br /> Node * FindMin (const Tree * const ptree) ;</p> <p>/* 操作: 获得指向树中最大数据所在结点的指针 */<br /> /* 操作前: ptree 指向一棵已初始化的线索树 */<br /> /* 操作后: 返回指向树中最大数据所在结点的指针 */<br /> Node * FindMax (const Tree * const ptree) ;</p> <p>/* 操作: 从线索树中删除一个指定数据所在的结点 */<br /> /* 操作前: tree 是一棵已初始化的线索树, item 是的被删除的数据 */<br /> /* 操作后: 如果可能, pitem 指向数据所在的结点从树中删除, 函数返回新树; 否则函数返回原树 */<br /> Tree Delete (Tree tree, const Item item) ;</p> <p>/* 操作: 调用将一棵二叉搜索树中序线索化的函数将该树以中序线索化 */<br /> /* 操作前: ptree 指向一棵已初始化的二叉搜索树 */<br /> /* 操作后: 该树被中序线索化 */<br /> void InorderThreading (Tree * const ptree) ;</p> <p>/* 操作: 以中序将一个函数作用于树中所有元素 */<br /> /* 操作前: tree 是一棵已初始化的线索树, pfun 指向一个没有返回值, 接受一个Item类型参数的函数 */<br /> /* 操作后: pfun 指向的函数以中序被作用于树中所有元素一次 */<br /> void ThreadedTraversal (const Tree tree, void (* pfun) (const Item item)) ;</p> <p>/* 操作: 以中序将一个函数作用于树中所有元素 */<br /> /* 操作前: tree 是一棵已初始化的线索树, pfun 指向一个没有返回值, 接受一个Item类型参数的函数 */<br /> /* 操作后: pfun 指向的函数以中序被作用于树中所有元素一次 */<br /> void InorderTraversal (const Tree tree, void (* pfun) (const Item item)) ;