数据结构——二叉树

二叉树

什么是树

树是一种非线性结构。树有一个特殊的节点，叫做根节点。根节点是一个树的起点，除根节点外，它下面的节点被分为很多的分支。以每个分支节点为起点又可以构成一个树，称为子树。由根节点及子树构成的结构称为树

树的相关概念

节点的度：该节点直接相连了几个节点，就是几度。
叶子节点：度为0的节点
分支节点：度不为0的节点
父亲节点：该节点有连接下一层的节点 ，该节点即为父节点
子节点：父节点连的节点为子节点
兄弟节点：有共同父节点的节点，互称为兄弟节点。
树的度：节点中度最大的，就是树的度。
节点的层次：如果定义根节点为第 1层，那么根的子节点为第二层，依次类推。
树的的高度（深度）：节点的最大层数为树的深度。
堂兄弟节点：处于同一层的节点。
节点的祖先：从根到该节点所经分支的全部节点。
子孙：以某节点为根的子树中任意一个节点都称为该节点的子孙
森林：多颗树构成的集合称为森林。

什么是二叉树

一个二叉树是节点的集合，该集合可以为空，也可以由根节点连接左右子树构成。
二叉树的特点：
1.每个节点的度最大为2。
2.二叉树有左右子树，因此是有序的，左右不能颠倒

特殊的二叉树

满二叉树：每一层的节点数都达到最大。
完全二叉树：除最后一层外，每一层的节点数都达到最大，且最后一层的节点都位于左部。

二叉树的性质

若根节点为第一层，那么二叉树的第i层最多有2(i-1)个节点，总节点数最多有2h-1。
对于任意一个二叉树，如果度为0的节点有n0,那么度为2的节点n2=n0-1。
对一个完全二叉树进行编号，编号的规则：自上而下，自左而右。
那么，第i个节点对应的左节点为2i+1，右节点为2i+2，对应的父节点为(i-1)/2。

链式二叉树

二叉树类型的创建

typedefint BTDataType;typedefstructBinaryTreeNode{structBinaryTreeNode* left;structBinaryTreeNode* right;
    BTDataType data;}BTNode;

二叉树的遍历

前序遍历：

先访问根节点，再访问左子树，最后访问右子树；每个子树又可以分为根，左树，右树。不断的递归，直到每个子树的根为空。

voidBinaryTreePrevOrder(BTNode* root){if(root ==NULL){printf("# ");return;}printf("%d ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);}

中序遍历：

先访问左子树，再访问根节点，最后访问右子树

voidBinaryTreeInOrder(BTNode* root){if(root ==NULL){printf("# ");return;}BinaryTreeInOrder(root->left);printf("%d ", root->data);BinaryTreeInOrder(root->right);}

后序遍历：

先访问右子树，再访问左子树，最后访问根节点

voidBinaryTreePostOrder(BTNode* root){if(root ==NULL){printf("# ");return;}BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);printf("%d ", root->data);}

二叉树节点的个数

先访问根，不为空就加1，然后访问左右子树。为空就返回0

intBinaryTreeSize(BTNode* root){if(root ==NULL)return0;elsereturn1+BinaryTreeSize(root->left)+BinaryTreeSize(root->right);}

查找数据为X的节点

先查找根节点，然后再分别查找左右子树，当为空的时候返回空，当节点的数据为x时，则返回该节点的地址。然后把左右子树按上面的方式继续查找。

BTNode*BinaryTreeFind(BTNode* root, BTDataType x){if(root ==NULL)returnNULL;if(root->data == x)return root;
    BTNode* ret1=BinaryTreeFind(root->left,x);if(ret1)return ret1;

    BTNode* ret2 =BinaryTreeFind(root->right, x);if(ret2)return ret2;returnNULL;}

查找叶子节点的个数

出度为0的节点为叶子节点，那我们就查找左右孩子为空的节点。

intBinaryTreeLeafSize(BTNode* root){if(root ==NULL)return0;if(root->left ==NULL&& root->right ==NULL)return1;returnBinaryTreeLeafSize(root->left)+BinaryTreeLeafSize(root->right);}

第k层节点的个数

我们把根看成第k层，那么实际上的第k层就是第一层。
如果节点为空就返回0，如果k为1就是到了第k层了，返回1。
上述是归的条件。递就是按这个逻辑继续查找左，右子树。

intBinaryTreeLevelKSize(BTNode* root,int k){if(root ==NULL)return0;if(k ==1)return1;returnBinaryTreeLevelKSize(root->left, k -1)+BinaryTreeLevelKSize(root->right, k -1);}

二叉树的高度

要求树的高度就是求路径最大的。
我们可以先比较左右子树的高度，然后最大的子树的高度加1就是树的高度。这个就是不断递归的过程。

intTreeDepth(BTNode* root){if(root ==NULL)return0;int ret1 =TreeDepth(root->left);int ret2 =TreeDepth(root->right);if(ret1 > ret2)return ret1+1;elsereturn ret2+1;}

二叉树的层序遍历

用一个队列储存节点，当一个节点出队时，它的孩子节点入队。这样就实现了层序遍历。

voidBinaryTreeLevelOrder(BTNode* root){
    Queue q;QueueInit(&q);if(root)QueuePush(&q, root);while(!QueueEmpty(&q)){
        BTNode* cur =QueueFront(&q);QueuePop(&q);if(cur ==NULL)printf("# ");else{printf("%d ", cur->data);QueuePush(&q, cur->left);QueuePush(&q, cur->right);}}QueueDestroy(&q);printf("\n");}

判断二叉树是不是完全二叉树

按照层序遍历，如果是完全二叉树，当出队列的节点为空的时候，后面所有的节点都是空，反之不是完全二叉树。

bool BinaryTreeComplete(BTNode* root){
    Queue q;QueueInit(&q);if(root)QueuePush(&q, root);while(!QueueEmpty(&q)){
        BTNode* cur =QueueFront(&q);QueuePop(&q);if(cur ==NULL)break;else{QueuePush(&q, cur->left);QueuePush(&q, cur->right);}}while(!QueueEmpty(&q)){
        BTNode* cur =QueueFront(&q);QueuePop(&q);if(cur !=NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;}