二叉树的学习笔记01

发布于 / 笔记 / 2 条评论

二叉树的递归定义如下:二叉树要么为,要么由根节点左子树右子树构成,而左子树和右子树分别是一棵二叉树。树和二叉树类似,区别是每个节点不一定只有两棵子树。

对于一个节点k,其左子节点和右子节点的编号分别是2k2k+1。二进制下可以十分明显地看出节点之间的父子关系。


构建二叉树

构建一个二叉树有很多种方法。其中常用的方法有数组法结构体+指针法等。

数组法就是简单地将数据存储在一个数组中,通过操作数字来访问和操作数据。例如:访问节点k的父节点则访问tree[k>>1]等。通常适用于小数据的题目(大数据也开不起来那么大的

结构体+指针法也是一个比较常用的方法,它通过构建一个节点,用指针来记录左右子节点或者父节点(按照具体需要构建类)。

一种可能的构建方法:

class Node
{
public:
	Node():data(0), left_child(NULL), right_child(NULL) {}
	
	int data;
	Node *left_child, *right_child;
	
};

Node *root;

Node* newnode()//新建节点
{
	return new Node();
}

void remove_tree(Node *u)//从一个节点删除子树
{
	if (!u) return ;
	remove_tree(u->left_child);
	remove_tree(u->right_child);

	delete u;
	return ;
}

遍历二叉树

层次遍历二叉树

即按层次从根节点开始向下逐层遍历二叉树(即BFS)。一种可能的做法是,使用一个队列来完成这个任务。初始时放入根节点,然后每次取出一个节点,就把他的左右子节点(如果存在)放进队列。

void bfs()
{
	queue<Node*> q;
	q.push(root);
	while(!q.empty())
	{
		Node* u = q.front();
		q.pop();

		if (u->left_child) q.push(u->left_child);
		if (u->right_child) q.push(u->right_child);
	}
}

先/中/后序遍历二叉树

对于二叉树T,可以递归定义它的先序遍历中序遍历后序遍历:

Pre(T) { T_root => Pre(T.left) => Pre(T.right) }
In(T) { In(T.right) => T_root => In(T.right) }
Post(T) { Post(T.left) => Post(T.right) => T_root }

即,三种遍历的不同点在于访问根节点的次序。例如,在如下所示的二叉树中

示例二叉树

先序遍历访问顺序:D B A C E G F

中序遍历访问顺序:A B C D E F G

后序遍历访问顺序:A C B F G E D

需要知道的两点性质:对于任一二叉树,先序遍历的第一个节点即其根节点,后序遍历的最后一个节点是其根节点。

由这点性质可知:根据三种顺序的中序遍历和任意一种遍历一起可以还原出一棵二叉树。因为可以从先序或者后序找到根和子树的根,然后根据中序遍历推出当前树的子树,直到还原完成。

以上,是冻葱重新学习二叉树的第一篇笔记。

转载原创文章请注明,转载自: 冻葱Tewi » 二叉树的学习笔记01
  1. 一个不愿意透露姓名的孙正阳

    冻葱NB!!!!(破音

    1. 冻葱Tewi
      @一个不愿意透露姓名的孙正阳 Σ