本文共 3461 字,大约阅读时间需要 11 分钟。
树:跟数组,链表,堆栈,队列不一样,这些都是线性的数据结构,而树呢是层级类的数据结构。
树的词汇表:最上层的节点叫树根节点,一个元素下层的直接元素称为它的孩子节点。直接上层节点称为父节点。例如a是f的孩子,并且f是孩子的父亲。最后没有孩子节点的元素称为叶子节点。
tree ---- j <-- root / \ f k / \ \ a h z <-- leaves
为啥要用树?
file system ----------- / <-- root / \ ... home / \ ugrad course / / | \ ... cs101 cs112 cs113
树的主要应用
二叉树:一个树中的元素最多有两个孩子节点,叫做二叉树。因为二叉树中每个节点只有两个孩子,所以我们一般叫它们左孩子与右孩子。
C语言表示的二叉树:一个树通过一个指向最顶部的节点的指针来表示,如果这个树为空,那么根节点的值为NULL
一个树的节点包含一下内容:
1. 数据 2. 指向左孩子的指针 3. 指向右孩子的指针在C语言中,我们可以用结构体表示一个树的节点。下面就是一个带有整数数据的树节点的例子:
struct node { int data; struct node *left; struct node *right;};
/* Class containing left and right child of current node and key value*/class Node{ int key; Node left, right; public Node(int item) { key = item; left = right = null; }}
用C写的第一个简单树
tree ---- 1 <-- root / \ 2 3 / 4
struct node { int data; struct node *left; struct node *right;};/* newNode() allocates a new node with the given data and NULL left and right pointers. */struct node* newNode(int data){ // Allocate memory for new node struct node* node = (struct node*)malloc(sizeof(struct node)); // Assign data to this node node->data = data; // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node);}int main(){ /*create root*/ struct node *root = newNode(1); /* following is the tree after above statement 1 / \ NULL NULL */ root->left = newNode(2); root->right = newNode(3); /* 2 and 3 become left and right children of 1 1 / \ 2 3 / \ / \ NULL NULL NULL NULL */ root->left->left = newNode(4); /* 4 becomes left child of 2 1 / \ 2 3 / \ / \ 4 NULL NULL NULL / \NULL NULL*/ getchar(); return 0;}
Java实现
/* Class containing left and right child of current node and key value*/class Node{ int key; Node left, right; public Node(int item) { key = item; left = right = null; }}// A Java program to introduce Binary Treeclass BinaryTree{ // Root of Binary Tree Node root; // Constructors BinaryTree(int key) { root = new Node(key); } BinaryTree() { root = null; } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); /*create root*/ tree.root = new Node(1); /* following is the tree after above statement 1 / \ null null */ tree.root.left = new Node(2); tree.root.right = new Node(3); /* 2 and 3 become left and right children of 1 1 / \ 2 3 / \ / \ null null null null */ tree.root.left.left = new Node(4); /* 4 becomes left child of 2 1 / \ 2 3 / \ / \ 4 null null null / \ null null */ }}
总结:树是一种层级的数据结构。树主要用于维护层级数据,提供更方便的访问,插入删除功能。二叉树是树的特例,它的每个节点最多有两个孩子。
转载地址:http://wkhii.baihongyu.com/