数据结构--二叉树

1.二叉树链式结构的实现

1.1 前置说明

1.2 二叉树的遍历

1.2.1 前序、中序以及后序遍历

1.2.2 层序遍历及判断是否为完全二叉树

1.3 节点个数，叶子节点个数，第k层节点个数以及高度等

1.4 二叉树的创建和销毁

1.二叉树链式结构的实现

1.1 前置说明

这时直接创建的二叉树，方便于各个接口函数的测试，当然你也可以选择1.4的方法直接创建。
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}TreeNode;TreeNode* BuyTreeNode(int x)
{TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));assert(node);node->data = x;node->left = NULL;node->right = NULL;return node;
}
TreeNode* CreateTree()
{TreeNode* node1 = BuyTreeNode(1);TreeNode* node2 = BuyTreeNode(2);TreeNode* node3 = BuyTreeNode(3);TreeNode* node4 = BuyTreeNode(4);TreeNode* node5 = BuyTreeNode(5);TreeNode* node6 = BuyTreeNode(6);TreeNode* node7 = BuyTreeNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;node5->right = node7;return node1;
}
再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：
        1. 空树
        2. 非空：根节点，根节点的左子树、根节点的右子树组成的。

        从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

1.2 二叉树的遍历

1.2.1 前序、中序以及后序遍历

         学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
        1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
        2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。
        3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

下面主要分析前序递归遍历，中序与后序图解类似，可以自己画画看。

        （1.）**前序遍历**，也称为**深度优先遍历**。它从根节点开始，递归地访问左子树，然后访问右子树。二叉树的前序遍历是按以下顺序访问节点的序列： 1. 根节点 2. 根节点的左子树 3. 根节点的右子树

        当左边递归到空时，会从叶子节点开始依次返回递归的结果，然后开始遍历右子树，递归迭代。
前序遍历递归图解：

前序遍历的代码：
void PrevOrder(TreeNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}
前序遍历结果为：1 2 3 4 5 6

（2.)**中序遍历**。它从根节点开始，递归地访问左子树，然后访问当前节点，然后访问右子树。二叉树的中序遍历是按以下顺序访问节点的序列： 1. 当前节点的左子树 2. 当前节点 3. 当前节点的右子树

中序遍历代码：
void InOrder(TreeNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}
中序遍历的结果：3 2 1 5 4 6

（3.）**后序遍历**。它从根节点开始，递归地访问左子树，然后访问右子树，最后访问根节点。二叉树的后序遍历是按以下顺序访问节点的序列： 1. 左子树的所有节点 2. 右子树的所有节点 3. 根节点

后序遍历代码：
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PrevOrder(root->left);PrevOrder(root->right);printf("%d ", root->data);
}
前序遍历结果为：3 2 5 6 4 1

1.2.2 层序遍历及判断是否为完全二叉树

层序遍历（又称广度优先遍历）：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

实现层序遍历，我们可以用到队列，A进入队列，可以去到B和C的地址，让A出队就能取到A的数据，然后通过B可以取到D、通过C可以取到E，F，让他们依次入队出队，就能取到每一层的节点，最后队列为空就结束
void LevelOrder(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);int levelSize = 1;while (!QueueEmpty(&q)){// 一层一层出while (levelSize--){TreeNode* front = QueueFront(&q);QueuePop(&q);//这里pop掉了front也能取到，因为这只是pop掉了指向节点的指针//并没有真的把节点pop掉了printf("%d ", front->data);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}printf("\n");levelSize = QueueSize(&q);}printf("\n");QueueDestroy(&q);
}
判断是否为完全二叉树

在层序遍历的基础上，我们稍作修改就可以了。我们再出队列的过程中，如果遇到了NULL，那我们就break，然后去判断NULL的后面是否有数据，如果NULL的后面还有数据，那么这就不是一个完全二叉树。
bool TreeComplete(TreeNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);int levelSize = 1;while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}// 前面遇到空以后，后面还有非空就不是完全二叉树while (!QueueEmpty(&q)){TreeNode* front = QueueFront(&q);QueuePop(&q);if (front)//判断是否为NULL，不是NULL返回false{QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

1.3 节点个数，叶子节点个数，第k层节点个数以及高度等

接口函数
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
1.二叉树节点的个数

我们用分治的思想，依次遍历左右两子树，如果不是空则+1
int TreeSize(TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) +TreeSize(root->right) + 1;
}
2.叶子节点的个数

叶子节点的特征就是，左孩子右孩子都为空，则视为叶子节点，分别遍历两个子树的叶子节点，是叶子节点就返回1。
int treeleafsize(TreeNode* root)
{//空返回0if (root == NULL)return 0;//是叶子返回1if ((root->left == NULL) &&(root->right == NULL))return 1;//非0也不是叶子，那继续往下找叶子//分治 叶子=左+右return treeleafsize(root->left) +treeleafsize(root->right);
}
3.第k层的节点个数

同样的，这里我们也用分治的思想。我们引入了变量k，我们从第一层开始，如果k不等于1的话，我就进行k-1的操作，直到k=1就到达了指定层数，k=1那么节点数就+1，统计每次递归到k=1的节点，就得到了第k层的节点数。
int lvksize(TreeNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1){return 1;}return lvksize(root->left, k - 1) + lvksize(root->right, k - 1);
}
4.二叉树查找值为x的节点

节点的查找不再是简单的遍历，我们递归一次就要保存一次递归的节点，因为递归是返回给每次调用的函数本身，函数是不能存值的，因此我们需要一个变量保存。
TreeNode* findtree(TreeNode* root, int x)
{if (root == NULL){return NULL;}if (root->data==x){return root;}//保存左子树的结果TreeNode* ret=findtree(root->left,x);if (ret){return ret;} //保存右子树的结果TreeNode* ret1=findtree(root->right, x);if (ret1){return ret1;}
}
5. 二叉树的高度

要找到二叉树的高度，我们可以使用以下算法（同样是分治的思想）：

1. 从根节点开始。

2. 如果节点没有子节点，那么它的高度为 0。

3.分别遍历左右子树

4. 如果节点有一个子节点，那么它的高度为 1 加上其子节点的高度。

5. 如果节点有两个子节点，那么它的高度为 1 加上其子节点高度的最大值。

6.比较左右子树的大小，大的那个为二叉树的高度，最后加上根节点，就得到了二叉树的高度。
int TreeHeight(TreeNode* root)
{if (root == NULL)return 0;return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}
这里我们用到fmax函数进行比较，当然你也可以选择使用运算符进行比较。

1.4 二叉树的创建和销毁

1.二叉树的创建

用先序，中序，后序的方式去直接创建二叉树，那么，知道先序的序列就用先序的序列去递归创建树，知道中序的序列就用中序的序列去递归创建树,知道后序的序列就用后序的序列去递归创建树

eg：用数组来存储
TreeNode* TreeCreate(char* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));if (root == NULL){perror("malloc fail");exit(-1);}root->data = a[(*pi)++];root->left = TreeCreate(a, pi);root->right = TreeCreate(a, pi);return root;
}
2.二叉树的销毁

关于二叉树的销毁，你可以以任意序列的去销毁二叉树
void destroy_tree(Node *root) {if (root == NULL) {return;}destroy_tree(root->left);destroy_tree(root->right);free(root);
}