树：
1 概念
-
定义：树是节点的有限集合
-
度：当前双亲的直接孩子个数
-
叶子：终端节点（度为0）就是叶子
-
根：非终端节点
-
有序树：树当中的节点之间位置不可以互换
-
无序树：树当中节点之间位置可以互换
-
深度之节点深度：当前节点所在第几层即为节点深度
-
深度之树的深度:该树最大的节点深度
2 二叉树：
3 二叉搜索树
- 定义：所有结点的度都小于或等于2，并且当前结点值一定是大于左孩子结点值，小于右孩子结点值
- 遍历：最后得到的遍历序列是一个有序序列
4 二叉树的遍历:
1(0)
3(1) 5(2)
10(3) 26(4) 19(5) 27(6)
-
前序遍历：根->左->右: 1->3->10->26->5->19->27
-
中序遍历：左->根->右: 10->3->26->1->19->5->27
-
后序遍历：左->右->根 10->26->3->19->27->5->1
5 树的用途
6 二叉树的常用操作
- 创建树
- 销毁树
- 根据下标搜索结点
- 往某个结点某个孩子添加结点
- 删除某个结点
- 二叉树的深度
- 二叉树结点个数
7 二叉树双向链表代码实现
//该结点所在的下标
private int index;
//该结点实际存储的数据
private T data;
//该结点下的左孩子
private TreeNode<T> leftNode;
//该结点下的右孩子
private TreeNode<T> rightNode;
//该结点对应的父结点
private TreeNode<T> parentNode;
//属性
public T Data{set{ data = value;
}get{ return data;}}
public TreeNode<T> LeftNode{
set{
leftNode = value;
}
get{
return leftNode;
}
}
public TreeNode<T> RightNode{
set{
rightNode = value;
}
get{
return rightNode;
}
}
public TreeNode<T> ParentNode{
set{
parentNode = value;
}
get{
return parentNode;
}
}
public int Index{
set{
index = value;
}
get{
return index;
}
}
//常用构造
public TreeNode ()
{
index = 0;
data = default(T);
leftNode = null;
rightNode = null;
parentNode = null;
}
public TreeNode(int index,T data){
this.index = index;
this.data = data;
leftNode = null;
rightNode = null;
parentNode = null;
}
//使用递归来判断该下标的结点是否存在于该结点之下
public TreeNode<T> NodeAtIndex(int index){
//(1) 首先判断是否为该结点
if (index == this.index) {
return this;
}
//(2)若不是则遍历该结点下的左右孩子，依次进行遍历下去
TreeNode<T> temp = null;
if (this.LeftNode != null) {
temp = this.LeftNode.NodeAtIndex (index);
}
if (temp == null) {
if(this.RightNode != null) {
temp = this.RightNode.NodeAtIndex (index);
}
}
return temp;
}
//删除本身结点以及该结点下的子结点
public void DeleteNode(){
//（1）判断该结点是否存在左右孩子，若有的话同样进行删除（使用递归）
if(this.LeftNode != null){
this.LeftNode.DeleteNode ();
}
if (this.RightNode != null) {
this.RightNode.DeleteNode ();
}
//判断该结点是属于双亲结点的左孩子还是右孩子，删除掉双亲对应的孩子
if (this.ParentNode != null) {
if (this.ParentNode.LeftNode == this) {
this.ParentNode.LeftNode = null;
}
if (this.ParentNode.RightNode == this) {
this.ParentNode.RightNode = null;
}
}
}
//使用递归该结点下的所有结点进行前序遍历
public void PreordeTraversal(){
/*思路：遍历该结点下以及左右孩子（左右孩子存在的时候）
对于左右孩子则视为某些结点的双亲再进行前序遍历
*/
Console.WriteLine("index = {0},data = {1} ",Index,Data);
if (this.LeftNode != null) {
this.LeftNode.PreordeTraversal();
}
if (this.RightNode != null) {
this.RightNode.PreordeTraversal ();
}
}
//该结点下的所有结点进行中序遍历
public void InorderTraversal(){
/*思路同前序遍历,顺序调整为中，左，右*/
if (this.LeftNode != null) {
this.LeftNode.InorderTraversal();
}
Console.WriteLine("index = {0},data = {1} ",Index,Data);
if (this.RightNode != null) {
this.RightNode.InorderTraversal ();
}
}
//该结点下的所有结点进行后序遍历
public void PostorderTraversal(){
/*思路同前序遍历,顺序调整为左，右，中*/
if (this.LeftNode != null) {
this.LeftNode.PostorderTraversal ();
}
if (this.RightNode != null) {
this.RightNode.PostorderTraversal ();
}
Console.WriteLine("index = {0},data = {1} ",Index,Data);
}
//该结点的子结点包括该结点总共有几个结点
public int CountOFChildNode(){
int count = 0;
if(this.LeftNode != null){
count += this.LeftNode.CountOFChildNode ();
}
if (this.RightNode != null) {
count += this.RightNode.CountOFChildNode ();
}
//返回之前进行++操作是将本身添加进去
return ++count;
}
//某个结点的最大深度
public int Depth(){
int leftDepth = 0,rightDepth = 0;
if(this.LeftNode != null){
leftDepth = this.LeftNode.Depth ();
}
if (this.RightNode != null) {
rightDepth = this.RightNode.Depth ();
}
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
//根结点
public TreeNode<T> rootNode;
//构造方法，在创建树的时候对根结点进行初始化
public BinaryTree ()
{
rootNode = new TreeNode<T> ();
}
//根据某个下标返回对应的结点
public TreeNode<T> NodeAtIndex(int index){
return rootNode.NodeAtIndex(index);
}
//在下标为index添加一个结点node，direction为0表示左孩子，为1表示右孩子
public bool AddNode(int index,int direction,TreeNode<T> node){
//先判断index对应的结点是否存在，不存在则没法挂载
TreeNode<T> temp = NodeAtIndex(index);
if (temp == null) {
return false;
}
//若是该结点存在则将要挂载的结点拷贝一份出来
TreeNode<T> newNode = new TreeNode<T>();
newNode.Index = node.Index;
newNode.Data = node.Data;
newNode.ParentNode = temp;
if (direction == 0) {
temp.LeftNode = newNode;
}
if (direction == 1) {
temp.RightNode = newNode;
}
return true;
}
//根据下标删除一个结点
public bool DeleteNode(int index){
TreeNode<T> temp = NodeAtIndex(index);
if (temp == null) {
return false;
}
if (temp.ParentNode.LeftNode ==temp) {
temp.ParentNode.LeftNode = null;
} else if (temp.ParentNode.RightNode == temp) {
temp.ParentNode.RightNode = null;
}
temp.DeleteNode ();
return true;
}
//二叉树的深度
public int DepthOfTree(){
return rootNode.Depth();
}
//树的某个结点下子结点个数（包括该结点）
public int CountOfNode(TreeNode<T> node){
if (rootNode == null) {
return 0;
} else {
return rootNode.CountOFChildNode ();
}
}
//前序遍历
public void PreordeTraversal(){
rootNode.PreordeTraversal();
}
//中序遍历
public void InorderTraversal(){
rootNode.InorderTraversal();
}
//后序遍历
public void PostorderTraversal(){
rootNode.PostorderTraversal();
}
0
1 2
3 4 5 6
7 8 9
前序遍历:根左右: 0 1 3 7 8 4 9 2 5 6
后序遍历：左右根:7 8 3 9 4 1 5 6 2 0
中序遍历:左根右：7 3 8 1 9 4 0 5 2 6
//创建结点
BinaryTree<string> btTree = new BinaryTree<string> ();
TreeNode<string> node0 = new TreeNode<string> (1, "node0");
TreeNode<string> node1 = new TreeNode<string> (2, "node1");
TreeNode<string> node2 = new TreeNode<string> (3, "node2");
TreeNode<string> node3 = new TreeNode<string> (4, "node3");
TreeNode<string> node4 = new TreeNode<string> (5, "node4");
TreeNode<string> node5 = new TreeNode<string> (6, "node5");
TreeNode<string> node6 = new TreeNode<string> (7, "node6");
TreeNode<string> node7 = new TreeNode<string> (8, "node7");
TreeNode<string> node8 = new TreeNode<string> (9, "node8");
//添加结点
btTree.AddNode (0, 0, node0);
btTree.AddNode (0, 1, node1);
btTree.AddNode (1, 0, node2);
btTree.AddNode (1, 1, node3);
btTree.AddNode (2, 0, node4);
btTree.AddNode (2, 1, node5);
btTree.AddNode (3, 0, node6);
btTree.AddNode (3, 1, node7);
btTree.AddNode (4, 0, node8);
//删除结点
btTree.DeleteNode (3);
btTree.DeleteNode (4);
//结点个数
Console.WriteLine ("count = {0}", btTree.CountOfNode (btTree.rootNode));
Console.WriteLine ("树的深度 = {0}", btTree.DepthOfTree ());
//某个下标下的结点
Console.WriteLine (btTree.NodeAtIndex (6).Data);
//前序遍历
btTree.PreordeTraversal ();
//后序遍历
btTree.PostorderTraversal();
//中序遍历
btTree.InorderTraversal();
