#include <stdio.h>
enum pointer_tag { LINK, THREAD };
struct node {
char* data;
struct node* lchild;
struct node* rchild;
enum pointer_tag ltag, rtag;
};
void visit(char* data) {
printf("%s ", data);
}
void traverse(struct node* head) {
struct node* p = head->lchild;
while (p != head) {
while (p->ltag == LINK)
p = p->lchild;
visit(p->data);
while (p->rtag == THREAD && p->rchild != head) {
p = p->rchild;
visit(p->data);
}
p = p->rchild;
}
printf("\n");
}
void set_node(struct node* node, char * data, struct node* lchild, struct node* rchild, enum
pointer_tag ltag, enum pointer_tag rtag) {
node->data = data;
node->lchild = lchild;
node->rchild = rchild;
node->ltag = ltag;
node->rtag = rtag;
}
/*
* +
* / \
* a b
*/
void test_1() {
struct node root, node1, node2, node3;
set_node(&root, "r", &node1, &node3, LINK, THREAD);
set_node(&node1, "+", &node2, &node3, LINK, LINK);
set_node(&node2, "a", &root, &node1, THREAD, THREAD);
set_node(&node3, "b", &node1, &root, THREAD, THREAD);
traverse(&root);
}
/*
* -
* / \
* / \
* + "/"
* / \ / \
* a * e f
* / \
* b -
* / \
* c d
*/
void test_2() {
struct node root, node1, node2, node3, node4, node5, node6, node7, node8,
node9, node10, node11;
set_node(&root, "r", &node1, &node7, LINK, THREAD);
set_node(&node1, "-", &node2, &node3, LINK, LINK);
set_node(&node2, "+", &node4, &node5, LINK, LINK);
set_node(&node3, "/", &node6, &node7, LINK, LINK);
set_node(&node4, "a", &root, &node2, THREAD, THREAD);
set_node(&node5, "*", &node8, &node9, LINK, LINK);
set_node(&node6, "e", &node1, &node3, THREAD, THREAD);
set_node(&node7, "f", &node3, &root, THREAD, THREAD);
set_node(&node8, "b", &node2, &node5, THREAD, THREAD);
set_node(&node9, "-", &node10, &node11, LINK, LINK);
set_node(&node10, "c", &node5, &node9, THREAD, THREAD);
set_node(&node11, "d", &node9, &node1, THREAD, THREAD);
traverse(&root);
}
int main(int argc, const char *argv[]) {
test_1();
test_2();
return 0;
}
分享到:
相关推荐
线索二叉树 线索二叉树(Threaded Binary Tree)是对二叉树的一种优化,目的是使遍历二叉树的过程更加高效。
这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种 一个结点的前一个结点,...
Threaded binary tree in C++
Threaded binary tree 186 AVL tree 191 Red-black tree 195 AA tree 210 Scapegoat tree 215 Splay tree 219 T-tree 234 Rope 237 Top Trees 242 Tango Trees 246 Van Emde Boas tree 268 Cartesian tree 272 Treap...
用Java实现【线索二叉树】完整版,加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)
左程云leetcode 数据结构和算法学习笔记...线索二叉树(Threaded Binary Tree) 前缀树/字典树(Trie) 5. 哈希/散列(Hashing) 哈希表(Hash Table) 哈希函数(Hash Functions) 6. 优先队列(Priority Queue) 堆
左程云leetcode 数据结构和算法学习笔记...线索二叉树(Threaded Binary Tree) 前缀树/字典树(Trie) 5. 哈希/散列(Hashing) 哈希表(Hash Table) 哈希函数(Hash Functions) 6. 优先队列(Priority Queue) 堆
Binary search tree (BST) based data structures, such as AVL trees, red-black trees, and splay trees, are often used in system software, such as operating system kernels. Choosing the right kind of ...
Theoretically a b+tree is O(N log k N) or log base k of N, now for the typical values of k which are above 200 for example the b+tree should outperform any binary tree because it will use less ...
option to restore this directory tree or you will have problems because the files would not be in their proper subdirectories. Please note most of these directories are differently named to ICS V7 ...
threaded. The overhead of a semaphore per-method is eliminated. Fixed a regression where an error was no longer emitted if a control method attempts to create 2 objects of the same name. This once ...
To guarantee uniqueness, they should be based on the full path in a project's source tree. For example, the file foo/src/bar/baz.h in project foo should have the following guard: #ifndef FOO_BAR_BAZ...