5. C#数据结构与算法 -- 非线性结构（树，二叉树，二叉查找树）
树的定义
树，由边连接的一些列节点。树是一种非线性的数据结构。
根节点，树上最高的节点。
父节点，某个节点的上层节点。
子节点，某个节点的下层节点。
叶子，没有任何子节点。
二叉树
二叉树，子节点的数量不超过两个的树。
父节点的两个节点分别称为左节点和右节点。
二叉查找树，是一种较小数据值存储在左节点，较大数据值存储在有节点的二叉树。
遍历的概念
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。
遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
此部分内容转自：http://blog.163.com/klint_khl1/blog/static/28831538200952391021725/
遍历方案
1．遍历方案
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任意给定结点上，可以按某种次序执行三个操作：
（1）访问结点本身(N)，
（2）遍历该结点的左子树(L)，
（3）遍历该结点的右子树(R)。
以上三种操作有六种执行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。
2．三种遍历的命名
根据访问结点操作发生位置命名：
① NLR：前序遍历(PreorderTraversal亦称(先序遍历))
——访问结点的操作发生在遍历其左右子树之前。
② LNR：中序遍历(InorderTraversal)
——访问结点的操作发生在遍历其左右子树之中(间)。
③ LRN：后序遍历(PostorderTraversal)
——访问结点的操作发生在遍历其左右子树之后。
注意：
由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
遍历算法
1．中序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
(1)遍历左子树；
(2)访问根结点；
(3)遍历右子树。
2．先序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
(1) 访问根结点；
(2) 遍历左子树；
(3) 遍历右子树。
3．后序遍历得递归算法定义：
若二叉树非空，则依次执行如下操作：
(1)遍历左子树；
(2)遍历右子树；
(3)访问根结点。
遍历序列
1．遍历二叉树的执行踪迹
三种递归遍历算法的搜索路线相同（如下图虚线所示）。
具体线路为：
从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。
A
B C
D E F
2．遍历序列
（1） 中序序列
中序遍历按照节点键值的升序顺序访问树中所有的节点。先访问根节点下的左子节点，再访问根节点下的右子节点。
中序遍历二叉树时，对结点的访问次序为中序序列
【例】中序遍历上图所示的二叉树时，得到的中序序列为：
D B A E C F
（2） 先序序列
先访问根节点，左子节点，再右子节点。
先序遍历二叉树时，对结点的访问次序为先序序列
【例】先序遍历上图所示的二叉树时，得到的先序序列为：
A B D C E F
（3） 后序序列
先访问左子节点，右子节点，再根节点。
后序遍历二叉树时，对结点的访问次序为后序序列
【例】后序遍历上图所示的二叉树时，得到的后序序列为：
D B E F C A
注意：
（1） 在搜索路线中，若访问结点均是第一次经过结点时进行的，则是前序遍历；若访问结点均是在第二次(或第三次)经过结点时进行的，则是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。
（2） 上述三种序列都是线性序列，有且仅有一个开始结点和一个终端结点，其余结点都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋(即双亲)结点和后继(即孩子)结点的概念，对上述三种线性序列，要在某结点的前趋和后继之前冠以其遍历次序名称。
【例】上图所示的二叉树中结点C，其前序前趋结点是D，前序后继结点是E；中序前趋结点是E，中序后继结点是F；后序前趋结点是F，后序后继结点是A。但是就该树的逻辑结构而言，C的前趋结点是A，后继结点是E和F。
从二叉查找树中移除叶子节点
把目标节点的父节点的每一个子节点设置为空。
50 50
25 75 => 25 75
1 49 51 99 1 49 51
=>
删除带有一个子节点的节点
将被删除节点的父节点，其左(右)节点指向被删除节点的左(右)子节点。
50 50
25 75 => 25 60
10 30 60 10 30
_________________________________________________________
50 50
25 75 => 25 80
10 30 80 10 30
_________________________________________________________
50 50
25 75 => 10 75
10 51 80 51 80
_________________________________________________________
50 50
25 75 => 30 75
30 51 80 51 80
删除带有两个子节点的节点
删除带有两个子节点的节点比较复杂。替换被删除的节点的这个新节点，我们暂称为后继节点。要实现删除，关键是寻找后继节点和重新设置后继节点的左右子节点。
后继节点是被删除节点的右子节点下的最小节点(中序遍历很快能找到)。
后继节点的左节点是原先被删除节点的左子节点，后继节点的右节点是原先被删除节点的右子节点(内部需要去除掉后继节点)。
例:
...............50
........25....................75
....10.......30........60.......80
...1..14..28..40...55.65..78..90
删除75(是一个右子节点)
...............50
........25...............78
....10......30.......60.....80
...1..14..28..40...55.65......90
删除25(是一个左子节点)
...............50
........28.................75
....10......30.......60.....80
...1..14......40...55.65..78..90
例:
...............50
........25....................75
....10......30..........60......80
...1..14..28..40...55.65......90
删除75
...............50
........25..............80
....10......30.......60.....90
...1..14..28..40...55.65........
重点实例1：
构造二叉查找树
一个节点Node类和一个二叉查找树BinarySearchTree类。
Node类包含数据成员：数据值、左节点、右节点。
BinarySearchTree类包含数据成员：根节点。和一个插入节点的方法。
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BinarySearchTree
{
public class Node
{
public int Data;
public Node Left;
public Node Right;
public void DisplayNode()
{
Console.Write(Data+"");
}
public Node(int v)
{
Data = v;
}
public Node()
{
Data = 0;
}
}
public class BinarySearchTree
{
public Node root;
public BinarySearchTree()
{
root = null;
}
//判断根节点为空，插入根节点
public void Insert(int i)
{
Node newNode = new Node();
newNode.Data = i;
if (root == null)
{
root = newNode;
}
else
{
Node current = root;
Node parent; //下一次的父节点
while (true)
{
parent = current;
if (i < current.Data)
{
current = current.Left;
if (current == null)
{
parent.Left = newNode;
break;
}
}
} //end while
}
}//end Insert()
//判断根节点为空，插入根节点，并判断左右节点，分别插入
public void Insert1(int i)
{
Node newNode = new Node();
newNode.Data = i;
if (root == null)
{
root = newNode;
}
else
{
Node current = root;
while (true)
{
if (i < current.Data)
{
if (current.Left == null)
{
current.Left = newNode;
break;
}
current = current.Left; //递归
}
else
{
if (current.Right == null)
{
current.Right = newNode;
break;
}
current = current.Right; //递归
}
} //end while
}
}//end Insert1()
///<summary>
/// 先序遍历
///</summary>
///<param name="theroot"></param>
public static void PreOrder(Node theroot)
{
if (!(theroot == null))
{
theroot.DisplayNode();
PreOrder(theroot.Left);
PreOrder(theroot.Right);
}
}
///<summary>
///中序遍历
///</summary>
///<param name="theroot"></param>
public static void InOrder(Node theroot)
{
if (!(theroot == null))
{
InOrder(theroot.Left);
theroot.DisplayNode();
InOrder(theroot.Right);
}
}
///<summary>
/// 后序遍历
///</summary>
///<param name="theroot"></param>
public static void PostOrder(Node theroot)
{
if (!(theroot == null))
{
PostOrder(theroot.Left);
PostOrder(theroot.Right);
theroot.DisplayNode();
}
}
}// end class BinarySearchTree
class Program
{
static void Main(string[] args)
{
BinarySearchTree bst = new BinarySearchTree();
bst.Insert1(1);
bst.Insert1(3);
bst.Insert1(5);
bst.Insert1(4);
bst.Insert1(2);
//调用
Console.WriteLine("PreOrder:");
BinarySearchTree.PreOrder(bst.root);///1 3 2 5 4
///
Console.WriteLine();
Console.WriteLine("InOrder:");
BinarySearchTree.InOrder(bst.root);///1 2 3 4 5
///
Console.WriteLine();
Console.WriteLine("PostOrder:");
BinarySearchTree.PostOrder(bst.root);///2 4 5 3 1
Console.ReadLine();
}
}
}参考：
http://blog.csdn.net/maths_bai/article/details/8046586
本文出自 “Ricky's Blog” 博客，请务必保留此出处http://57388.blog.51cto.com/47388/1658507
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
