二叉树理论基础
二叉树种类:
1. 满二叉树
如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。节点数量2^k-1,k是深度。
2. 完全二叉树
在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^(h-1) 个节点。比如优先级队列实际上是堆,堆即为完全二叉树,同时保证父子节点顺序关系。
3.二叉搜索树(logn)
二叉搜索树是一个有序树,对布局没要求,对顺序有要求。若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。
4.平衡二叉搜索树(AVL)
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。插入是log(n)搜索也是log(n)。map和set的底层就是平衡二叉搜索树,因此元素有序。注意unordered_set或unordered_map是用哈希表实现。
二叉树存储方式
1.链式存储
用指针实现。通过左指针和右指针指向下一个子节点。
2.顺序存储
用数组实现。如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。
更常使用链式存储,但要清楚如何用数组实现。
二叉树的遍历方式
深度优先搜索:先一直往下遍历,直到触底进行回退,前中后序搜索都属于深度优先搜索。可以用递归法(用栈)或者迭代法(非递归,用队列)。
广度优先搜索:一层层或者一圈圈进行遍历,二叉树中层序遍历就是广度优先搜索。层序遍历就是迭代法,使用队列实现。
前序遍历:中左右
中序遍历:左中右
后续遍历:左右中
二叉树的定义方式
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) :val(x),left(NULL),right(NULL)
};
递归遍历
1.确认递归函数的参数和返回值
2.确定终止条件
3.确定单层递归的逻辑
前序遍历
void traversal(*cur,vector<int> &num){
if(cur==NULL)
return;
num.push_back(cur->val);
traversal(cur->left,num);
traversal(cur->right,num);
}
中序遍历
void traversal(*cur,vector<int> &num){
if(cur==NULL)
return;
traversal(cur->left,num);
num.push_back(cur->val);
traversal(cur->right,num);
}
后序遍历
void traversal(*cur,vector &num){
if(cur==NULL)
return;
traversal(cur->left,num);
traversal(cur->right,num);
num.push_back(cur->val);
}
完成了144.145.94三道分别是前后中序遍历的题目。
迭代遍历
前序遍历
前序遍历是中左右,使用stack先把中push,然后pop,再把右push,左push,这样弹出即为中左右。记得中间check一下node是否为null
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode *> st;
vector<int> result;
if(root==NULL)
return result;
st.push(root);
while(!st.empty()){
TreeNode *Node=st.top();
st.pop();
if(Node!=NULL)
{
result.push_back(Node->val);
st.push(Node->right);
st.push(Node->left);
}
}
return result;
}
后序遍历
后序遍历是左右中,可以在前序遍历的基础上,变成中右左,最后再reverse数组变成左右中。
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode *> st;
vector<int> result;
if(root==NULL)
return result;
st.push(root);
while(!st.empty()){
TreeNode *Node=st.top();
st.pop();
if(Node!=NULL)
{
result.push_back(Node->val);
st.push(Node->left);
st.push(Node->right);
}
}
reverse(result.begin(),result.end());
return result;
}
中序遍历
中序遍历是左中右,需要先一直到最底的左节点,直到左节点不存在,通过st.top()找到中间节点,取值弹出再接着遍历右节点。
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
TreeNode* cur=root;
while(cur!=NULL||!st.empty())
{
if(cur!=NULL)
{
st.push(cur);
cur=cur->left;
}
else
{
cur=st.top();
st.pop();
result.push_back(cur->val);
cur=cur->right;
}
}
return result;
}
统一迭代
统一迭代是通过在访问过的节点后放空指针的方式进行标记,暂时搁置。