二叉树概述

目录

一、二叉树的基本结构

二、二叉树的遍历

1.前序

2.中序

3.后序 

4.层序遍历 

三.计算二叉树的相关参数

1.计算节点总个数

 2.计算叶子节点的个数

 3.计算树的高度

4.计算第k层的子树个数

 5.查找树中val为x的节点

 四.刷题

1.单值二叉树

2.检查两棵树是否相同

3.一棵树是否对称

---

二叉树的实现源码_gitee

---

一、二叉树的基本结构

 这里的二叉树比堆的定义更广泛，

heap=>完全二叉树/满二叉树

二叉树=>二叉，不成图（没有闭合圈）

二、二叉树的遍历

1.前序

NULL用‘#’表示，下面实例的val是char类型

void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}printf("%c ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);}

这里使用的是递归式的遍历，因为二叉树可以看作根和子树，而子树又可以看作根和子树

注意，这里的return 是指返回上一层的递归，下面是部分运行逻辑

2.中序

void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}BinaryTreeInOrder(root->_left);printf("%c ", root->_data);BinaryTreeInOrder(root->_right);}

3.后序 

void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%c ", root->_data);
}

4.层序遍历 

这里要使用队列，先根节点入队，根节点出队后，对应的左右子树节点入队，左子树节点作为根节点出队，再有对应的左右子树节点入队，以此类推

void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while(!QueueEmpty(&q)){BTNode* cur = QueueFront(&q);QueuePop(&q);printf("%c ", cur->_data);if (cur->_left)QueuePush(&q, cur->_left);if(cur->_right)QueuePush(&q, cur->_right);}}

---

这是带有换行效果的层序遍历，实现原理是需要记录每一层的个数，方便pop 完一层接一个换行

void BinaryTreeLevelOrder(BTNode* root)
{Queue Bq;QueueInit(&Bq);QueuePush(&Bq, root);int popnum = QueueSize(&Bq);while(!QueueEmpty(&Bq)){while(popnum--){BTNode* cur = QueueFront(&Bq);QueuePop(&Bq);printf("%c ", cur->_data);if(cur->_left!=NULL){QueuePush(&Bq, cur->_left);}if(cur->_right!=NULL){QueuePush(&Bq, cur->_right);}}popnum = QueueSize(&Bq);printf("\n");}}

三.计算二叉树的相关参数

1.计算节点总个数

思路1：遍历二叉树，不过要传入一个可以记录的参数，为了这个参数可以随遍历而变化，不能传入实参拷贝为形参这一套

解决方法：

1.使用static参数，在函数内定义，只要把static的值最后return,在全局则可以不用，直接查static的值，弊端：这个函数不能再同一个程序里重复调用，因为static的值不会再从0开始 

2.在参数列表里多传入一个int *size,每次++时就（*size）++,在进入下一个递归

---

 思路2：递归计数，

当root==NULL,   return 0;

当root不为NULL时，return 1+左子树的个数+右子树的个数

int BinaryTreeSize(BTNode* root)
{
if(root==NULL)
{return 0;
}
return 1 + BinaryTreeSize(root->_right) + BinaryTreeSize(root->_left);}

 2.计算叶子节点的个数

思路：递归计数，叶子节点时左右子树都为NULL时，

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

 3.计算树的高度

int nummax(int p1, int p2)
{return p1 > p2 ? p1 : p2;}
int tree_height(BTNode* root)
{if(root==NULL){return 0;}return 1 + nummax(height(root->_left),height(root->_right));}

4.计算第k层的子树个数

 思路：距离root为k,那么距离root的下一层为k-1，当k==1时，就是递归到第k层了

root==NULL,return 0

root!=NULL&&k==1,return 1;

其他情况：return knum(root->left,k-1)  +  knum(root->right,k-1)

int knum(BTNode* root,int k)
{if(root==NULL){return 0;}if (k == 1){return 1;}return knum(root->left, k - 1) + knum(root->right, k - 1);}

 5.查找树中val为x的节点

思路:递归遍历+比较是否为x

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

 

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

思路：以层序遍历对二叉树进行收集(此时NULL也收入)，在每个节点开始pop时，判断是否为NULL，一旦为NULL,则跳出循环，开始判断NULL之后的队列是否全为NULL,

如果全为NULL==>是完全二叉树

如果不是==>不是

bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* cur = QueueFront(&q);QueuePop(&q);if (cur == NULL)break;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;}

 

 四.刷题

1.单值二叉树

bool _isUnivalTree(struct TreeNode* root,int val)
{
if(root==NULL)
return true;if(root->val!=val)
return false;return _isUnivalTree(root->left,val)&&_isUnivalTree(root->right,val);}bool isUnivalTree(struct TreeNode* root) {int val=root->val;
return _isUnivalTree(root,val);}

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

3.一棵树是否对称

bool issame(struct TreeNode* p1, struct TreeNode* p2)
{if (p1 == NULL && p2 == NULL){return true;}if (p1 == NULL || p2 == NULL){return false;}if (p1->val != p2->val) { return false; }return issame(p1->left, p2->right)&&issame(p1->right, p2->left);
}
bool isSymmetric(struct TreeNode* root) {if(root==NULL){return true;}return issame(root->left, root->right);}

---