数据结构:链式二叉树

对于二叉树而言,如果不是完全二叉树,就不再适合用数组存储了

二叉树结构

typedef struct BinTreeNode
{
	int val;
	struct BinTreeNode* left;
	struct BinTreeNode* right;
}BTNode;

二叉树的遍历

                顺序                                访问顺序(n = NULL)

1.前序      根,左子树,右子树        1 2 3 n n n 4 5 n n 6 n n

2.中序      左子树,根,右子树        n 3 n 2 n 1 n 5 n 4 n 6 n 

3.后序      左子树,右子树,根        n n 3 n 2 n n 5 n n 6 4 1

4.层序                                         1 2 4 3 5 6 

1.前序遍历

通过递归,可以将一颗树拆解为许多棵树(直到root为空为止),是根就访问,不是,就向下走

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
    printf("%d\n", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}

2.中序遍历

同理,是左子树(该左子树不能有任何其他子树,否则就是根),就访问,不是就向下

void InOrder(BTNode* root)
{
	
	if (root == NULL)
	{
		return;
	}
	PreOrder(root->left);
	printf("%d\n", root->val);
	
	PreOrder(root->right);
}

3.后序遍历

同理

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PreOrder(root->left);
	PreOrder(root->right);
	printf("%d\n", root->val);
}

4.求二叉树的大小

通过递归,将所有左子树和右子树节点遍历,再加上根本身,就是总节点数,它的本质是二叉树的后序遍历(走完根后结束)(必须将左右子树全部走完才能求出树的大小,因此一定是后序)

int TreeSize(BTNode* root)
{

	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

5.求第k层的节点个数

分割子问题 : 从第一层起的第k层的节点个数 = 第二层起的第k - 1层的节点个数

一直递归,每递归一次,k - 1,第k层时k = 1

int TreeLevel(BTNode* root, int k)
{
	asssert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	//不为空且k>0说明第k层的节点再子树里
	return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1);
}

6.查找值为x的节点

注意:要保证函数存在返回值

BTNode* TreeFind(BTNode* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->val == x)
	{
		return root;
	}
	//在左树中找,找到返回
	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1 != NULL)
	{
		return ret1;
	}
	//在右树中找,找到返回
	BTNode* ret2 = TreeFind(root->right, x);
	if (ret2 != NULL)
	{
		return ret2;
	}
	//树中没有x节点
	return NULL;
}