数据结构 From Zero To Hero(七)
發佈於 2021-03-01
之前几篇，我们介绍的都是线性存储结构，从本篇开始，我们要来介绍计算机科学中两个非常重要的非线性存储结构，其中之一就是本篇的重点 —— 树(Tree)。
二叉树(Binary Tree)
类似于真实世界，计算机科学中的树也有不同种类，我们首先学习最简单的树 —— 二叉树。一旦我们学会二叉树之后我们就可以快速学习其他类型的树了。
树的应用非常多，例如:
- 展示层级结构(File 和 Folder)
- 数据库索引(Index)
- 编译器(Syntax Tree)
- 压缩(JPEG、MP3)
- 自动补全
有一类特殊的二叉树称为二叉搜索树，他的特点是: 左子树的所有值小于该节点，右子树的所有值都大于该节点。
Building a BinarySearchTree
public class BinarySearchTree<T> where T : IComparable
{
private class Node<T>
{
public T Value { get; private set; }
public Node<T> LeftChild { get; set; }
public Node<T> RightChild { get; set; }
public Node(T value)
{
Value = value;
}
}
private Node<T> Root { get; set; }
public void Insert(T value)
{
var node = new Node<T>(value);
if (Root == null)
{
Root = node;
return;
}
var current = Root;
while (true)
{
if (current.Value.CompareTo(value) == 1)
{
if (current.LeftChild == null)
{
current.LeftChild = node;
break;
}
current = current.LeftChild;
}
else
{
if (current.RightChild == null)
{
current.RightChild = node;
break;
}
current = current.RightChild;
}
}
}
public bool Find(T value)
{
var current = Root;
while (current != null)
{
if (current.Value.CompareTo(value) == 1)
{
current = current.LeftChild;
}
else if (current.Value.CompareTo(value) == -1)
{
current = current.RightChild;
}
else
{
return true;
}
}
return false;
}
}Traversing Trees
不同于线性结构，树的遍历分为两种方式:
- 广度优先(BREADTH FIRST): 以层次顺序遍历，先遍历同一层次，再遍历下一层次
- 深度优先(DEPTH FIRST): 以深度顺序遍历，又可分为前序、中序、后序三种方式
- 前序遍历(Pre-Order): Root -> Left -> Right
- 中序遍历(In-Order): Left -> Root -> Right
- 前序遍历(Post-Order): Left -> Right -> Root
注意: 前中后指的是何时访问 Root 元素。
Recursion
在实现树的遍历代码之前，我们首先要介绍在计算机科学中极其常用的概念 —— 递归。
“In order to understand recursion, one must first understand recursion.”
recursion
public int Factorial(int n)
{
//base case
if (n == 0)
{
return 1;
}
//recursion case
return n * Factorial(n - 1);
}Depth First Traversal
public void TraversePreOrder()
{
TraversePreOrder(Root);
}
private void TraversePreOrder(Node<T> root)
{
if (root == null)
{
return;
}
Console.WriteLine(root.Value);
TraversePreOrder(root.LeftChild);
TraversePreOrder(root.RightChild);
}
public void TraverseInOrder()
{
TraverseInOrder(Root);
}
private void TraverseInOrder(Node<T> root)
{
if (root == null)
{
return;
}
TraverseInOrder(root.LeftChild);
Console.WriteLine(root.Value);
TraverseInOrder(root.RightChild);
}
public void TraversePostOrder()
{
TraversePostOrder(Root);
}
private void TraversePostOrder(Node<T> root)
{
if (root == null)
{
return;
}
TraversePostOrder(root.LeftChild);
TraversePostOrder(root.RightChild);
Console.WriteLine(root.Value);
}Equality Checking
public bool Equal(Tree<T> other)
{
return Equal(Root, other.Root);
}
private bool Equal(Node<T> first, Node<T> second)
{
if (first == null && second == null)
{
return true;
}
if (first != null && second != null)
{
return first.Value.Equals(second.Value)
&& Equal(first.LeftChild, second.LeftChild)
&& Equal(first.RightChild, second.RightChild);
}
return false;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-03-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
