二叉樹(shù)小結(jié)
樹(shù)
樹(shù)是一種由有限個(gè)數(shù)的節(jié)點(diǎn)組成的數(shù)據(jù)結(jié)構(gòu)，它有以下特點(diǎn)：
- 根節(jié)點(diǎn)只有一個(gè)。
- 每個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)（即父節(jié)點(diǎn)）只有一個(gè)。
- 每個(gè)節(jié)點(diǎn)可以有任意數(shù)量的后驅(qū)節(jié)點(diǎn)（即子樹(shù)節(jié)點(diǎn)）。
二叉樹(shù)是一種特殊的樹(shù)，它的每個(gè)節(jié)點(diǎn)只有兩個(gè)后驅(qū)節(jié)點(diǎn)。二叉搜索樹(shù)又是一種特殊的二叉樹(shù)，它除了有二叉樹(shù)的特點(diǎn)外，還有：
- 如果根節(jié)點(diǎn)的左子樹(shù)不為空，則左子樹(shù)上每個(gè)節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值，且左子樹(shù)也是一棵二叉搜索樹(shù)，以此類(lèi)推。
- 如果根節(jié)點(diǎn)的右子樹(shù)不為空，則右子樹(shù)上每個(gè)節(jié)點(diǎn)的值大于根節(jié)點(diǎn)的值，且右子樹(shù)也是一棵二叉搜索樹(shù)，以此類(lèi)推。
實(shí)現(xiàn)二叉搜索樹(shù)
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
struct TreeNode
{
int val;
SearchTree left;
SearchTree right;
};
Position Find(int x, SearchTree root)
{
if (!root)
{
return NULL;
}
else
{
if (root->val == x)
{
return root;
}
else
{
if (root->val > x)
{
return Find(x, root->left);
}
else
{
return Find(x, root->right);
}
}
}
}
Position FindMin(SearchTree root)
{
if (root == NULL)
{
return NULL;
}
else
{
if (root->left == NULL)
{
return root;
}
else
{
return FindMin(root->left);
}
}
}
Position FindMax(SearchTree root)
{
if (root == NULL)
{
return NULL;
}
else
{
if (root->right == NULL)
{
return root;
}
else
{
return FindMin(root->right);
}
}
}
SearchTree insertNode(int x, SearchTree root)
{
if (root == NULL)
{
SearchTree node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node->val = x;
node->left = NULL;
node->right = NULL;
return node;
}
else
{
if (x < root->val)
{
root->left = insertNode(x, root->left);
}
else
{
root->right = insertNode(x, root->right);
}
}
return root;
}
SearchTree deleteNode(int x, SearchTree root)
{
Position temp;
if (x < root->val)
{
root->left = deleteNode(x, root->left);
}
else if (x > root->val)
{
root->right = deleteNode(x, root->right);
}
else
{
if (root->left && root->right)
{
temp = FindMin(root->right);
root->val = temp->val;
root->right = deleteNode(root->val, root->right);
}
else
{
temp = root;
if (root->left == NULL)
{
root = root->right;
}
else if (root->right == NULL)
{
root = root->left;
}
free(temp);
}
}
}
//前序遍歷
void preOrder(SearchTree root)
{
if (root)
{
printf("val:%d \n", root->val);
if (root->left)
{
preOrder(root->left);
}
if (root->right)
{
preOrder(root->right);
}
}
}
//中序遍歷
void inOrder(SearchTree root)
{
if (root)
{
if (root->left)
{
inOrder(root->left);
}
printf("val:%d \n", root->val);
if (root->right)
{
inOrder(root->right);
}
}
}
//后續(xù)遍歷
void postOrder(SearchTree root)
{
if (root)
{
if (root->left)
{
postOrder(root->left);
}
if (root->right)
{
postOrder(root->right);
}
printf("val:%d \n", root->val);
}
}
void main()
{
SearchTree tree = (struct TreeNode *)malloc(sizeof(struct TreeNode));
tree->val=10;
tree->left=NULL;
tree->right=NULL;
insertNode(3,tree);
insertNode(15,tree);
insertNode(5,tree);
insertNode(2,tree);
insertNode(11,tree);
insertNode(18,tree);
insertNode(1,tree);
printf("preorder:\n");
preOrder(tree);
printf("inorder:\n");
inOrder(tree);
printf("postorder:\n");
postOrder(tree);
}
關(guān)于遍歷
對(duì)于二叉樹(shù)，主要的遍歷方式有3種：
前序遍歷
方法是先處理當(dāng)前節(jié)點(diǎn)，再處理左右子樹(shù)。
//前序遍歷
void preOrder(SearchTree root)
{
if (root)
{
printf("val:%d \n", root->val);
if (root->left)
{
preOrder(root->left);
}
if (root->right)
{
preOrder(root->right);
}
}
}
前序遍歷算法示例：
- 合并二叉樹(shù)
給定兩個(gè)二叉樹(shù)，想象當(dāng)你將它們中的一個(gè)覆蓋到另一個(gè)上時(shí)，兩個(gè)二叉樹(shù)的一些節(jié)點(diǎn)便會(huì)重疊。
你需要將他們合并為一個(gè)新的二叉樹(shù)。合并的規(guī)則是如果兩個(gè)節(jié)點(diǎn)重疊，那么將他們的值相加作為節(jié)點(diǎn)合并后的新值，否則不為 NULL 的節(jié)點(diǎn)將直接作為新二叉樹(shù)的節(jié)點(diǎn)。
來(lái)源：LeetCode
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2){
if(!t1&&!t2)
{
return NULL;
}
else if(t1&&!t2)
{
return t1;
}
else if(!t1&&t2)
{
return t2;
}
else
{
//先處理當(dāng)前節(jié)點(diǎn)，再處理左右子樹(shù)
t1->val=t1->val+t2->val;
t1->left=mergeTrees(t1->left,t2->left);
t1->right=mergeTrees(t1->right,t2->right);
return t1;
}
}
中序遍歷
先遍歷左子樹(shù)，再處理當(dāng)前節(jié)點(diǎn)，最后處理右子樹(shù)。
//中序遍歷
void inOrder(SearchTree root)
{
if (root)
{
if (root->left)
{
inOrder(root->left);
}
printf("val:%d \n", root->val);
if (root->right)
{
inOrder(root->right);
}
}
}
中序遍歷算法示例：
- 合法二叉搜索樹(shù)
實(shí)現(xiàn)一個(gè)函數(shù)，檢查一棵二叉樹(shù)是否為二叉搜索樹(shù)。
來(lái)源:LeetCode
二叉搜索樹(shù)的特點(diǎn)是中序遍歷呈遞增狀態(tài)，可以中序遍歷并存入數(shù)組，判斷數(shù)組是否遞增即可。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int idx=0;
int getLength(struct TreeNode* root)
{
if(!root)
{
return 0;
}
else
{
int len=1;
return len+getLength(root->left)+getLength(root->right);
}
}
void push(struct TreeNode* root,int* arr)
{
if(root)
{
push(root->left,arr);
arr[idx++]=root->val;
push(root->right,arr);
}
else
{
return;
}
}
bool isValidBST(struct TreeNode* root){
int len = getLength(root);
if(len<=1)
{
return true;
}
int* arr = (int *)malloc(sizeof(int)*len);
idx = 0;
push(root,arr);
for(int i=1;i<len;i++)
{
if(arr[i-1]>=arr[i])
{
free(arr);
return false;
}
}
free(arr);
return true;
}
后序遍歷
先處理左右子樹(shù)，最后處理當(dāng)前節(jié)點(diǎn)。
//后續(xù)遍歷
void postOrder(SearchTree root)
{
if (root)
{
if (root->left)
{
postOrder(root->left);
}
if (root->right)
{
postOrder(root->right);
}
printf("val:%d \n", root->val);
}
}
后序遍歷算法示例：
- 二叉樹(shù)剪枝
給定二叉樹(shù)根結(jié)點(diǎn) root ，此外樹(shù)的每個(gè)結(jié)點(diǎn)的值要么是 0，要么是 1。
返回移除了所有不包含 1 的子樹(shù)的原二叉樹(shù)。
( 節(jié)點(diǎn) X 的子樹(shù)為 X 本身，以及所有 X 的后代。)
來(lái)源：LeetCode
根據(jù)左右子樹(shù)的處理結(jié)果處理當(dāng)前節(jié)點(diǎn)。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void deleteNode(struct TreeNode* root)
{
if(root)
{
deleteNode(root->left);
deleteNode(root->right);
if(root->left&&root->left->left==NULL&&root->left->right==NULL&&root->left->val==0)
{
root->left=NULL;
}
if(root->right&&root->right->left==NULL&&root->right->right==NULL&&root->right->val==0)
{
root->right=NULL;
}
}
}
struct TreeNode* pruneTree(struct TreeNode* root){
if(!root)
{
return NULL;
}
else
{
deleteNode(root);
}
return root;
}
