树的结构
一棵二叉树又三个部分组成:
- 根节点
- 左子树
- 右子树
我们将树的结构定义如下:
class TreeNode{
public:
int val;
TreeNode*left;
TreeNode*right;
int height;
TreeNode(int x):val(x),left(nullptr),right(nullptr),height(1){};
TreeNode(): TreeNode (0){};
};
因此当我们需要遍历一棵二叉树时,有四种遍历方法:
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
前序遍历
遍历顺序:根节点->左子树->右子树
void preOrder(TreeNode*root){
if(!root)return;
Process(root);
preOrder(root->left);
preOrder(root->right);
}
中序遍历
遍历顺序:左子树->根节点->右子树
void inOrder(TreeNode*root){
if(!root)return;
inOrder(root->left);
Process(root);
inOrder(root->right);
}
后序遍历
遍历顺序:左子树->右子树->根节点
void latOrder(TreeNode*root){
if(!root)return;
latOrder(root->left);
latOrder(root->right);
Process(root);
}
层序遍历
遍历顺序:逐层 层序遍历相对比较复杂,我们需要用一个队列来记录所有同层的节点然后依次遍历
void layerOrder(TreeNode*root){
if(!root)return;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()) {
TreeNode *f = q.front ();
if ( f->left )q.push (f->left);
if ( f->right )q.push (f->right);
Process (f);
q.pop ();
}
}
我们不难发现,所谓的 X序遍历 就是根节点在顺序中的位置
二叉树本身就是递归的定义的,所以我们可以得知,二叉树算法中最重要的一点就是递归。
树的性质
满二叉树
满二叉树指的是深度为n的树,n-1层全为满的并且第n层的子节点都是连续的。
完全二叉树
满二叉树是完全二叉树的一种特殊情形,指的是对于每个节点,左子树与右子树的高度之差绝对值不大于1.完全二叉树常常被用于二叉查找树,它可以在$O(logn)$的时间找到目标。
一般二叉树
对于深度为n的一棵二叉树,节点个数在$n$至$2^n-1$之间。 同理,对于节点个数为n的二叉树,深度在$log(n+1)$至$n$之间。
标签:遍历,TreeNode,right,二叉树,root,节点 From: https://blog.51cto.com/deltamaya/6167489