二叉树的基本数据结构

1
2
3
4
5
6
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

新建二叉树

先序创建二叉树

例:123##4##56###

1
2
3
4
5
6
7
8
9
10
11
12
void createTree(TreeNode* &head) {
char ch;
cin >> ch;
if (ch == '#') {
head = nullptr;
}
else {
head = new TreeNode(ch - '0');
createTree(head->left);
createTree(head->right);
}
}

先序遍历

递归版

1
2
3
4
5
6
7
8
void preorderRecur(TreeNode* head) {
if (!head) {
return;
}
cout << head->val << " ";
preorderRecur(head->left);
preorderRecur(head->right);
}

非递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void preorderUnRecur(TreeNode* head) {
if (head) {
stack<TreeNode*> stack;
stack.push(head);
while (!stack.empty()) {
head = stack.top();
stack.pop();
cout << head->val << " ";
if (head->right) {
stack.push(head->right);
}
if (head->left) {
stack.push(head->left);
}
}
}
cout << endl;
}

中序遍历

递归版

1
2
3
4
5
6
7
8
void inorderRecur(TreeNode* head) {
if (!head) {
return;
}
inorderRecur(head->left);
cout << head->val << " ";
inorderRecur(head->right);
}

非递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void inorderUnRecur(TreeNode* head) {
if (head) {
stack<TreeNode*> stack;
while (!stack.empty() || head) {
if (head) {
stack.push(head);
head = head->left;
}
else {
head = stack.top();
stack.pop();
cout << head->val << " ";
head = head->right;
}
}
cout << endl;
}
}

后序遍历

递归版本

1
2
3
4
5
6
7
8
void posorderRecur(TreeNode* head) {
if (!head) {
return;
}
posorderRecur(head->left);
posorderRecur(head->right);
cout << head->val << " ";
}

非递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void posorderReRecur(TreeNode* head) {
if (head) {
stack<TreeNode*> s1;
stack<TreeNode*> s2;
s1.push(head);
while (!s1.empty()) {
head = s1.top();
s1.pop();
s2.push(head);
if (head->left) {
s1.push(head->left);
}
if (head->right) {
s1.push(head->right);
}
}
while (!s2.empty()) {
cout << s2.top()->val << " ";
s2.pop();
}
cout << endl;
}
}

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void levelOrderUnRecur(TreeNode* head) {
queue<TreeNode*> queue;
queue.push(head);
while (!queue.empty()) {
head = queue.front();
queue.pop();
cout << head->val << " ";
if (head->left) {
queue.push(head->left);
}
if (head->right) {
queue.push(head->right);
}
}
cout << endl;
}

树的深度

1
2
3
4
5
6
7
8
9
10
int treeDepth(TreeNode* head) {
if (!head) {
return 0;
}
else {
int m = treeDepth(head->left);
int n = treeDepth(head->right);
return m > n ? m + 1 : n + 1;
}
}

树的节点的个数

1
2
3
4
5
6
7
8
int treeNodeNums(TreeNode* head) {
if (!head) {
return 0;
}
else {
return treeNodeNums(head->left) + treeNodeNums(head->right) + 1;
}
}

树中叶子节点的个数

1
2
3
4
5
6
7
8
9
10
11
int treeLeftNums(TreeNode* head) {
if (!head) {
return 0;
}
if (!head->left && !head->right) {
return 1;
}
else {
return treeLeftNums(head->left) + treeLeftNums(head->right);
}
}

树从根节点到每个叶子节点的路径及距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void getAllPath(TreeNode* head, vector<int>& path, int pathLen) {
int i;
if (head) {
//path[pathLen] = head->val;
path.push_back(head->val);
if (!head->left && !head->right) {
for (i = 0; i <= pathLen; ++i) {
cout << path[i] << " ";
}
cout << endl;
}
else {
getAllPath(head->left, path, pathLen + 1);
path.pop_back();
getAllPath(head->right, path, pathLen + 1);
path.pop_back();
}
}
}

树的度为1的节点个数

1
2
3
4
5
6
7
8
9
10
11
int treeNode_1_Nums(TreeNode* head) {
if (!head) {
return 0;
}
if ((!head->left && head->right) || (head->left && !head->right)) {
return 1 + treeNode_1_Nums(head->left) + treeNode_1_Nums(head->right);
}
else {
return treeNode_1_Nums(head->left) + treeNode_1_Nums(head->right);
}
}

查找值为e的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
TreeNode* searchNode(TreeNode* head, int elem) {
if (!head) {
return nullptr;
}
stack<TreeNode*> stack;
stack.push(head);
while (!stack.empty()) {
head = stack.top();
stack.pop();
if (head->val == elem) {
cout << "find it!" << endl;
return head;
}
if (head->right) {
stack.push(head->right);
}
if (head->left) {
stack.push(head->left);
}
}
cout << "can't find it!" << endl;
}

树中插入一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void insertNode(TreeNode* head, int elem) {
queue<TreeNode*> queue;
queue.push(head);
while (!queue.empty()) {
head = queue.front();
queue.pop();
if (!head->left) {
TreeNode* node = new TreeNode(elem);
head->left = node;
break;
}
else {
queue.push(head->left);
}
if (!head->right) {
TreeNode* node = new TreeNode(elem);
head->right = node;
break;
}
else {
queue.push(head->right);
}
}
}

二叉搜索树的构建

二叉搜索树使用中序遍历可以得到递增的序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void createSearchTree(TreeNode* &head, int elem) {
if (!head) {
head = new TreeNode(elem);
return;
}
else {
if (elem < head->val) {
createSearchTree(head->left, elem);
}
else if (elem > head->val) {
createSearchTree(head->right, elem);
}
else {
cout << "已存在!" << endl;
return;
}
}
}

二叉搜索树的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TreeNode* findNodeInSearchTree(TreeNode* head, int elem) {
if (!head) {
cout << "cne't find!" << endl;
return head;
}
if (head->val > elem) {
findNodeInSearchTree(head->left, elem);
}
if (head->val < elem) {
findNodeInSearchTree(head->right, elem);
}
if (head->val == elem) {
cout << "find!" << endl;
return head;
}
}

二叉搜索树插入一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insertNodetoSearchTree(TreeNode* &head, int elem) {
if (!head) {
cout << "插入成功" << endl;
head = new TreeNode(elem);
return;
}
if (head->val > elem) {
insertNodetoSearchTree(head->left, elem);
}
if (head->val < elem) {
insertNodetoSearchTree(head->right, elem);
}
if (head->val == elem) {
cout << "已存在,插入失败" << endl;
return;
}
}

二叉搜索树删除一个节点

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
TreeNode* findMin(TreeNode* head) {
if (head) {
while (head->left) {
if (head->left) {
head = head->left;
}
}
}
return head;
}

TreeNode* deleteNodeInSearchTree(TreeNode* &head, int elem) {
TreeNode* temp = nullptr;
if (!head) {
cout << "没有此节点!" << endl;
}
else if (head->val > elem) {
head->left = deleteNodeInSearchTree(head->left, elem);
}
else if (head->val < elem) {
head->right = deleteNodeInSearchTree(head->right, elem);
}
else {
//有两个子节点
if (head->left && head->right) {
temp = findMin(head->right);
head->val = temp->val;
head->right = deleteNodeInSearchTree(head->right, head->val);
}
else {
temp = head;
if (!head->left) {
head = head->right;
}
else if (!head->right) {
head = head->left;
}
delete temp;
}
}
return head;
}