二叉树

二叉树

基本概念

定义

n(n≥0)个结点的有限集合,由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

逻辑结构

一对二

基本特征

  • 每个结点最多只有两棵子树(不存在度大于2的结点);
  • 左子树和右子树次序不能颠倒(有序树)。

二叉树的实现

二叉树的遍历

  • DLR — 先序遍历,即先根再左再右
  • LDR — 中序遍历,即先左再根再右
  • LRD — 后序遍历,即先左再右再根

“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。
从递归的角度看,这三种算法是完全相同的,或者说这三种遍历算法的访问路径是相同的,只是访问结点的时机不同。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>



typedef struct _BINARYNODE {
char ch;
struct _BINARYNODE *LeftChirld;
struct _BINARYNODE *RightChirld;
} BubaryNode;


static void recursion(BubaryNode *pBINARYNODE);

static void test1() {
BubaryNode nodeA = {'A', NULL, NULL};
BubaryNode nodeB = {'B', NULL, NULL};
BubaryNode nodeC = {'C', NULL, NULL};
BubaryNode nodeD = {'D', NULL, NULL};
BubaryNode nodeE = {'E', NULL, NULL};
BubaryNode nodeF = {'F', NULL, NULL};
BubaryNode nodeG = {'G', NULL, NULL};
BubaryNode nodeH = {'H', NULL, NULL};

// 建立关系
nodeA.LeftChirld = &nodeB;
nodeA.RightChirld = &nodeF;
nodeB.RightChirld = &nodeC;
nodeC.LeftChirld = &nodeD;
nodeC.RightChirld = &nodeE;
nodeF.RightChirld = &nodeG;
nodeG.LeftChirld = &nodeH;

recursion(&nodeA);

}

/**
* 二叉树递归
* @param rootNode
*/
static void recursion(BubaryNode *rootNode) {
if (rootNode == NULL){
return;
}

// 先序遍历 :先根,再左,再右。
printf("%c ", rootNode->ch);
recursion(rootNode->LeftChirld);
recursion(rootNode->RightChirld);



// 中序遍历 :先左,再右,再根。
/*
recursion(rootNode->LeftChirld);
printf("%c ", rootNode->ch);
recursion(rootNode->RightChirld);
*/


// 后序遍历 : 先左,再右,再根。
/*
recursion(rootNode->LeftChirld);
recursion(rootNode->RightChirld);
printf("%c ", rootNode->ch);
*/


}

int main(int argc, char *argv[]) {

test1();

return 0;
}

二叉树的使用

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>



typedef struct _BINARYNODE {
char ch;
struct _BINARYNODE *LeftChirld;
struct _BINARYNODE *RightChirld;
} BinaryNode;


/**
* 计算二叉树高度:左子树与右子树同时为NULL,则为叶子
* @param rootnode
* @param p
*/
static void calLeaves(BinaryNode *rootnode, int *p) {

if (rootnode == NULL) {
return;
}

if (rootnode->LeftChirld == NULL && rootnode->RightChirld == NULL) {
(*p)++;
}


calLeaves(rootnode->LeftChirld, p);
calLeaves(rootnode->RightChirld, p);

}

/**
* 二叉树遍历
* @param rootNode
*/
static void recursion(BinaryNode *rootNode) {
if (rootNode == NULL) {
return;
}

printf("%c ", rootNode->ch);
recursion(rootNode->LeftChirld);
recursion(rootNode->RightChirld);

}

static int BinaryTreeHeight(BinaryNode *root) {
if (root == NULL) {
return 0;

}

int left = BinaryTreeHeight(root->LeftChirld);
int right = BinaryTreeHeight(root->RightChirld);

return left > right ? left + 1 : right + 1;

}

/**
* 拷贝二叉树
* @param root
* @return
*/
static BinaryNode *copyTree(BinaryNode *root) {
if (root == NULL) {
return NULL;
}

BinaryNode *leftChild = copyTree(root->LeftChirld);
BinaryNode *rightChild = copyTree(root->RightChirld);

BinaryNode *newNode = malloc(sizeof(BinaryNode));
newNode->ch = root->ch;

newNode->LeftChirld = leftChild;
newNode->RightChirld = rightChild;


return newNode;
}

/**
* 二叉树的内存释放
* @param root
*/
static void freeTree(BinaryNode *root){

if (root==NULL){
return;
}


freeTree(root->LeftChirld);
freeTree(root->RightChirld);
printf("Free:%c\n", root->ch);
free(root);

}

static void test01() {
int num = 0;
BinaryNode nodeA = {'A', NULL, NULL};
BinaryNode nodeB = {'B', NULL, NULL};
BinaryNode nodeC = {'C', NULL, NULL};
BinaryNode nodeD = {'D', NULL, NULL};
BinaryNode nodeE = {'E', NULL, NULL};
BinaryNode nodeF = {'F', NULL, NULL};
BinaryNode nodeG = {'G', NULL, NULL};
BinaryNode nodeH = {'H', NULL, NULL};

// 建立关系
nodeA.LeftChirld = &nodeB;
nodeA.RightChirld = &nodeF;
nodeB.RightChirld = &nodeC;
nodeC.LeftChirld = &nodeD;
nodeC.RightChirld = &nodeE;
nodeF.RightChirld = &nodeG;
nodeG.LeftChirld = &nodeH;

calLeaves(&nodeA, &num);
printf("二叉树叶子数量:%d\n", num);


BinaryNode *newTree = copyTree(&nodeA);
recursion(newTree);

printf("\n二叉树高度:%d\n", BinaryTreeHeight(&nodeA));

freeTree(newTree);
printf(":::%c\n", (unsigned char) newTree->RightChirld->RightChirld);


}

int main(int argc, char *argv[]) {

test01();

return 0;
}