二叉树
1. 二叉树
- 空树
- 非空：根节点，根节点的左子树、根节点的右子树组成的。
1.1 二叉树的遍历
从二叉树的定义来看，二叉树是递归定义的，因此我们可以用递归的形式来遍历二叉树。
1.1.1二叉树前中后序遍历（递归版）
访问根结点的顺序不同。
//先序遍历 void PreOrder(BTNode* root) { if (root == NULL) { printf("* "); return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); } //中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("* "); return; } PreOrder(root->left); printf("%d ", root->data); PreOrder(root->right); } //后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("* "); return; } PreOrder(root->left); PreOrder(root->right); printf("%d ", root->data); }
1.1.2 层序遍历
层序遍历是按照二叉树的高度，一层一层遍历，需要借助队列来完成。但是C语言没有这样的数据结构，需要我们自己来提前写一个。（本例子不提供队列的实现）
//层序遍历 void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); //根节点入队 if (root) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { //先获取队首元素，再出队，左右孩子不为空，入队 BTNode* front = QueueFront(&q); QueuePop(&q); if (front->left) { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } printf("%d ", front->data); } QueueDestroy(&q); }
1.2 二叉树的其他相关接口
1.2.1 求二叉树的结点数量
//求二叉树的结点数量 int NodeSize(BTNode* root) { if (root == NULL) return 0; return 1+NodeSize(root->left)+NodeSize(root->right); }
1.2.2 求叶子结点个数
//求叶子结点个数 int LeafSize(BTNode* root) { //防止空树 if (root == NULL) return 0; //是叶子 if (root->left == NULL && root->right == NULL) return 1; //不是叶子 return LeafSize(root->left)+LeafSize(root->right); }
1.2.3 求树高
//求树高 int TreeDepth(BTNode* root) { //避免空树 if (root == NULL) return 0; int depth_left = 1 + TreeDepth(root->left); int depth_right = 1 + TreeDepth(root->right); return depth_left > depth_right ? depth_left : depth_right; }
1.2.4 求第k层结点个数
//求第k层结点个数 int BinaryTreeLevelKSize(BTNode* root,int k) { //空树 if (root == NULL) return 0; if (k == 1) return 1; int count = BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); return count; }
1.2.5 查找二叉树值为k的结点
//查找二叉树值为x的结点 BTNode* BinaryTreeFind(BTNode* root, int x) { //防止二叉树为空 if (root == NULL) return NULL; if (root->data == x) return root; BTNode* ret1 = BinaryTreeFind(root->left, x); if (ret1 != NULL) return ret1; BTNode* ret2 = BinaryTreeFind(root->right, x); if (ret2 != NULL) return ret2; return NULL; }
文章知识点与官方知识档案匹配，可进一步学习相关知识
