2.4树的高度及二叉树第K层的节点个数
2.4.1树的高度（TreeHeight）：
设根节点的层数为1。
当只有一层的时候，左子树为0，右子树为0层，总层数为 1层。
当有2层时，左子树为1，右子树为1层，总层数为1+1层。
当有3层时，左子树为2，右子树为2层，总层数为2+1层。
....
当有N层时，左子树为N-1层，右子树为N1层，总层数为（N-1）+1层。
- 这样就可以将树的高度看成较高子树的层高+1（根节点的那一层）。因此将左右子树的层数计算出来，让他们较大的一个+1就是二叉树的高度了。
//树的高度 int TreeHeight(BTNode* root) { if (root == NULL) return 0; int left = TreeHeight(root->left); int right = TreeHeight(root->right); return left > right ? left+1 : right+1; }
2.4.2二叉树第K层的节点个数（TreeLevelSize）：
可以通过左右子树，让他们可下降k-1层，就到达了第k层
如果到了第k层就说明节点就是第k层的其中一个节点就返回1就好了。
如果为NULL，就返回0。
// 二叉树第k层节点个数 int TreeLevelSize(BTNode* root, int k) { if (root == NULL) return 0; if (k == 1 )//当k==1时，刚好是第三层 return 1; return TreeLevelSize(root->left, k - 1) + TreeLevelSize(root->right, k - 1); }
2.5二叉树查找值为x的节点（TreeFind）：
依旧不断通过左子树和右子树分别遍历下去
找到等于x的值，就返回那个节点的地址
遇到NULL时，返回NULL
当全部找完依旧没找到，那就返回NULL。
// 二叉树查找值为x的节点 BTNode* TreeFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->data == x) return root; BTNode* left = TreeFind(root->left,x); if (left) return left; BTNode* right = TreeFind(root->right, x); if (right) return right; return NULL; }
2.6层序遍历（LevelOrder）：
这里需要用到队列，不懂队列可以先看看另外一篇博客：http://t.csdn.cn/sLlHK
这里就直接使用队列了。
- 先让根节点进入队列
- 将队头用一个变量保存下来，如果不为NULL就将其打印
- 再将队头pop一下
- 当左右节点存在，就将其push进去队列，以此循环
//层序遍历 void LevelOrder(BTNode* root) { Queue q; QInit(&q); if (root) { QPush(&q, root); } while (!QEmpty(&q)) { BTNode* front = QFront(&q); printf("%d ", front->data); QPop(&q); if (front->left) QPush(&q, front->left); if (front->right) QPush(&q, front->right); } printf("\n"); QDestroty(&q); }
2.7判断二叉树是否是完全二叉树及二叉树销毁
2.7.1判断二叉树是否是完全二叉树（BinaryTreeComplete）
这个是建立在层序遍历的基础上的，利用层序遍历，遍历到第一个NULL时，后面都不能为NULL才为完全二叉树，如果后面有一个不能为NULL，那就不是完全二叉树返回false。
// 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue q; QInit(&q); if (root) { QPush(&q, root); } while (!QEmpty(&q)) { BTNode* front = QFront(&q); QPop(&q); if (front == NULL) { break; } else { QPush(&q,front->left); QPush(&q,front->right); } } while (!QEmpty(&q)) { BTNode* front = QFront(&q); QPop(&q); if (front != NULL) { QDestroty(&q); return false; } } QDestroty(&q); return true; }
2.7.2二叉树销毁（TreeDestory）：
// 二叉树销毁 void TreeDestory(BTNode* root) { if (root == NULL) return; TreeDestory(root->left); TreeDestory(root->right); free(root); }
3.完整代码：
3.1test.c文件(二叉树实现):
#include"Queue.h" #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyBTNode(BTDataType x) { BTNode*newnode=(BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->left = newnode->right = NULL; return newnode; } // 二叉树前序遍历 void PreOrder(BTNode* root) { //assert(root); if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); } // 二叉树中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } // 二叉树后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); } // 二叉树节点个数 int TreeSize(BTNode* root) { if (root == NULL) return 0; return TreeSize(root->left) + TreeSize(root->right) + 1; } // 二叉树叶子节点个数 int TreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return TreeLeafSize(root->left) + TreeLeafSize(root->right); } //树的高度 int TreeHeight(BTNode* root) { if (root == NULL) return 0; int left = TreeHeight(root->left); int right = TreeHeight(root->right); return left > right ? left+1 : right+1; } // 二叉树第k层节点个数 int TreeLevelSize(BTNode* root, int k) { if (root == NULL) return 0; if (k == 1 )//当k==1时，刚好是第三层 return 1; return TreeLevelSize(root->left, k - 1) + TreeLevelSize(root->right, k - 1); } // 二叉树查找值为x的节点 BTNode* TreeFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->data == x) return root; BTNode* left = TreeFind(root->left,x); if (left) return left; BTNode* right = TreeFind(root->right, x); if (right) return right; return NULL; } //层序遍历 void LevelOrder(BTNode* root) { Queue q; QInit(&q); if (root) { QPush(&q, root); } while (!QEmpty(&q)) { BTNode* front = QFront(&q); printf("%d ", front->data); QPop(&q); if (front->left) QPush(&q, front->left); if (front->right) QPush(&q, front->right); } printf("\n"); QDestroty(&q); } // 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue q; QInit(&q); if (root) { QPush(&q, root); } while (!QEmpty(&q)) { BTNode* front = QFront(&q); QPop(&q); if (front == NULL) { break; } else { QPush(&q,front->left); QPush(&q,front->right); } } while (!QEmpty(&q)) { BTNode* front = QFront(&q); QPop(&q); if (front != NULL) { QDestroty(&q); return false; } } QDestroty(&q); return true; } // 二叉树销毁 void TreeDestory(BTNode* root) { if (root == NULL) return; TreeDestory(root->left); TreeDestory(root->right); free(root); } void test1() {//构造二叉树 BTNode* n1 = BuyBTNode(1); BTNode* n2 = BuyBTNode(2); BTNode* n3 = BuyBTNode(3); BTNode* n4 = BuyBTNode(4); BTNode* n5 = BuyBTNode(5); BTNode* n6 = BuyBTNode(6); BTNode* n7 = BuyBTNode(7); n1->left = n2;//链接二叉树 n1->right = n4; n2->left = n3; n4->left = n5; n4->right = n6; n3->left = n7; printf("前序遍历顺序："); PreOrder(n1); printf("\n"); printf("中序遍历顺序："); InOrder(n1); printf("\n"); printf("后序遍历顺序："); PostOrder(n1); printf("\n"); printf("Treesize:%d\n", TreeSize(n1)); printf("TreeHeight:%d\n", TreeHeight(n1)); printf("TreeLevelSize:%d\n", TreeLevelSize(n1,3)); printf("TreeFind:%d\n", TreeFind(n1, 3)->data); LevelOrder(n1); printf("是否是完全二叉树：%d", BinaryTreeComplete(n1)); TreeDestory(n1); n1 = NULL; } //void test2() //{ // BTNode* n1 = BuyBTNode(1); // BTNode* n2 = BuyBTNode(1); // BTNode* n3 = BuyBTNode(1); // BTNode* n4 = BuyBTNode(1); // BTNode* n5 = BuyBTNode(1); // //BTNode* n6 = BuyBTNode(1); // BTNode* n7 = BuyBTNode(1); // n1->left = n2; // n1->right = n3; // n2->left = n4; // n2->right = n5; // n3->right = n7; //} int main() { test1(); //test2(); return 0; }
3.2Queue.h文件：
#pragma once #include<stdio.h> #include<assert.h> #include<stdbool.h> #include<stdlib.h> //前置声明 struct BinaryTreeNode; typedef struct BinaryTreeNode* QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; void QInit(Queue* pq); void QDestroty(Queue* pq); void QPush(Queue* pq, QDataType x); void QPop(Queue* pq); QDataType QFront(Queue* pq); QDataType QBack(Queue* pq); bool QEmpty(Queue* pq); int QSize(Queue* pq);
3.3Queue.c文件：
#include"Queue.h" void QInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; pq->size = 0; } void QDestroty(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); } pq->head = pq->tail = NULL; } void QPush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail==NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QPop(Queue* pq) { assert(pq); assert(!QEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = NULL; pq->tail = NULL; } else { QNode* del = pq->head; pq->head = pq->head->next; free(del); del = NULL; } pq->size--; } QDataType QFront(Queue* pq) { assert(pq); assert(!QEmpty(pq)); return pq->head->data; } QDataType QBack(Queue* pq) { assert(pq); assert(!QEmpty(pq)); return pq->tail->data; } bool QEmpty(Queue* pq) { assert(pq); return pq->head == NULL && pq->tail == NULL; } int QSize(Queue* pq) { assert(pq); return pq->size; }
