【数据结构与算法】第9课—数据结构之二叉树(链式结构)

1. 二叉树的性质

---

• 假设一个二叉树有a个度为2的节点，b个度为1的节点，c个度为0的节点，那么该二叉树的边数是2a+b == a+b+c-1
• 二叉树的边数等于其节点数-1
• 二叉树度为2的节点数等于度为0的节点数-1
• 完全二叉树的高度h = log2(n+1) 2为底，n+1为对数，n为二叉树节点数
• 若完全二叉树的节点数为2n个，那么它的叶子节点数为n
• 若完全二叉树的节点数为2n-1个，那么它的叶子节点数为n

2. 链式结构二叉树

• 链式二叉树的数据结构

---

3. 二叉树链式结构的4种遍历方式

• 前序遍历----根左右原则

---

//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);
}

• 兄弟们，感受一下函数递归的暴力美学吧！

---

• 中序遍历----左根右原则

---

---

//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return ;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}

---

• 后序遍历----左右根原则

---

---

//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}

---

• 层序遍历
• 除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1，层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历
• 实现层序遍历需要额外借助数据结构：队列

---

---

//层序遍历
void LevelOrder(BTNode* root)
{//队列Queue q;QueueInit(&q);//初始化QueuePush(&q, root);//根节点入队//队列不为空while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);//取队头QueuePop(&q);//销毁队头printf("%c ", top->data);//打印队头//取出的队头的左子结点不为空入队if (top->left){QueuePush(&q, top->left);}//取出的队头的右子结点不为空入队if (top->right){QueuePush(&q, top->right);}}QueueDestroy(&q);//销毁队列
}

4. 二叉树节点个数

---

//二叉树节点数个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

---

5. 二叉树的叶子节点个数

---

//二叉树的叶子节点个数
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);
}

6. 二叉树第k层节点个数

---

//二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

---

7. 二叉树的高度/深度

---

//二叉树的高度/深度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return 1 + (leftDep > rightDep ? leftDep : rightDep);
}

---

8. 二叉树查找值为x的节点

---

//查找二叉树中值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right, x);if (rightFind){return rightFind;}//二叉树没有这个节点return NULL;
}

9. 二叉树的销毁

---

---

//二叉树的销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

10. 判断是否为完全二叉树

---

---

//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);//根节点入队//第一次遍历非空队列找NULLwhile (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);//取队头QueuePop(&q);//出队头if (top == NULL){break;}QueuePush(&q, top->left);//队头的左孩子入队QueuePush(&q, top->right);//队头的右孩子入队}//第二次遍历找NULL后是否有非NULL节点while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);//取队头QueuePop(&q);//出队头if (top != NULL){QueueDestroy(&q);//销毁队列return false;}}//第二次循环中没有NULLQueueDestroy(&q);return true;
}

11. 二叉树练习题

11.1 单值二叉树

---

bool isUnivalTree(struct TreeNode* root) 
{//如果根节点为NULL，它也是单值二叉树if(root == NULL){return true;}//如果根节点的左孩子节点存在且该节点的值不等于其左孩子节点的值if(root->left && root->val != root->left->val){return true;}//如果根节点的右孩子节点存在且该节点的值不等于其右孩子节点的值if(root->right && root->val != root->right->val){return true;}//说明当前节点和它的左孩子右孩子节点的值相等return isUnivalTree(root->left) && isUnivalTree(root->right);
}

11.2 相同的树

---

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{//两个二叉树都为空if(p == NULL && q == NULL){return true;}//一个二叉树为空，另一个二叉树非空if(p == NULL || q == NULL){return false;}//两个二叉树都是非空if(p->val != q->val){return false;  //值不同返回}return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

11.3 另一棵树的子树

---

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{//两个二叉树都为空if(p == NULL && q == NULL){return true;}//一个二叉树为空，另一个二叉树非空if(p == NULL || q == NULL){return false;}//两个二叉树都是非空if(p->val != q->val){return false;  //值不同返回}return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) 
{//如果传过来的节点为空if(root == NULL){return false;}//如果root和subRoot两个二叉树相同if(isSameTree(root,subRoot)){return true;}//root和subRoot不是相同的树//分别判断subRoot是否是root的左子树和右子树return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

11.4 二叉树的前序遍历

---

---

 typedef struct TreeNode TreeNode;//求二叉树节点个数int TreeSize(TreeNode* root){if(root == NULL){return 0;}return 1 + TreeSize(root->left) + TreeSize(root->right);}//前序遍历--根左右void PreOrder(TreeNode* root,int* arr,int* p){if(root == NULL){return ;}arr[(*p)++] = root->val;PreOrder(root->left,arr,p);PreOrder(root->right,arr,p);}
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{//先求出二叉树节点的个数*returnSize = TreeSize(root);//为数组arr申请节点空间int* arr = (int*)malloc(sizeof(int)*(*(returnSize)));if(arr == NULL){exit(1);}int i = 0;PreOrder(root,arr,&i);return arr;
}

11.5 二叉树遍历

---

---

#include <stdio.h>
#include <stdlib.h>
typedef char BTDataType;
//创建二叉树的数据结构
typedef struct BinaryNode
{BTDataType data;struct BinaryNode* left;struct BinaryNode* right;
}BTNode;
//申请节点
BTNode* buyNode(char x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));node->data = x;node->left = node->right = NULL;return node;
}//创建二叉树---根左右
BTNode* CreaterTreeNode(char* arr, int* p)
{if(arr[*p] == '#'){(*p)++;return NULL;}//如果读取到的数组元素不是'#'BTNode* root = buyNode(arr[*p]);(*p)++;root->left = CreaterTreeNode(arr, p);root->right = CreaterTreeNode(arr, p);return root;
}
//中序遍历
void InOrder(BTNode* root)
{if(root == NULL){return;}//非空InOrder(root->left);printf("%c ",root->data);InOrder(root->right);
}
int main() 
{//创建数组char arr[100];scanf("%s",arr);//读取字符串//创建二叉树int i = 0;//数组下标BTNode* root = CreaterTreeNode(arr,&i);//中序遍历InOrder(root);return 0;
}