C# 二叉树的简介

什么是二叉树？？？

二叉树是树结构的一种特殊形式。它是n个节点的集合，每个节点最多只能有两个子结点，二叉树的子树仍然是二叉树。二叉树的一个结点对应的两个子树分别称为左子树和右子树。由于子树有左右之分，因此二叉树是有序树。

二叉树还可以进一步细分为两种特殊类型。满二叉树，完全二叉树（如上图）

**满二叉树：**即在二叉树中最下一层的叶节点外，每层的节点都有两个子结点。
**完全二叉树：**即在二叉树中除二叉树中最后一层外，其他各层的结点树都达到最大个数，且最后一层叶节点按照从左到右的顺序连续存在，只缺最后一层右侧若干个结点。

二叉树主要性质：
1，在二叉树的第i层最多有2^(i-1)个结点（i>=1）

2, 深度为K的二叉树至多有2^k -1个结点

3，对于一个完全二叉树，假设它有n个结点，对节点进行从开始编号，对任意结点i满足下面：
a，它的双亲是结点i/2(除了i=1的情况)
b，左孩子是2i，右孩子是2i+1
c，如果2*i>n说明无左孩子 2i+1>n说明无右孩子

二叉树的几种遍历方法：
1，前序遍历：
当给出当前终点的数据，再依次遍历给出左结点和右结点。

2，中序遍历：
先遍历输出做结点，再输出当前结点，在遍历输出右结点

3，后序遍历
先遍历输出左结点，再遍历输出右结点，最后输出当前结点的数据

4，层序遍历
从树的第一层开始，从上到下逐层遍历，在同一层中，从左到右对结点 逐个访问输出

二叉树的存储–顺序存储以及遍历的方法

using System;

namespace _2_1_2二叉树顺序结构存储
{ /// <summary> /// T类型的二叉树类 /// </summary> /// <typeparam name="T"></typeparam> class BiTree<T> { private T[] data; private int count = 0; /// <summary> /// 构造方法 /// </summary> /// <param name="capacity">二叉树的容量</param> public BiTree(int capacity) { data = new T[capacity]; } /// <summary> /// 给二叉树添加数据 /// </summary> /// <param name="item">添加的数据</param> /// <returns></returns> public bool Add(T item) { if (count >= data.Length) return false; data[count] = item; count++; return true; } //提供给外部调用的公有方法--前序遍历 public void Forword() { Forword(0); } /// <summary> /// 前序遍历二叉树 /// </summary> private void Forword(int index) { //递归出口 if (index >= count) return; //不能大于数据的数量 if (data[index].Equals(-1)) return;  //如果不是满二叉树，顺序存入的时候以-1代替，那么遍历到-1的时候就直接return。 //得到要遍历的结点的编号 int number = index + 1; Console.Write(data[index] + " "); //得到做结点的编号 int leftNum = number * 2; int rightNum = number * 2 + 1; //递归调用 Forword(leftNum - 1); Forword(rightNum - 1); } //中序遍历 public void Middle() { Middle(0); } /// <summary> /// 中序遍历二叉树 /// </summary> private void Middle(int index) { //递归出口 if (index >= count) return; if (data[index].Equals(-1)) return; //得到要遍历的结点的编号 int number = index + 1; //得到左子结点的编号 int leftNum = number * 2; int rightNum = number * 2 + 1; Middle(leftNum - 1); Console.Write(data[index] + " "); Middle(rightNum - 1); } //后序遍历 public void Last() { Last(0); } /// <summary> /// 后序遍历二叉树 /// </summary> private void Last(int index) { //递归出口 if (index >= count) return; if (data[index].Equals(-1)) return; //得到要遍历的结点的编号 int number = index + 1; //得到左子结点的编号 int leftNum = number * 2; int rightNum = number * 2 + 1; Middle(leftNum - 1); Middle(rightNum - 1); Console.Write(data[index] + " "); } }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
 

using System;

namespace _2_1_2二叉树顺序结构存储
{ class Program { static void Main(string[] args) { //要存储到二叉树中的数据 char[] data = { 'A','B','C','D','E','F','G','H','I','J'}; //顺序存储二叉树 BiTree<char> tree = new BiTree<char>(10); for (int i = 0; i < data.Length; i++) { //存储数据到二叉树中 tree.Add(data[i]); } //调用遍历二叉树的方法 tree.Forword(); Console.WriteLine(); tree.Middle(); Console.WriteLine(); tree.Last(); Console.ReadKey(); } }
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
 

文章来源: czhenya.blog.csdn.net，作者：陈言必行，版权归原作者所有，如需转载，请联系作者。

原文链接：czhenya.blog.csdn.net/article/details/78828985