二叉树

内容来源于代码随想录

二叉树的递归遍历

递归推理的三个思考点

  • 确定递归的参数和返回值：哪些参数是递归过程需要考虑的
  • 确定终止条件：操作系统使用一个栈结构来保存每一层递归的信息
  • 确定单层递归的逻辑

二叉树的深度搜索三个方法：前序、中序、后序就是使用递归遍历：

首先是二叉树的创建：

输入样例：1 5 8 0 0 0 6 0 0

这个采用的是先根遍历的方式创建的：首先读入根节点，然后一路向左创建新的节点，再向左搜索直至没有左节点，接着回溯至上一根节点寻找右节点，若无结束当层节点的递归，再返回上一个节点。这边要特别注意记得返回的是当前节点：

1
2
3
4
5
6
7
else{
		t = (struct node *)malloc(sizeof(struct node));
		t->val = num;
		//printf("%d", t->val);
		t->left = create_tree(t->left);
		t->right = create_tree(t->right); 
	}return t;

return t 特别注意

接下来就是根据先根中跟后跟的口诀来依次递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<stdio.h>
#include<stdlib.h>
struct treenode{
	int data;
	struct treenode * left;
	struct treenode * right;
};
   struct treenode* root = NULL;
struct treenode * create(struct treenode * root){
	int d;
	struct treenode * node;
	while(scanf("%d", &d)!= EOF){
		if(d == 0)return NULL;
		else{
		
			node = (struct treenode *)malloc(sizeof(struct treenode));
			node->data = d;
			node->left = create(node->left);
			node->right = create(node->right);
					}
		return node;
	}
}  
void travel_first(struct treenode *node){//先根
	       if(node == NULL)return;
		   else{
		   	printf("%d ", node->data);
		   	travel_first(node->left);
		   	travel_first(node->right);
		   } 
}
void travel_second(struct treenode *node){//中跟
	       if(node ==NULL)return;
		   else{
		   	travel_second(node->left);
		   	printf("%d ", node->data);
		   	travel_second(node->right);
		   } 
}
void travel_third(struct treenode *node){//后根
	       if(node ==NULL)return;
		   else{
		   	travel_third(node->left);
		   	
		   	travel_third(node->right);
		   	printf("%d ", node->data);
		   } 
}
int main() {
     struct treenode* r = NULL;
     r = create(r);
     travel_first(r);printf("\n");
     travel_second(r);printf("\n");
     travel_third(r);printf("\n");
	return 0;
}

二叉树的非递归遍历

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

为了方便说明，先附上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void travel_first(struct node *r){
	struct node*stack[100];
	int top = 0;
    if(r == NULL)return;
    stack[++top] = r;
    while(top != 0){
    	struct node * tmp;
    	tmp = stack[top];
    	stack[top]=NULL;
    	top--;
    	result[++toper] = tmp->val;
    	if(tmp->right != NULL)stack[++top] = tmp->right;
    	if(tmp->left != NULL)stack[++top] = tmp->left;	
	}
}

首先建立一个树节点的临时栈，将根节点压入栈中，然后再将值压入结果栈中，再先压右子树进入栈中，后压左子树（这点非常的重要），再打印result数组。

强调：临时栈弹出后一定要清空！然后打印数组时一定要打印到top指向的位置而不是前一位！

后根遍历改变压栈顺序先左后右然后逆序输出result数组即可，这边不再强调。

  • 中根遍历
  1. 处理：将元素放进result数组中
  2. 访问：遍历节点

这个时候需要一个指针用来存储临时遍历的节点，直至遍历到左子树最下面的一个叶子节点：我们常常把对根节点的处理作为递归出口，然后使用临时栈来判断循环条件。

这边要特别注意不能直接将临时栈中的数据直接取出来存入结果数组中，因为这样子树的链表连接就直接断开了，在这一步和上面相同的是要更新这个临时节点指向的数据，将其更新为栈顶元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void travel_first(struct node *r){
	struct node*stack[100];
	int top = 0;
    if(r == NULL)return;
    struct node * temp = r;
    while(top != 0||temp != NULL){//根节点为空、栈为空 
       if(temp != NULL){//temp代表的是一路向左的指针，有可能本身为空，不要写成temp->left 
       	stack[++top] = temp;
       	temp = temp->left;
	   }
	   else{//这个地方特别注意这个节点的传递
	   	temp = stack[top]; 
	   	stack[top] = NULL;
	   	  	top--;
	   	  	result[++toper] = temp->val;
	   	  	temp = temp->right;
	   } 
    }
    
}

统一迭代法

统一迭代法使用一个空指针作为标记，用以区分访问过的节点和决定弹出的顺序；根后面跟着一个空指针，然后压入顺序记得颠倒：

中序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void travel_first(struct node *r){
	struct node*stack[100];
	int top = 0;
    if(r == NULL)return;
    stack[++top] = root;//将根节点放入栈中，不放会是空栈，死循环 
    while(top != 0){//根节点为空、栈为空 
    struct node * temp = stack[top];//统一迭代法中的临时节点实际上是指针，谁访问的节点由谁决定 
       if(temp != NULL){//temp不为空的时候代表一种标记，不必弹栈
        stack[top] = NULL;
        top--;//弹栈
		if(temp->right != NULL)stack[++top] = temp->right;
		stack[++top] = temp; 
       	stack[++top] = NULL;//根节点后做标记
       	if(temp->left != NULL)stack[++top] = temp->left;
	   }
	   else{//遇到NULL则弹栈
	   	top--;//开始弹出节点
	   	temp = stack[top]; 
	   	stack[top] = NULL;
	   	  	top--;
	   	  	result[++toper] = temp->val;
	   } 
    }
    
}

前序和后序改变两个if语句的顺序即可。

二叉树的层序遍历

广度优先搜索

利用辅助队列，每层节点按顺序进入队列，接着分别判断左右节点是否为空，若不为空则分别进入队列，再按顺序依次弹出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void leverOrder(struct node * r){
	struct node * queue[100];
	int front= 0;
	int rear = 0;
	if(r != NULL)queue[++rear] = r;
	//front = rear;
	while(front != rear){
		int size = rear-front;//size实际上是每层节点的数目 
		for(int i = 0;i < size;i++){
			struct node *tmp = queue[front+1];
            //这边要注意出队的时候我们记录的是front+1 
			result[++toper] = tmp->val;
            front++;
		    if(tmp->left != NULL)queue[++rear] = tmp->left;
		    if(tmp->right != NULL)queue[++rear] = tmp->right;
		}	
	}
}

二叉树的深度(max,min)

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数

注意：使用递归求取最大深度，（后序遍历）分别对左子树和右子树求，然后再返回左右子树中深度最大的。不可直接返回左右子树求出来的那个值：原因不详。

1
2
3
4
5
6
7
8
9
10
int depth(struct node * r){
	if(r == NULL)return 0;
	else{
		int leftdepth = depth(r->left);
		int rightdepth = depth(r->right);
		int max = leftdepth > rightdepth ?leftdepth:rightdepth;
			return max+1; 
	}

}

此外还有两种解决办法：通过先序遍历来求解深度（回溯）以及通过层次遍历来求解：层次遍历思路较为简单，详情参见上面层次遍历的模板，在计算每层节点数时顺便让深度depth+1即可。

先度遍历：先检测根节点，再监测左子树，不为空就加一，回溯到底则让深度把借过来的一还回去，接着再求解最大值，此处先暂时省略（我有时间一定敲）QAQ

二叉树的高度（平衡二叉树判断）

本题采用后序遍历，仍然是采用递归的三个思想，应该传入什么参数（我个人觉得刷到现在都是传入根的节点）

1.明确递归函数的参数和返回值

参数：当前传入节点。
返回值：以当前传入节点为根节点的树的高度。

2.明确终止条件

递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0

3.明确单层递归逻辑

如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。

分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。

1
2
3
4
5
6
7
8
int get_height(struct node * r){
	if(r == NULL)return 0;
	int leftheight = get_height(r->left);//这边不需要判断该节点的左子树 是否为空 
	if(leftheight == -1)return -1;
    int rightheight = get_height(r->right);
	if(rightheight == -1)return -1;
	return abs(leftheight-rightheight) >1? -1:1+max(leftheight,rightheight);//这个语句的语法最好还是记一下挺常见的 
}

二叉树的所有路径

dfs+回溯（本题我并没有看懂这个网站的解法，所以自己思考加上参考别人的思路最终敲出来的代码）

注意：1.本题真正的终止条件是访问到的节点是个叶子节点，在这个时候递归与回溯是配套的，所以我们要使用一个配套的存储数组stack，来暂时保存该条路径所有访问过的节点。

​ 2.本题第二个麻烦的是输出路径必然为char数组，鉴于动态分配我实在是没学会，我就还是选择将数组开大一点然后一次存储路径。

​ 3.本题采用的是先根序列的方式，前面我们提到一般求深度的时候首选先根，所有路径的起点均为根，所以我们还是选择了先根序列。

​ 4.单层递归思路，往左一直走，走到没有路了将这条路记录给stack，这边要注意的是stack是个int 整型而我们需要一个临时字符串数组来存储，这边借助了别人的方法来使用sprintf函数，值得一提的是，它的头文件正是include<stdio.h>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int count = 0;
int stack[1001];//存储单条路径访问过的节点 
int top;    
void dfs(struct node* root,char result[][101],int* stack, int top)
{
    if(root == NULL)return;
    if(root->left == NULL && root->right == NULL)
    {
        char tmp[101];//tmp最终记录当前叶子节点对应得路径 
        int len = 0;
        for (int i = 0; i < top; i++) //将栈中所有暂存的点全部输出出来 
        {//按照顺序输出节点 
            len += sprintf(tmp + len, "%d->", stack[i]);//sprintf返回的是该字符串的长度，len是这个路径字符串的长度，
			//tmp是字符串的指针，要向后移动多少长度才能把stack中包括箭头加入进来 
        }
        sprintf(tmp + len, "%d", root->val);//记得加入最后一个节点 
        strcpy(result[count++],tmp);  // 把路径加入到答案中
    }
    else
    {
        stack[top++] = root->val;  // 当前节点不是叶子节点，继续递归遍历
        dfs(root->left, result, stack, top);
        dfs(root->right, result, stack, top);
    }
}



for(int i = 0;i < count;i++)printf("%s\n", result[i]);

二叉树的路径和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

这道题还是常规的回溯，但是它是依次减去根节点的数值，从而来判断是否符合给出的目标值。

注意：本题给出的解答并未将根节点的数值进行录入，如果考虑输入输出情况需要在主函数中判断根节点是否为空，如果不为空将目标值减去根节点的数值然后再进行求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool sum_tree(struct node *r, int target){
	if(r->left == NULL && r->right == NULL && target == 0)return true;//符合路径和 
	if(r->left == NULL && r->right == NULL)return false;//遇到叶子节点直接返回 
	if(r->left){
		target -= r->left->val;
		if(sum_tree(r->left,target))return true;
		target+=r->left->val; 
	}
	if(r->right){
		target -= r->right->val;
		if(sum_tree(r->right,target))return true;
		target += r->right->val; //记得每次回溯要加回去，才能去检测下一条路径 
	}
	return false;//所有路径走完均没有找到符合条件的值，返回false
}

二叉树线索化

介个是我们老师课内拓展的内容–为了强化记忆我特意还原了老师pdf内的算法。首先结构体内会多出两部分内容：

1
2
3
4
5
6
7
struct node{
	int val;
	int Lthread;
	int Rthread;
	struct node * left;
	struct node * right;
};

先描述如何将一个二叉树线索化：首先它的基本思路就是中序遍历：在中序遍历的基础上进行修改。访问完左子树后，对左子树进行判断，为空进行线索化，此时我们需要借助一个父节点用来实时更新左子树指向的位置。同理对于右子树，我们利用了pre这一节点来进行判断是否需要线索化，当满足pre不为空且右子树为空（这边一开始错了改了半个点QAQ）从而来实现线索化，最后尤其注意更新pre的位置，将其变化为下一个节点，再递归进行右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void travel_second(struct node *r){
    if(r == NULL)return;
	travel_second(r->left);
	if(r->left == NULL){
		r->Lthread = 1;
		r->left = pre;
	}
    else r->Lthread = 0;
    if(pre != NULL && pre->right == NULL){//
    	pre->Rthread = 1;
    	pre->right = r;
	}
	else if(pre != NULL)pre->Rthread = 0;
	pre = r;
	travel_second(r->right);
	return;
}

接下来关于中序线索二叉树的遍历，我主要描述利用找首个节点和下一节点的方法，对于找最后节点和前一节点，将左子树改为右子树即可，不再详细赘述。

首个节点：一路向左，直至没有左子树返回

下个节点：当Rthread=1时，意味着它的右指针指向下个节点，直接返回

​ 否则，则返回它右子树的第一个节点。

那么利用上述两个函数，我们最终写出了遍历的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct node* first_order(struct node *r){
	while(r->Lthread == 0){
		r = r->left;
	}
	return r;
}
struct node* next_order(struct node *t){
	if(t->Rthread ==1){
	return t->right;}
	else {
		//printf("%d",t->right->val);
	return first_order(t->right);
}
} 
void inorder(struct node *r){
	struct node * tmp = r;
	tmp = first_order(r);
	while(tmp!= NULL){
		printf("%d ", tmp->val);
		tmp = next_order(tmp);
	}
	
}

二叉树的公共祖先

归纳三点：

  1. 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
  2. 在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
  3. 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果

1
2
3
4
5
6
7
8
9
10
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if(root == NULL)return NULL;//根节点为空直接返回空
    if(root==p || root == q)return root;
    struct TreeNode *left =lowestCommonAncestor (root->left,p,q);
    struct TreeNode *right = lowestCommonAncestor(root->right,p,q);
    if(left == NULL)return right;//可以看上图中2和4，
    //在5这一层递归时left == NULL,于是在右侧查找，找到2时返回right,而这个时候返回的值为3这一层的左值
    if(right == NULL)return left;//同理可得
    return root;//左右子树同时不为空
}

二叉搜索树

概念：二叉查找树中任一结点P，其左子树中结点的关键词都小于P的关键词，右子树中结点的关键词都大于P的关键词，且结点P左右子树也都是二叉查找树。

查找算法：

要强调的就是返回值的问题，如果发现不需要记录沿途的路径值，就直接返回它查找得到的节点。

1
2
3
4
5
6
7
struct TreeNode* searchBST(struct TreeNode* root, int val){
         if(root == NULL)return root;//这个地方要返回的是root，而不是NULL会出现野指针
         if(root->val == val)return root;
         if(root->val > val)return searchBST(root->left,val);
         if(root->val < val)return searchBST(root->right,val);
    return root;
}

插入算法：

一个是递归终点的判断错误，不是找到叶子节点就结束，而是找到叶子结点下一位并对此新分配新的空间。

还有就是递归返回的判断错误：这边是要返回当前节点左子树和右子树的位置，也没有判断正确。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct TreeNode* insertIntoBST(struct TreeNode* root, int val){
         if(root == NULL){
             struct TreeNode * tmp =(struct TreeNode* )malloc(sizeof(struct TreeNode));
             tmp->val = val;
             tmp->left = tmp->right = NULL;//没有对左右指针赋值会出现问题在力扣
             return tmp;//回溯，层层上交
         }
         if(root->val < val){
             root->right =  insertIntoBST(root->right, val);//只有让root的位置一直在才能回溯
         }
        if(root->val >val)
             root->left = insertIntoBST(root->left, val);
    return root;
}

删除算法：

删除算法整体逻辑不变，就是找到后记得分五种情况处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

struct TreeNode* deleteNode(struct TreeNode* root, int key){
          if(root == NULL)return root;//大框架还是找到了，比它大比它小
          if(root->val == key){//这里是在找到这个节点下要删除的四种情况
              if(root->left == NULL)return root->right;
              //左子树为空，右子树可空可不空，直接返回右子树
              else if(root->right == NULL)return root->left;//右子树为空返回左子树
              else{//最复杂的是左右子树都不为空，这个时候我们要先找到这个点右子树最小的点，就是最左边
              //然后将根的左子树变为这个点的左子树
              //临时记录根的位置，然后让根删除
                  struct TreeNode * cur = root->right;
                  while(cur->left != NULL) cur = cur->left;
                  cur->left = root->left;
                  struct TreeNode * tmp = root;
                root = root->right;//此时这个已经失去左子树，只剩右子树，让右子树的根覆盖它即可
                free(tmp);
                return root;
              }
          }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
          return root;
}