二叉树相关(C语言描述)

60 阅读 0 评论 40 点赞

我是靠谱客的博主苹果小懒虫，最近开发中收集的这篇文章主要介绍二叉树相关(C语言描述)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二叉树和递归有着妙不可言的联系，这篇文章会有着不断的递归，递归往往代码简单，但是十分难想
首先给出二叉树的结构

//二叉树的数据结构
typedef char Elem;
typedef struct BNode {
	Elem _data;
	struct BNode* _left;
	struct BNode* _right;
}BNode;

以前序遍历的方式建立二叉树

如果字符不为‘#’,创建结点,并给数据,然后创建左子树,在创建右子树
这里应该注意int一定要传入指针,如果不传入指针,递归压栈的时候,压入的int还是原来的int,并不会连续改变p的值

BNode* CreateBinaryTree(char* src, int * p) {
	if (src[*p] != '#') {
		BNode* root = (BNode*)malloc(sizeof(BNode));
		root->_data = src[*p];
		++(*p);
		root->_left = CreateBinaryTree(src, p);
		++(*p);
		root->_right = CreateBinaryTree(src, p);
		return root;
	} else {
		return NULL;
	}
}

前后中序的非递归遍历

以前序遍历为例:如果该节点不为空,打印该根节点,
再遍历左子树,再遍历右子树

//前序遍历
void BinaryTreePrevOrder(BNode* root) {
	if (root) {
		printf("%c ", root->_data);
		BinaryTreePrevOrder(root->_left);
		BinaryTreePrevOrder(root->_right);
	} else {
		printf("# ");
	}
}

//中序遍历
void BinaryTreeInOrder(BNode* root) {
	if (root) {
		BinaryTreeInOrder(root->_left);
		printf("%c ", root->_data);
		BinaryTreeInOrder(root->_right);
	} else {
		printf("# ");
	}
}

//后序遍历
void BinaryTreePostOrder(BNode* root) {
	if (root) {
		BinaryTreePostOrder(root->_left);
		BinaryTreePostOrder(root->_right);
		printf("%c ", root->_data);
	} else {
		printf("# ");
	}
}

在这里插入图片描述
二叉树的销毁函数

这里值得一说的是二级指针的必要性，虽然一级指针可以起到销毁的作用，但是并没有更改root的指向，通过二级指针直接修改外部指针的内容
如下图：

void DeleteBinaryTree(BNode** root) {
	BNode* curRoot = *root;
	if (curRoot) {
		DeleteBinaryTree(&curRoot->_left);
		DeleteBinaryTree(&curRoot->_right);
		free(curRoot);
		*root = NULL;
	}
}

二叉树结点个数

int BinaryTreeSize(BNode* root) {
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->_left) + 
		BinaryTreeSize(root->_right) + 1;
}

二叉树叶子结点个数

int BinaryTreeLeafSize(BNode* root) {
	if (root == NULL)
		return 0;
	//root为叶子结点
	if (root->_left == NULL && root->_right == NULL) {
		return 1;
	}
	return BinaryTreeLeafSize(root->_left) + 
		BinaryTreeLeafSize(root->_right);
}

第K层结点个数

int BinaryTreeLevelKSize(BNode* root, int k) {
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->_left, k - 1) + 
		BinaryTreeLevelKSize(root->_right, k - 1);
}

查找结点

BNode* BinaryTreeFind(BNode* root, elem x) {
	BNode * ret;
	//空树，没有找到
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;
	ret = BinaryTreeFind(root->_left, x);
	if (ret)
		return ret;
	ret = BinaryTreeFind(root->_right, x);
	if (ret)
		return ret;
	return NULL;
}

判断两棵树是否相同

int isSameTree(BNode* p, BNode* q) {
	if (p == NULL && q != NULL)
		return 0;
	if (p != NULL && q == NULL)
		return 0;
	if (p == NULL && q == NULL)
		return 1;

	if (p->_data == q->_data)
		return isSameTree(p->_left, q->_left)
		&& isSameTree(p->_right, q->_right);
	else
		return 0;

}

判断一个树是否为另一个树的子树
leetcode链接:另一个树的子树

int isSubtree(BNode* s, BNode* t) {
	if (s == NULL)
		return 0;

	//根相同，判断当前这个树是否和t相同
	if (s->_data == t->_data && isSameTree(s, t))
		return 1;
	return isSubtree(s->_left, t)
		|| isSubtree(s->_right, t);
}

二叉树的深度

int maxDepth(BNode* root) {
        if (root == NULL)
            return 0;
        return fmax(maxDepth(root->left), 
        		maxDepth(root->right)) + 1;
    }

判断是否为一棵平衡二叉树
leetcode链接: 平衡二叉树

bool _isBalanced(TreeNode* root, int* curDepth) {
        if (root == NULL) {
            //空树高度为0
            *curDepth = 0;
            return true;
        }
        int leftDepth = 0, rightDepth = 0;
        if (_isBalanced(root->left, &leftDepth)
           && _isBalanced(root->right, &rightDepth)
           && abs(leftDepth - rightDepth) < 2) {
            //当前树的高度max(leftDepth, rightDepth)
            *curDepth = max(leftDepth, rightDepth) + 1;
            return true;
        } else 
            return false;
    }
    
    bool isBalanced(TreeNode* root) {
        int depth = 0;
        return _isBalanced(root, &depth);
    }

判断是否为对称二叉树
leetcode链接：对称二叉树

bool _isSymmetric(TreeNode* left, TreeNode* right) {
        if (left == NULL && right == NULL)
            return true;
        if (left == NULL || right == NULL) 
            return false;
        return left->val == right->val
                && _isSymmetric(left->left, right->right)
                && _isSymmetric(left->right, right->left);
    }
    
    bool isSymmetric(TreeNode* root) {
        if (root == NULL)
            return true;
        return _isSymmetric(root->left, root->right);
    }