数据结构-树的基础知识

数和二叉树 - 概念讲解与实战(一)

树与二叉树

定义

树是一种非线性的数据结构,可用来描述有分支的结构,属于一种阶层性的非线性结构。二叉树是个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两棵不相交的、被分别称为左子树、右子树的二叉树组成。

其余概念

  • 叶节点:度为0的节点称为叶节点,或称为终端节点。
  • 节点的度:节点所拥有的子树的个数称为该节点的度。
  • 分支节点:度不为0的节点称为分支节点,或称为非终端节点。
  • 左孩子右孩子双亲:树中一个节点的子树的根节点称为这个节点的孩子,这个节点称为它孩子的双亲。
  • 路径路径长度
  • 祖先子孙:所谓祖先,是指从树根到该节点路径上所包含的节点,而子孙则是在该节点子树中的任一节点。
  • 节点的层数:规定树的根节点的层数为1,其余节点的层数等于它的双亲结点的层数加1。
  • 树的深度:树中所有节点的最大层数称为树的深度。
  • 树的度:树中各节点度的最大值称为该树的度。
  • 歪斜树:当一个二叉树完全没有右节点或左节点时,我们就把它称为左歪斜树或右歪斜树。
  • 严格二叉树:如果二叉树的每个分支节点均有非空的左右子树,则成为严格二叉树。
  • 满二叉树:在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子节点都在同一层上,这样的一棵二叉树称之为满二叉树。
  • 完全二叉树:一棵深度为k的有n个节点的二叉树,对树中的节点按照从上到下、从左到右的顺序进行编号,如果编号为i的节点与满二叉树之间树中编号为i的节点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。
    • 特点:叶子节点只能出现在最下层和次下层,且最下层的叶子节点集中在树的左部。

二叉树主要性质

  • 一棵非空二叉树的第i层上最多有2i-1个节点(i>=1)。

  • 一颗深度为k的二叉树中,最多具有2k-1个节点。

  • 对于一个非空的二叉树,如果叶子节点数为n0,度数为2的节点数为n2,则有n0 = n2 + 1。

  • 具有n个节点的完全二叉树的深度k为[log2n]+1(向下取整)。

  • 对于具有n个节点的完全二叉树,如果按照从上至下、从左至右的顺序对二叉树中的所有节点从1开始顺序编号,则对于任意的序号为i的节点,有如下情况:

    • 如果i>1,则序号为i的节点的双亲节点的序号为i/2;如果i=1,如果序号为i=1,则序号为i的节点是根节点,无双亲节点。
    • 如果2i<=n,则序号为i的节点的左孩子节点的序号为2i;如果2i>n,则序号为i的节点无左孩子。
    • 如果2i+1<=n,则序号为i的结点的右孩子结点的序号为2i+1;如果2i+1>n,则序号为i的结点无右孩子。
  • 对于具有n个节点的完全二叉树,如果按照从上至下、从左至右的顺序对二叉树的根节点从0开始编号,则相应的i号结点的双亲结点的编号为(i-1)/2,左孩子的编号为2i+1,右孩子的编号为2i+2

二叉树基本操作

  • 建立二叉树
  • 获得左子树
  • 获得右子树
  • 插入结点到左子树
  • 插入节点到右子树
  • 删除左子树
  • 删除右子树
  • 查找结点
  • 遍历二叉树

二叉树的实现

顺序存储

说白了就是用数组存储。

用一组连续的存储单元存放二叉树的结点,通常按照二叉树结点从上至下、从左至右的顺序存储。因为这样的结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系,只有通过一些方法确定某些节点在逻辑上的前驱节点和后继结点,这种存储才有意义。

因此,顺序结构只适用于满二叉树和完全二叉树,对于一般的二叉树我们会采用添加空结点,使之成为一棵完全二叉树(这当然会造成资源的浪费)的方式来进行存储。

显而易见,越接近满二叉树,则越节省空间,如果是歪斜树则最浪费空间。另外,要增删数据比较麻烦,必须重新建立二叉树。因为,我们一般不使用顺序存储。

链式存储

该方式是用链表来表示一棵二叉树,即用链表来指示元素的逻辑关系。

  • 二叉链表存储(最常用)

    链表中每个节点由三个域组成:一个数据域和两个指针域,分别用来给出该节点左孩子和右孩子所在链节点的存储地址。

lchild data rchild
左孩子 数据 右孩子
  • 三叉链表存储

    链表中每个节点由四个域组成:一个数据域和三个指针域,指针分别指向左孩子、右孩子和双亲的存储地址。

lchild data rchild parent
左孩子指针 数据 右孩子指针 双亲指针

遍历方法★

二叉树的遍历是指按照某种顺序访问二叉树的每个节点,使每个节点被访问一次且仅被访问一次。二叉树的遍历方法又分为先序遍历、中序遍历、后序遍历,而每一种都可以按照先左后右或者先右后左两种方法进行遍历,因此,一共有DLR DRL LDR RDL LRD RLD等六种遍历方法,所有的遍历都从根节点开始。

  • 先序遍历
    • 先序遍历的递归过程为
      • 若二叉树为空,遍历结束
      • 否则,访问根节点D,先序遍历根节点的左子树L,先序遍历根节点的右子树R(DLR)
  • 中序遍历
    • 中序遍历的递归过程为
      • 若二叉树为空,遍历结束
      • 否则,中序遍历根节点的左子树,访问根节点,中序遍历根节点的右子树(LDR)。
  • 后序遍历
    • 后序遍历的递归过程为
      • 若二叉树为空,遍历结束
      • 否则,后序遍历根节点的左子树,后序遍历根节点的右子树,访问根节点(LRD)。

就像该图片上所展示的那样,先序遍历结果为1,2,4,7,3,5,6,中序遍历为4,7,2,1,5,3,6,后序遍历为7,4,2,5,6,3,1

  • 层次遍历
    • 所谓二叉树的层次遍历,是指从二叉树的第一层(根节点)开始,从上至下逐层遍历,在同一层中,则按从左至右的顺序对节点逐个访问。在上图中,若按照层次遍历,顺序为1,2,3,4,5,6,7
    • 算法实现
      • 由于层次遍历节点的顺序是先遇到的节点先访问,与队列操作的顺序相同,所以,在进行层次遍历时,设置一个队列,将根节点引用入队,当队列非空时,循环执行一下三步;
        • 从队列中取出一个节点引用,并访问该节点。
        • 若该节点的左子树不为空,则将该结点的左子树引用入队。
        • 若该节点的右子树不为空,则将该节点的右子树引用入队。
      • 最后,输出队列即可实现。

代码实现

由于顺序存储较为简单,所以就不进行代码展示了,这里仅进行链式存储的相关展示,为了方便描述,特将其结构展示如下:

其中,IbiTree是接口,用来展示该二叉树实现的各项功能,Node文件采用了二叉链表结构的节点数据结构表示,LinkBiTree文件是接口的实现类,Test就是测试程序了,无关紧要。

Node.java

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
package com.x1aolin.hh;

public class Node<E> {
private E data; //数据域
private Node<E> lchild; //左孩子
private Node<E> rchild; //右孩子
//构造函数
public Node(E val,Node<E> lp,Node<E> rp){
this.data = val;
this.lchild = lp;
this.rchild = rp;
}
public Node(Node<E> lp,Node<E> rp){
this(null,lp,rp);
}
public Node(E val){
this(val,null,null);
}
public Node(){
}
//get set属性
public E getData(){
return data;
}
public void setData(E val){
data = val;
}
//左孩子
public Node<E> getLchild(){
return lchild;
}
public void setLchild( Node<E> lp){
this.lchild = lp;
}
//右孩子
public Node<E> getRchild(){
return rchild;
}
public void setRchild(Node<E> rp){
rchild = rp;
}
}

IbiTree.java

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
package com.x1aolin.hh;

public interface IbiTree<E> {
//判断是否为空
public boolean isEmpty();
//获取根节点
public Node<E> Root();
//获取树的高度
public int getHeight();
//获取节点数目
public int size();
//获取节点的左孩子节点
public Node<E> getLchild(Node<E> p);
//获取节点的右孩子节点
public Node<E> getRchild(Node<E> p);
//将节点p的左子树插入值为val的新节点,原来的左子树称为新节点的左子树
public void insertL(E val,Node<E> p);
//将节点p的右子树插入值为val的新节点,原来的右子树称为新节点的右子树
public void insertR(E val,Node<E> p);
//若p非空,删除p的左子树,并将其返回
public Node<E> deleteL(Node<E> p);
//若p非空,删除p的右子树,并将其返回
public Node<E> deleteR(Node<E> p);
//编写算法,在二叉树中查找值为value的节点
public Node<E> search(Node<E> root,E value);
//判断是否是叶子节点
public boolean isLeaf(Node<E> p);
//中序遍历 递归实现
public void inOrder();
//前序遍历 递归实现
public void preOrder();
//后序遍历 递归实现
public void postOrder();
//非递归实现中序遍历
public void inOrderByStack();
//非递归实现前序遍历
public void preOrderByStack();
//非递归实现后序遍历
public void postOrderByStack();
//层次遍历 可使用队列来实现
public void levelOrder();
}

LinkBiTree.java

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
package com.x1aolin.hh;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class LinkBiTree<E> implements IbiTree<E>{
private Node<E> root; //链表头引用指针 root根节点
public Node<E> getHead(){ //对应get方法
return root;
}
//无需set方法,该功能在构造方法中实现

public LinkBiTree(E val,Node<E> lp,Node<E> rp){
Node<E> p = new Node<E>(val,lp,rp);
root = p;
}
//仅创建根节点
public LinkBiTree(E val){
this(val,null,null);
}
public LinkBiTree(){ //空树
root = null;
}
//判断是否为空
public boolean isEmpty(){
return root==null;
}
//获取根节点
public Node<E> Root(){
return root;
}
//获取树的高度
public int getHeight(){
int i = this.getHeight(root);
System.out.println("二叉树的高度为:"+i);
return i;
}
private int getHeight(Node<E> root){
if(root==null) return 0;
return Math.max(getHeight(root.getLchild()),getHeight(root.getRchild()))+1;

}
//获取树的节点数
public int size(){
int i = this.size(root);
System.out.print("结点数为:"+i);
return i;
}
private int size(Node<E> root){
if(root!=null){
return size(root.getLchild())+size(root.getRchild())+1;
}
return 0;
}
//获取节点的左孩子节点
public Node<E> getLchild(Node<E> p){
return p.getLchild(); //这个是节点类中的方法,并不是该方法的递归!!!!
}
//获取节点的右孩子节点
public Node<E> getRchild(Node<E> p){
return p.getRchild();
}
//将节点p的左子树插入值为val的新节点,原来的左子树称为新节点的左子树
public void insertL(E val,Node<E> p){
Node<E> tmp = new Node<E>(val);
tmp.setLchild(p.getLchild());
p.setLchild(tmp);
}
//将节点p的右子树插入值为val的新节点,原来的右子树称为新节点的右子树
public void insertR(E val,Node<E> p){
Node<E> tmp = new Node<E>(val);
tmp.setRchild(p.getRchild());
p.setRchild(tmp);
}
//若p非空,删除p的左子树,并将其返回
public Node<E> deleteL(Node<E> p){
if(p==null || p.getLchild()==null){
return null;
}
else{
Node<E> tmp = p.getLchild();
p.setLchild(null);
return tmp;
}
}
//若p非空,删除p的右子树,并将其返回
public Node<E> deleteR(Node<E> p){
if(p==null || p.getRchild()==null)
return null;
Node<E> temp = p.getRchild();
p.setRchild(null);
return temp;
}
//编写算法,在二叉树中查找值为value的节点
public Node<E> search(Node<E> root,E value){
Node<E> p = root;
if(p==null){
return null;
}
if(p.getData().equals(value)){
return p;
}
if(p.getLchild()!=null){
return search(p.getLchild(),value);
}
if(p.getRchild()!=null){
return search(p.getRchild(),value);
}
return null;
}
//判断是否是叶子节点
public boolean isLeaf(Node<E> p){
return (p!=null)&&(p.getLchild()==null)&&(p.getRchild()==null);
}

//中序遍历LDR 这样外部直接使用即可,更好的封装,减轻了测试人员的劳动
public void inOrder(){
System.out.print("中序遍历:");
this.inOrder(root);
System.out.println();
}
private void inOrder(Node<E> p){
if(isEmpty()){
System.out.println("Tree is empty");
return;
}
if(p!=null){
inOrder(p.getLchild());
System.out.print(p.getData()+" ");
inOrder(p.getRchild());
}
}
//前序遍历
public void preOrder(){
System.out.print("前序遍历:");
this.preOrder(root);
System.out.println();
}
private void preOrder(Node<E> p){
if(isEmpty()){
System.out.println("Tree is empty");
return;
}
if(p!=null){ //递归结束条件
System.out.print(p.getData()+" ");
preOrder(p.getLchild());
preOrder(p.getRchild());
}
}
//后序遍历
public void postOrder(){
System.out.print("后序遍历:");
this.postOrder(root);
System.out.println();
}
private void postOrder(Node<E> p){
if(isEmpty()){
System.out.println("Tree is empty");
return;
}
if(p!=null){
postOrder(p.getLchild());
postOrder(p.getRchild());
System.out.print(p.getData()+" ");
}
}
//非递归实现中序遍历
public void inOrderByStack(){
if(root==null) return;
System.out.print("非递归实现中序遍历: ");
Deque<Node<E>> stack = new LinkedList<>();
Node<E> current = root;
//因为这两种情况下都要继续
while(current!=null||!stack.isEmpty()){
while(current!=null){
stack.push(current);
current = current.getLchild();
}
current = stack.pop();
System.out.print(current.getData()+" ");
current = current.getRchild();
}
System.out.println();
}
//非递归实现前序遍历 DLR
public void preOrderByStack(){
if(root==null) return;
System.out.print("非递归实现前序遍历: ");
Deque<Node<E>> stack = new LinkedList<>();
Node<E> current = root;
while(current !=null || !stack.isEmpty()){
while(current != null){
System.out.print(current.getData()+" ");
stack.push(current);
current = current.getLchild();
}
current = stack.pop();
current = current.getRchild();
}
System.out.println();
}
//非递归实现后序遍历 先序DRL的倒叙输出
public void postOrderByStack(){
if(root==null) return;
System.out.print("非递归实现后序遍历: ");
Deque<Node<E>> stack = new LinkedList<>();
Deque<Node<E>> res = new LinkedList<>();
Node<E> current = root;
while(current !=null || !stack.isEmpty()){
while(current != null){
res.push(current);
stack.push(current);
current = current.getRchild();
}
current = stack.pop();
current = current.getLchild();
}
while(!res.isEmpty()){
System.out.print(res.pop().getData()+" ");
}
System.out.println();
}
//层次遍历 使用队列进行依次输入
public void levelOrder(){
System.out.print("层次遍历:");
this.levelOrder(root);
System.out.println();
}
private void levelOrder(Node<E> root){
if(root==null) return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
Node<E> tmp = queue.poll();
System.out.print(tmp.getData()+" ");
if(tmp.getLchild()!=null)
queue.offer(tmp.getLchild());
if(tmp.getRchild()!=null)
queue.offer(tmp.getRchild());
}
}
}

二叉树的应用

哈夫曼树

哈夫曼树,又称最优二叉树,是指对于一组带有确定权值的叶节点,构造的具有最小带权路径长度的二叉树。其算法基本思想如下:

  • 由给定的N个权值(W1,W2,…,Wn)构造n棵只有一个叶子节点的二叉树,从而得到一个二叉树集合F={T1,T2,…,Tn};
  • 在F中选取根节点的权值最小和次小的两颗二叉树作为左、右子树构造一棵新的二叉树,这棵新的二叉树根节点的权值为其左右子树根节点权值之和;
  • 在集合F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到集合F中;
  • 重复步骤(2)和步骤(3),当F中只剩下一棵二叉树时,这棵二叉树就是所要建立的哈夫曼树。

代码实现

HNode.java

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
package com.x1aolin.huff;
/***
* 用数组来存放原来的n个叶子节点和构造过程中临时生成的节点
* @author x1aolin
*
*/
public class HNode {
private int weight;
private int lchild;
private int rchild;
private int parent;
private String name;
private String code;
public HNode(int w,String name) {
super();
this.weight = w;
this.lchild = -1;
this.rchild = -1;
this.parent = -1;
this.name = name;
this.code = "";
}
public HNode(){
this(0,null);
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getLchild() {
return lchild;
}
public void setLchild(int lchild) {
this.lchild = lchild;
}
public int getRchild() {
return rchild;
}
public void setRchild(int rchild) {
this.rchild = rchild;
}
public int getParent() {
return parent;
}
public void setParent(int parent) {
this.parent = parent;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getCode() {
return code;
}
public void setCode(String code) {
this.code = code;
}
}

HuffmanTree.java

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
package com.x1aolin.huff;

import java.util.Scanner;
/***
* 使用Huffman树的算法求报文字符编码
* 这样可以使传输的位数最少(最优二叉树)
* @author x1aolin
*
*/
public class HuffmanTree {
private HNode[] data; //节点数目
private int leafNum; //叶子节点数目

//判断是否为叶子节点
public boolean isLeaf(HNode p){
return (p!=null)&&(p.getLchild()==-1)&&(p.getRchild()==-1);
}
//构造一棵Huffman树
public void create(){
Scanner sc = new Scanner(System.in);
System.out.println("please input your context:");
String str = sc.nextLine().toLowerCase();
str = str.replace(" ", ""); //去掉空格
int[] c = new int[26]; //统计26个小写字符
for(int i=0;i<str.length();i++){
c[str.charAt(i)-'a']++; //统计所有字符的出现次数
}
int cnt = 0;
for(int i=0;i<26;i++){
if(c[i]>0){
cnt++; //统计字符的个数,需要至少出现一次
}
}
this.leafNum = cnt;

//这样可以存放原来的n个叶子节点和构造过程中临时生成的节点
//因为是临时生成,两两生成一个,所以会生成n-1个,两者一加为2n-1
data = new HNode[this.leafNum*2-1];
for(int i =0;i<2*this.leafNum-1;i++){
data[i] = new HNode();
}
cnt = 0;
for(int i=0;i<26;i++){
if(c[i]>0){
data[cnt].setName((char)(i+'a')+"");
data[cnt++].setWeight(c[i]);
}
}
int m1,m2,x1,x2;
//处理n个叶子节点,建立Huffman树
for(int i=0;i<this.leafNum-1;i++){
m1 = m2 = Integer.MAX_VALUE; //m1,m2为最小的两个权值
x1 = x2 = 0; //x1,x2为上面数值的对应位置
//在全部节点中找权值最小的两个节点
for(int j=0;j<this.leafNum+i;j++){
if((data[j].getWeight()<m1)&&(data[j].getParent()==-1)){//没有父节点
m2 = m1;
x2 = x1;
m1 = data[j].getWeight();
x1 = j;
}
else if((data[j].getWeight()<m2)&&(data[j].getParent()==-1)){
m2 = data[j].getWeight();
x2 = j;
}
}
//用两个权值最小点构造一个新的中间结点
data[this.leafNum + i].setWeight(data[x1].getWeight()+data[x2].getWeight());
data[this.leafNum + i].setLchild(x1);
data[this.leafNum + i].setRchild(x2);
//修改权值最小的两个节点的父节点指向
data[x1].setParent(this.leafNum + i);
data[x2].setParent(this.leafNum + i);
}
}
//输出huffman树的存储结构
public void print(){
System.out.println("位置\t字符\t权值\t父节点\t左孩子节点\t右孩子节点");
for(int i=0;i<2 * leafNum - 1;i++){
System.out.printf("%d\t%s\t%d\t%d\t%d\t%d\n",
i,data[i].getName(),data[i].getWeight(),data[i].getParent(),
data[i].getLchild(),data[i].getRchild());
}
}
//先序遍历,输出所有叶子节点的编码,并计算总的报文编码长度
public int preOrder(HNode root,String code){
int sum = 0;
if(root!=null){
root.setCode(code);
if(isLeaf(root)){
System.out.println(root.getName()+":"+root.getCode());
return root.getWeight() * root.getCode().length();
}
if(root.getLchild()!=-1){
sum += preOrder(data[root.getLchild()],code+"0");
}
if(root.getRchild()!=-1){
sum += preOrder(data[root.getRchild()],code+"1");
}
}
return sum;
}
}

二叉运算树

一般的算数式也可以转换成二叉运算树(Binary Expression Tree)的方式,方法如下:

  1. 考虑算数式中运算符的结合性与优先权,再适当的加上括号。
  2. 再由最内层的括号逐步向外,利用运算符当树根,左边操作数当左子树,右边操作数当右子树,其中优先权最低的运算符作为此二叉运算数的树根。

未完待续……

二叉排序树

请点击这里查看二叉排序树详细介绍

二叉搜索树

请点击这里查看二叉搜素树详细介绍

线索二叉树

请点击这里查看线索二叉树详细介绍

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------