一、简单创建一个二叉树
直接简单创建二叉树
typedef int BTDataType; typedef struct BinayrTree { struct BinayrTree* left; struct BinayrTree* right; BTDataType val; }BTNode; BTNode* BuyNode(int x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail\n"); exit(-1); } node->val = x; node->left = NULL; node->right = NULL; return node; } BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6;
二、二叉树遍历
1、前序遍历（深度优先遍历）
递归思想实现
void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) return; printf("%d ",root->val); BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); }
2、中序遍历
递归思想实现
可以参考：前序遍历上的图
void BinaryTreeInOrder(BTNode* root) { if (root == NULL) return; BinaryTreePrevOrder(root->left); printf("%d ", root->val); BinaryTreePrevOrder(root->right); }
3、后序遍历
递归思想实现
可以参考：前序遍历上的图
void BinaryTreePostOrder(BTNode* root) { if (root == NULL) return; BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); printf("%d ", root->val); }
4、层序遍历（广度优先遍历）
队列思想实现
void Levelorder(BTNode* root) { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); printf("%d ", front->val); if(root->left) QueuePush(&q, root->left); if(root->right) QueuePush(&q, root->right); QueuePop(&q); } printf("\n"); QueueDestory(&q); }
三、二叉树结点问题
1、二叉树叶子结点个数
递归解法：
（1）如果二叉树为空，返回0
（2）如果二叉树不为空且左右子树为空，返回1
（3）如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数
int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); }
2、二叉树总结点数
递归解法：
（1）如果二叉树为空，节点个数为0
（2）如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
int BinaryTreeSize(BTNode* root) { return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; }
3、第k层的结点数
递归解法：
（1）如果二叉树为空或者k<1返回0
（2）如果二叉树不为空并且k==1，返回1
（3）如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和
int TreeLevel(BTNode* root, int k) { assert(k > 0); if (root == NULL) { return 0; } if (k == 1) { return 1; } return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1); }
四、二叉树查找值为x的节点
（1）遍历二叉树即可，当发现与该值相等时返回该结点
（2）若没有则返回NULL
BTNode* TreeFind(BTNode* root, int x) { if (root == NULL) { return NULL; } if (root->val == x) { return root; } BTNode* a = NULL; a = TreeFind(root->left, x); if(a) return a; a = TreeFind(root->right,x); if (a) return a; return NULL; }
五、求二叉树深度
递归解法：
（1）如果二叉树为空，二叉树的深度为0
（2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1
int TreeHight(BTNode* root) { if (root == NULL) return 0; int leftHight = TreeHight(root->left); int rightHight = TreeHight(root->right); return leftHight > rightHight ? leftHight+1 : rightHight+1 ; }
六、判断是否为完全二叉树
通过层序遍历从上往下，从左往右将每一个节点（包括非空节点）都放到队列里，在出队列的过程中，如果遇到空节点，判断队列中剩下的元素是否有非空节点，若有非空节点则该树不是完全二叉树；若全是空节点，则该树为完全二叉树。
int TreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); if (front == NULL) break; QueuePush(&q, front->left); QueuePush(&q, front->right); QueuePop(&q); } // 已经遇到空节点，如果队列中后面的节点还有非空，就不是完全二叉树 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front != NULL) { QueueDestory(&q); return false; } } QueueDestory(&q); return true; }
七、二叉树销毁
递归销毁
void BinaryTreeDestory(BTNode* root) { if (root == NULL) return; BinaryTreeDestory(root->left); BinaryTreeDestory(root->right); free(root); }
最后在主函数中
node1 = NULL;
