树的结构

一棵二叉树又三个部分组成：

• 根节点
• 左子树
• 右子树

我们将树的结构定义如下：

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$之间。