二叉树（三）

一、二叉树的遍历

二叉树遍历是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。

1.前序遍历（先根遍历）

前序遍历（Preorder Traversal也叫先序遍历）——根、左子树、右子树。属于DFS（深度优先遍历）。空用N表示。

// 前序遍历空用N表示
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->_data);PrevOrder(root->_left);PrevOrder(root->_right);
}// 前序遍历不打印空
void PrevOrder(BTNode* root)
{if (root){printf("%d ", root->_data);PrevOrder(root->_left);PrevOrder(root->_right);}
}

2.中序遍历（中根遍历）

中序遍历（Inorder Traversal）——左子树、根、右子树。空用N表示。

// 中序遍历空用N表示
void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->_left);printf("%d ", root->_data);InOrder(root->_right);
}

3.后序遍历（后根遍历）

后序遍历（Postorder Traversal）——左子树、右子树、根。空用N表示。

// 后序遍历空用N表示
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->_left);PostOrder(root->_right); printf("%d ", root->_data);
}

4.层序遍历

设二叉树的根结点所在层数为1，层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。层序遍历是非递归遍历。属于BFS（广度优先遍历）。

需要用到队列的代码，可以将之前写的代码拷贝过来（源代码->添加->现有项）。

// 层序遍历
#include"Queue.h"
void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->_data);if (front->_left)QueuePush(&q, front->_left);if (front->_right)QueuePush(&q, front->_right);}QueueDestroy(&q);
}

其中Queue.h文件中要修改：

typedef struct BinaryTreeNode* QDataType;//要使用原生类型

二、二叉树结点个数

// 二叉树结点个数（错误示范）
int TreeSize(BTNode* root)
{static int size = 0;//静态if (root == NULL)return 0;else++size;TreeSize(root->_left);TreeSize(root->_right);return size;//打印结果会累加
}

正确写法：递归遍历思路

// 二叉树结点个数，方法一
int size = 0;
int TreeSize(BTNode* root)
{if (root == NULL)return 0;else++size;TreeSize(root->_left);TreeSize(root->_right);return size;
}
int main()
{BTNode* root = CreatBinaryTree();size = 0;printf("二叉树结点个数：%d\n", TreeSize(root));size = 0;printf("二叉树结点个数：%d\n", TreeSize(root));return 0;
}// 二叉树结点个数，方法二
int TreeSize(BTNode* root, int* psize)
{if (root == NULL)return 0;else++(*psize);TreeSize(root->_left, psize);TreeSize(root->_right, psize);return *psize;//可以不要返回值
}
int main()
{BTNode* root = CreatBinaryTree();int size = 0;printf("二叉树结点个数：%d\n", TreeSize(root, &size));size = 0;printf("二叉树结点个数：%d\n", TreeSize(root, &size));return 0;
}

分治（分而治之）递归思路：

// 二叉树结点个数，方法三
int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->_left) + TreeSize(root->_right) + 1;
}
int main()
{BTNode* root = CreatBinaryTree();printf("TreeSize:%d\n", TreeSize(root));return 0;
}

三、二叉树叶子结点个数

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);
}

四、二叉树高度

为空是0，不为空就是左子树高度和右子树高度中大的加1。

//方法一：
int fmax(int x, int y)
{return x > y ? x : y;
}
int TreeHeight(BTNode* root)
{if (root == NULL)return 0;return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}

//方法二：
int TreeHeight(BTNode* root)
{if (root == NULL)return 0;int leftHeight = TreeHeight(root->_left);int rightHeight = TreeHeight(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

 LCR 175. 计算二叉树的深度 - 力扣（LeetCode）下面代码OJ过不了，效率问题

//OJ不能通过
int TreeHeight(BTNode* root)
{if (root == NULL)return 0;return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

五、二叉树第k层节点个数

int TreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;// 子问题return TreeLevelKSize(root->_left, k - 1) + TreeLevelKSize(root->_right, k - 1);
}

六、二叉树查找值为x的节点

若有多个值为x的节点，返回第一次找到的节点，因为找到值为x的节点就不会再往下找了（若左子树找到值为x的节点，就不会再找右子树的节点）。

BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->_data == x)return root;BTNode* ret1 = TreeFind(root->_left, x);if (ret1)return ret1;BTNode* ret2 = TreeFind(root->_right, x);if (ret2)return ret2;return NULL;
}

七、二叉树的销毁

如果是空树，不需要销毁。

使用后序遍历，先销毁左子树，在销毁右子树，最后释放根结点。

void TreeDestory(BTNode* root)
{if (root == NULL)return;TreeDestory(root->_left);TreeDestory(root->_right);free(root);
}

八、判断二叉树是否是完全二叉树

①层序遍历走，空也进队列；

②遇到第一个空节点时，开始判断，后面全空就是完全二叉树，后面有非空就不是完全二叉树。

bool TreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);// 遇到第一个空，就可以开始判断，如果队列中还有非空，就不是完全二叉树if (front == NULL){break;}QueuePush(&q, front->_left);QueuePush(&q, front->_right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);// 如果有非空，就不是完全二叉树if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

九、二叉树链式结构的实现

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;
BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->_data = x;node->_left = NULL;node->_right = NULL;return node;
}
BTNode* CreatBinaryTree()
{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;return node1;
}
// 前序遍历空用N表示
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->_data);PrevOrder(root->_left);PrevOrder(root->_right);
}
// 中序遍历空用N表示
void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->_left);printf("%d ", root->_data);InOrder(root->_right);
}
// 后序遍历空用N表示
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->_left);PostOrder(root->_right); printf("%d ", root->_data);
}
// 二叉树结点个数
int TreeSize(BTNode* root)
{return root == NULL ? 0 : 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);
}
// 二叉树的高度：为空是0，不为空就是左子树高度和右子树高度大的加1
int TreeHeight(BTNode* root)
{if (root == NULL)return 0;int leftHeight = TreeHeight(root->_left);int rightHeight = TreeHeight(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
// 二叉树第k层节点个数
int TreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;return TreeLevelKSize(root->_left, k - 1) + TreeLevelKSize(root->_right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->_data == x)return root;BTNode* ret1 = TreeFind(root->_left, x);if (ret1)return ret1;//return TreeFind(root->_right, x);BTNode* ret2 = TreeFind(root->_right, x);if (ret2)return ret2;return NULL;
}
// 二叉树销毁
void TreeDestory(BTNode* root)
{if (root == NULL)return;TreeDestory(root->_left);TreeDestory(root->_right);free(root);
}
// 层序遍历
#include"Queue.h"
void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->_data);if (front->_left)QueuePush(&q, front->_left);if (front->_right)QueuePush(&q, front->_right);}QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
bool TreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);// 遇到第一个空，就可以开始判断，如果队列中还有非空，就不是完全二叉树if (front == NULL){break;}QueuePush(&q, front->_left);QueuePush(&q, front->_right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);// 如果有非空，就不是完全二叉树if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}
int main()
{BTNode* root = CreatBinaryTree();PrevOrder(root);printf("\n"); InOrder(root);printf("\n");PostOrder(root);printf("\n");printf("TreeSize:%d\n", TreeSize(root));printf("TreeLeafSize:%d\n", TreeLeafSize(root));printf("TreeHeight:%d\n", TreeHeight(root));printf("TreeLevelKSize:%d\n", TreeLevelKSize(root, 3));TreeLevelOrder(root);printf("\n");TreeComplete(root);TreeDestory(root);root = NULL;return 0;
}