数据结构 - 二叉树基础
树是一种数据结构，二叉树是应用非常广泛的一种。其特点为：每个节点的子节点不超过两个。
一般情况下，使用链表来建立二叉树。
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
在完美二叉树的情况下，也可以使用数组来构造，同循环数组一样，也是通过数学的方式寻找下标：
left-child-index = 2i + 1;
right-child-index = 2i + 2;
搜索二叉树
搜索二叉树相当于二分查找法，使用 即可找到指定的元素。
所有左子节点小于或等于父节点，所有右子节点大于父节点.
搜索二叉树的优势除了搜索，插入和删除的时间复杂度也是一样。
节点的构造
struct BstNode* GetNewNode(int data)
{
struct BstNode* newNode = (struct BstNode*)malloc(sizeof(struct Node*));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
当二叉树是NULL的时候，将调用该函数生成只用一个节点二叉树，root = GetNewNode(data);
插入节点
struct BstNode* Insert(struct BstNode* root, int data)
{
if (root == NULL)
{
root = GetNewNode(data);
return root;
}
else if (root->data >= data)
{
root->left = Insert(root->left, data); // 递归
}
else
{
root->right = Insert(root->right, data); // 递归
}
return root;
}
当插入的值小于或等于递归调用传入的参数为左，当插入的值大于时递归调用传入的参数在右。
搜索节点
bool Search(struct BstNode* root, int data)
{
if(root == NULL)
return false;
else if(root->data == data)
return true;
else if(data <= root->data)
return Search(root->left, data);
else
return Search(root->right, data);
}
同插入一样，递归调用查询。
找出最大值或最小值
利用二叉树左值越来越小，右值越来越大。可以很轻松的就找出其中的最大值和最小值。
因为是一直往左或者右找，使用遍历和递归都可以实现。这里最小值使用遍历,最大值使用递归。
int FindMin(struct BstNode* root)
{
if(root == NULL)
{
printf("Error: Tree is emoty.\n");
return -1;
}
while(root->left != NULL)
{
root = root->left;
}
return root->data;
}
这里传入的root是一个局部变量，所以可以直接遍历它，一直遍历到为NULL返回该值即可。
int FindMax(struct BstNode* root)
{
if(root == NULL)
{
printf("Error: Tree is emoty.\n");
return -1;
}
else if(root->right == NULL)
{
return root->data;
}
return FindMax(root->right);
}
遍历的话要考虑退出条件，这里的退出条件和遍历差不多，也是找到NULL为止。
二叉树的高度
深度和高度的区别：
-
深度：某节点的深度指的是从根节点到该节点的最长路径。 -
高度：该节点到叶子节点的最长路径。
树的高度和深度一致，对于兄弟节点，深度应该一致，高度不一定。
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
int max(int i, int j)
{
return (i > j) ? i : j;
}
int FindHeight(struct Node* root)
{
if(root == NULL)
return -1;
return max(FindHeight(root->left),FindHeight(root->right)) + 1;
}
// leftHeight = FindHeight(root->left);
// rightHeight = FindHeight(root->right);
// return max(leftHeight, rightHeight) + 1;
注意最后的加1,递归结束一次就加一次。
二叉树的遍历
-
广度优先: 一行一行。 -
深度优先: 一列一列。
广度优先，层次遍历。
void LevelOrder(struct Node* root)
{
if(root == NULL)
return;
queue<Node*> Q;
Q.push(root);
while*!Q.emoty())
{
Node* current = Q.front();
cout<<current->data<<" ";
if(current->left != NULL) Q.push(current->left);
if(current->right != NULL) Q.push(current->right);
Q.pop();
}
}
深度优先 前序，中序和后序遍历
数据的访问顺序：
-
前序 data->left->right先数据 -
中序 left->data->right中数据 -
后序 left->right->data后数据
前序
void Preorder(struct Node* root)
{
if(root == NULL)
return;
printf("%d", root->data);
Preorder(root->left);
Preorder(root-right);
}
中序
void Inorder(struct Node* root)
{
if(root == NULL)
return;
Preorder(root->left);
printf("%d", root->data);
Preorder(root-right);
}
后序
void Postorder(struct Node* root)
{
if(root == NULL)
return;
Preorder(root->left);
printf("%d", root->data);
Preorder(root-right);
}
删除一个节点
对于二叉树，删除的节点是叶子节点和只有一个子节点的节点很容易，只需把删除或者跳过它，再回收内存即可。但是对于有两个子节点的节点就麻烦一些了。父节点应该链接哪一个节点呢？
struct Node* Delete(struct Node* root, int data)
{
if(root == NULL)
return root;
else if(data < root->data) root->left = Delete(roo->left,data);
else if(data > root->data) root->right = Delete(root->right, data);
slse
{
// 叶子节点
if(root->left == NULL && root->right ==NULL)
{
free(root);
root = NULL;
return root;
}
// 只有一个子节点
else if(root->left == NULL)
{
struct Node* temp = root;
root = root->right;
free(temp);
}
else if(return->right == NULL)
{
struct Node* temp = root;
root = root->left;
free(temp);
}
// 两个节点
else
{
struct Node* temp = FindMin(root->right);
root->data = temp->data;
root->right = Delete(root->right, temp->data);
}
}
return root;
}