前提

关于二叉树的创建有问题的可以参考下面这个文章

二叉树的创建--五种方法

目录

目录

目录

🍖二叉树结点个数

🍖中序遍历

🍖后序遍历

🍖求二叉树高度

🍖查找二叉树结点

🍖查找二叉树的父节点

🍖克隆二叉树

🍖判断两个二叉树是否相等

---

🍖二叉树结点个数

int Size(BinTree t)
{
	assert(t);
	if (t == NULL){
		return 0;
	}
	else{
//左子树的个数+右子树的个数+根节点
		return Size(t->leftChild) + Size(t->rightChild) + 1;
	}
}

🍖先序遍历

//先序遍历
void BinTreeVLR(BinTree t)
{
	assert(t);
	if (t != NULL){
		printf("%c", t->data);//先输出根结点
		BinTreeVLR(t->leftChild);
		BinTreeVLR(t->rightChild);
	}
}

🍖中序遍历

//中序遍历
void BinTreeLVR(BinTree t)
{
	assert(t);
	if (t != NULL){		
		BinTreeLVR(t->leftChild);
        printf("%c", t->data);//先递归完左子树再输出
		BinTreeLVR(t->rightChild);
	}
}

🍖后序遍历

//后序遍历
void BinTreeLRV(BinTree t)
{
	assert(t);
	if (t != NULL){
		BinTreeLRV(t->leftChild);
		BinTreeLRV(t->rightChild);
		printf("%c", t->data);//遍历完左子树和右子树再输出
	}
}

🍖求二叉树高度

int Height(BinTree t)
{
	if (t == NULL)
		return 0;
	else
//树的高度是指从根节点到距根节点最远的那个结点之间的层数，先判断左子树和右子树哪个高度更大，取大的那个，再加上根节点那一层
		return 1 + Height(t->leftChild) > Height(t->rightChild) ? Height(t->leftChild) : Height(t->rightChild);
}

🍖查找二叉树结点

//查找
BinTreeNode *BinTreeFind(BinTree t, BTElemType key)
{
	if (t == NULL||t->data == key)//二叉树为空或是根节点就是所要找的目标值，直接返回t
		return t;
	BinTreeNode *p = BinTreeFind(t->leftChild,key);//在左子树里面找
	if (p != NULL)//如果p不为空，则代表在左子树里已经找到了目标值
		return p;
	return BinTreeFind(t->rightChild,key);//否则在右子树里找
}

🍖查找二叉树的父节点

//查找父节点
BinTreeNode *BinTreeParent(BinTree t, BinTreeNode *p)
{
	if (t == NULL || p==NULL||t->data==p->data)
		return NULL;
	if (t->leftChild == p || t->rightChild == p)
		return t;
	BinTreeNode *pt = BinTreeParent(t->leftChild, p);
	if (pt != NULL)
		return pt;
	return BinTreeParent(t->rightChild, p);

}

🍖克隆二叉树

//克隆二叉树
BinTreeNode *BinTreeClone(BinTree t)
{
	if (t == NULL)
		return NULL;
	else
	{
		BinTreeNode *bt = (BinTreeNode*)malloc(sizeof(BinTreeNode));
		assert(bt != NULL);
		bt->data = t->data;
		bt->leftChild = BinTreeClone(t->leftChild);
		bt->rightChild = BinTreeClone(t->rightChild);
		return bt;
	}
}

🍖判断两个二叉树是否相等

bool Equal(BinTree t1, BinTree t2)
{
	if (t1 == NULL && t2 == NULL){
		return true;
	}
	if ((t1 == NULL || t2 == NULL)){
		return false;
	}
	return (t1->data == t2->data) && Equal(t1->leftChild, t2->leftChild) && Equal(t1->rightChild, t2->rightChild);
}