定义结构体:
typedef int BTDatatype;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode *left;
struct BinaryTreeNode *right;
BTDatatype data;
}BTNode;
前序构建二叉树的结点;
前序遍历二叉树;
中序遍历二叉树;
后序遍历二叉树;
求二叉树的结点,叶子节点,第K层结点数,查找结点,树的深度。
对于上列问题,都可以用递归求解,因为一棵非空二叉树都有一个根,一个左子树,一个右子树。对于这种特性,可以将问题化为子问题。
前序遍历二叉树画图说明:
代码如下:
int BTreeDepth(BTNode *root)//求树的深度
{
if (root == NULL)
return 0;
//将问题化为子问题,求树的高度也就是求左子树高度和右子树高度最大值
if (BTreeDepth(root->left) > BTreeDepth(root->right))
return BTreeDepth(root->left)+1;
else //如果相等,也可以返回右子树高度
return BTreeDepth(root->right)+1;
}
BTNode *BTreeFind2(BTNode *root, BTDatatype x)//查找结点
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode *ret = NULL;
ret = BTreeFind2(root->left, x);
if (ret)//在左边找到,就不用在右结点找,直接返回
return ret;
//在左边没有找到
ret= BTreeFind2(root->right, x);
if (ret)//在右边找到
return ret;
else //如果在一颗树的右边没有找到,那这棵树就没有该节点,就可以返回
return NULL;
}
BTNode *ret = NULL;
BTNode *BTreeFind1(BTNode *root, BTDatatype x)//查找结点
{
if ((root) == NULL)
return NULL ;
if (root->data == x)
ret=root;
//查找左子树和右字树
else {
BTreeFind1(root->left,x);
BTreeFind1(root->right, x);
}
return ret;
}
int BTreeKLevelsize(BTNode *root, int k)//求第k层结点数
{
//求解二叉树第K层节点数目,使用递归解法,
//第k层的节点数 = 第k - 1层左孩子节点数 + 第k - 1层右孩子节点数目,
//直到k == 1时,说明已经到了第K层。
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BTreeKLevelsize(root->left, k -1) + BTreeKLevelsize(root->right, k - 1);
}
int BTtreeLeafSize(BTNode *root)//树叶子结点数
{
if (root == NULL)
return 0;
if (root->left == NULL&&root->right == NULL)
return 1;
return BTtreeLeafSize(root->left) + BTtreeLeafSize(root->right);
}
int BTtreeSize(BTNode *root)//树一共结点数
{//将问题化为子问题,结点数等于1+左子树结点数+右子树结点数
if (root == NULL)
return 0;
return 1 + BTtreeSize(root->left) + BTtreeSize(root->right);
}
void BTtreePostOreder(BTNode *root)//后根遍历
{
if (root)
{
BTtreePostOreder(root->left);
BTtreePostOreder(root->right);
printf("%d ", root->data);
}
return;
}
void BTtreeInOreder(BTNode *root)//中根遍历
{
if (root)
{
BTtreeInOreder(root->left);
printf("%d ", root->data);
BTtreeInOreder(root->right);
}
return;
}
void BTtreePrevOreder(BTNode *root)//前序遍历
{
if (root)
{
printf("%d ", root->data);
BTtreePrevOreder(root->left);
BTtreePrevOreder(root->right);
}
return;
}
BTNode *BuyBTNode(BTDatatype x)//构建树的结点
{
BTNode *tree = (BTNode *)malloc(sizeof(BTNode));
tree->data = x;
tree->left = NULL;
tree->right = NULL;
return tree;
}
BTNode *CreateBTTree(BTDatatype *a, int sz, int *pIndex, BTDatatype invalid)
{//invalid代表表示空的字符
assert(a);
BTNode *root = NULL;
if ((*pIndex) < sz)
{
if (a[*pIndex] != invalid)
{
root = BuyBTNode(a[*pIndex]);
(*pIndex)++;
root->left = CreateBTTree(a, sz, pIndex, invalid);
(*pIndex)++;
root->right = CreateBTTree(a, sz, pIndex, invalid);
}
}
return root;
}
void TestBinaryTree(){
BTNode *root = NULL;
BTDatatype a[] = { 1,2,3,'#',4,'#','#',5,6,'#','#','#' };
int pIndex = 0;
int sz = sizeof(a) / sizeof(a[0]);
root = CreateBTTree(a, sz, &pIndex, '#');
BTtreePrevOreder(root);//前序
printf("\n");
BTtreeInOreder(root);//中序
printf("\n");
BTtreePostOreder(root);//后序
printf("\n");
printf("树的结点数:%d\n", BTtreeSize(root));//树的结点数
printf("树的叶子结点数:%d\n", BTtreeLeafSize(root));//树叶子结点数
int k = 4;
printf("第%d层结点数:%d\n", k,BTreeKLevelsize(root, k));//求第k层结点数
printf("%d\n", BTreeFind1(root, 6)->data);//查找结点
printf("%d\n", BTreeFind2(root, 3)->data);//查找结点
printf("%d\n", BTreeFind2(root, 4)->data);//查找结点
printf("树的高度:%d\n",BTreeDepth(root));}