二叉树基本操作上

二叉树的概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的二叉树组成
二叉树特点：

• 每个结点最多有两棵子树，即二叉树不存在度大于2的结点
• 二叉树的子树有左右之分，其子树的次序不能颠倒

因此：二叉树是通过上述形式的组合或嵌套而形成

满二叉树&完全二叉树

• 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子节点都在同一层上
• 完全二叉树：如果一棵具有N个结点的二叉树的结构与满二叉树的前N个结点的结构相同，称为完全二叉树

二叉树的性质

• 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有
  (i>0)个结点
• 若规定只有根节点的二叉树的深度为1，则深* 度为K的二叉树的最大
  结点数是(k>=0)
• 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数
  为 n2,则有n0＝n2＋1
• 具有n个结点的完全二叉树的深度k为上取整
  对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序
• 对所有节点从0开始编号，则对于序号为i的结点有：
  1.若i>0，双亲序号：(i-1)/2；
  i=0，i为根节点编号，无双亲结点
  2.若2i+1n,右孩子序号：2i+1,否则无右孩子

二叉树的存储结构

二叉树主要有顺序存储和链式存储结构

• 顺序存储结构
  对于一棵完全二叉树所有结点按照层序自顶向下，同一层自左向右顺
  序编号，就得到一个节点的顺序序列
  1.优点：存储完全二叉树，简单省空间
  2.缺点：存储一般二叉树尤其单支树，存储空间利用不高
• 链式存储

  struct BinTreeNode
  {
  struct BinTreeNode* _pLeft; // 当前节点左孩子
  struct BinTreeNode* _pRight; // 当前节点右孩子
  DataType _data; // 当前节点值域
  };

二叉树基本操作

二叉树的创建

typedef int DataType;

typedef struct BTreeNode
{
	DataType data;
	struct BTreeNode *LeftChild;
	struct BTreeNode *RightChild;
} BTreeNode;

//二叉树的初始化
void BTreeInit(BTreeNode *root)
{
	root->data = 0;
	root = NULL;
}

//创建结点
BTreeNode * CreateNode(DataType data)
{
	BTreeNode *node = (BTreeNode *)malloc(sizeof(BTreeNode));
	node->data = data;
	node->LeftChild = node->RightChild = NULL;

	return node;
}

//创建二叉树
BTreeNode * CreateBTree( int arr[],int size,int *pUsedSize)
{
	if (size <= 0)
	{
		*pUsedSize = 0;
		return NULL;
	}
	int leftUse, rightUse;
	int data = arr[0];
	if (data == -1)
	{
		*pUsedSize = 1;
		return NULL;
	}

	BTreeNode *root = CreateNode(data);

	root->LeftChild = CreateBTree(arr + 1,size - 1,&leftUse);
	root->RightChild = CreateBTree(arr + 1+leftUse, size - leftUse - 1,&rightUse);

	*pUsedSize = leftUse + rightUse + 1;

	return root;
}

二叉树的遍历

遵循某种次序，遍历二叉树中的所有节点，使得每个结点被访问一次，而且仅访问一次。“访问”：即对结点施行某些操作。
若规定VLR分别代表：遍历根节点、遍历根节点的左子树、遍历根节点的右子树，则有：
前序：VLR
中序：LVR
后序：LRV
前序遍历递归算法

//先序遍历
void PreOrderTraverse(BTreeNode *root)
{
	if (root == NULL)
	{
		return;
	}

	printf("%d ",root->data);
	PreOrderTraverse(root->LeftChild);
	PreOrderTraverse(root->RightChild);
}

中序遍历递归算法

//中序遍历
void InOrderTraverse(BTreeNode *root)
{
	if (root == NULL)
	{
		return;
	}

	InOrderTraverse(root->LeftChild);
	printf("%d ", root->data);
	InOrderTraverse(root->RightChild);
}

后序遍历递归算法

//后序遍历
void  LastOrderTraverse(BTreeNode *root)
{
	if (root == NULL)
	{
		return;
	}

	LastOrderTraverse(root->LeftChild);
	LastOrderTraverse(root->RightChild);
	printf("%d ", root->data);
}

二叉树的其他操作：

　1. 求二叉树的高度

#define MAX(a,b) ((a)>(b)?(a):(b))
int GetHight(BTreeNode *root)
{
	if (root ==NULL)
	{
		return 0;
	}

	return MAX(GetHight(root->LeftChild) ,GetHight(root->RightChild)) + 1;
}

　2. 求二叉树叶子结点的个数

int GetLeafNum(BTreeNode *root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		if (root->LeftChild == NULL && root->RightChild == NULL)
		{
			return 1;
		}
		else
			return GetLeafNum(root->LeftChild) + GetLeafNum(root->RightChild);
	}
}

　3. 求二叉树结点的个数

//方法一
int count;
int GetNodeNum(BTreeNode *root)
{
	if (root == NULL)
	{
		return 0;
	}
	GetNodeNum(root->LeftChild);
	GetNodeNum(root->RightChild);
	count++;
	return count;
}

//方法二
int GetNodeNum2(BTreeNode *root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = GetNodeNum2(root->LeftChild);
	int right = GetNodeNum2(root->RightChild);

	return left + right + 1;
}

1. 求二叉树第K层结点的个数

   int GetLevelKNum(BTreeNode *root,DataType k)
   {
   	assert(k>=1);
   
   	if (root == NULL)
   	{
   		return 0;
   	}
   	if (k == 1)
   	{
   		return 1;
   	}
   	DataType left = GetLevelKNum(root->LeftChild, k-1);
   	DataType right = GetLevelKNum(root->RightChild, k-1);
   
   	return left + right;
   }

　5. 判断一个节点是否在一棵二叉树中

BTreeNode * FindNode(BTreeNode *root,DataType data)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == data)
	{
		return root;
	}

	BTreeNode *result1 = FindNode(root->LeftChild,data);
	BTreeNode *result2 = FindNode(root->LeftChild, data);

	return result1 == NULL ? result1 : result2;
}