c++递归的实例使用1(链表和排序二叉树)——包含单链表的倒序输出和排序二叉树的后序输出 #朱小黑的小白日记#_链表c尾插法倒序输出

过程封装一部分比较实用的单链表函数
主要练习的是其中的 void reverse_print_list函数，需要使用简单的递归，在二叉树中的递归会更加复杂一些。

/*goodlist.h*/
#include<iostream> 
using namespace std;
struct Node {
 int value;
 Node* next;
};
int list_tail_insert(Node* list_head, int var);//单个数据插入，尾插法
Node* list_head_insert(Node* list_head, int var);//单个数据插入，头插法
Node* list_specific_insert(Node* list_head, int location, int var);//指定位置插入,可以插入头，尾，或者头尾之间任意位置
void print_list(Node* list_head);//输出链表，循环方式，空格隔开
void reverse_print_list(Node* list_head);//逆序输出，递归方式，空格隔开
//void reverseprintlist(Node* list_head);
void change_specific_var(Node* list_head, int old_var, int new_var);//修改链表中的指定元素值
Node* del_specific_var(Node* list_head, int del_var);//删除链表中的指定元素值
Node* sort(Node* list_head);//从小到大排序
int list_len(Node* list_head);//检测链表长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

以下是自定义这些链表函数内容（一开始为了快点交作业排序采用了交换值的方法，之后会改为交换节点，方便以后的复用）

Node* list_head_insert(Node* list_head, int var) {
 Node* p = new Node;
 p->value = var;
 p->next = NULL;
 if (list_head == NULL)return p;
 else {
  p->next = list_head;
  return p;
 }
}
int list_tail_insert(Node* list_head, int var) {
 if (list_head == NULL) {
  cout << "无法在空链表中插入尾部" << endl;
  exit(-1);
 }
 else
 {
  Node* p = new Node;
  p->value = var;
  p->next = NULL;
  Node* tmp = list_head;
  while (tmp->next) tmp = tmp->next;
  tmp->next = p;
  return 1;
 }
}
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

Node* sort(Node* list_head){
if (list_head == NULL || list_head->next == NULL) return list_head;//如果链表为空或只有一个节点，直接返回
 int len = list_len(list_head);
 Node* p = list_head;
 for (int i = 1;i <= len - 1;++i) {
  p = list_head;
  while (p->next) {
   if (p->value > p->next->value) {
    int tmp = p->value;
    p->value = p->next->value;
    p->next->value = tmp;
   }
   p = p->next;
  }
 }
 return list_head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

其他比较简单的函数在此不再列出，来到关键的单链表倒序输出

void reverse_print_list(Node* list_head) {
 static int i = 0;//设置标识符用来判断是否应该输出换行符
 ++i;
 if (list_head == NULL) {
  --i;
  return;
 }
 else reverse_print_list(list_head->next);
 cout << list_head->value << " ";
 --i;
 if (i == 0)cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11

最初没有static int作为标识符，没有办法在打印完链表后输出一个回车，所以我采用的办法是在另一个函数中包含这个递归函数，结束后再输出一个回车。

虽然这样十分的简单粗暴，效果也很好，但破坏了过程的封装，使用者还可以调用单独的递归函数（主要是觉得这样写很难看）然后再一位同学的启发下改用静态变量来控制递归函数，也是将来使用递归的一个重要的小技巧。

顺便练习节点交换的冒泡排序

Node* sort(Node* list_head){
if (list_head == NULL || list_head->next == NULL) return list_head;
 int len = list_len(list_head);
 Node* cur = list_head, * pre = list_head;
 for (int i = 1;i <= len - 1;++i) {
  cur = list_head;
  pre = list_head;
  while (cur->next) {
   if (cur->value > cur->next->value) {
    if (cur == list_head) {
     list_head = list_head->next;
     cur->next = list_head->next;
     list_head->next = cur;
     pre = list_head;
     continue;
    }
    else {
     pre->next = cur->next;
     cur->next = NULL;
     cur->next = pre->next->next;
     pre->next->next = cur;
     pre = pre->next;
     continue;
    }
   }
   pre = cur;
   cur = cur->next;
  }
 }
 return list_head;

}
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

————————————————————————————————————
二叉树

#include<iostream>
using namespace std;
struct Node {
 int value;
 Node* leftnext;
 Node* rightnext;
};
bool is_leaf(Node* head);//是否是叶子结点
Node* insert(Node* T, int x);//在二叉树中插入一个结点
void postorder(Node* T);//后序遍历
1
2
3
4
5
6
7
8
9

Node* insert(Node* T, int x) {
 Node* p = new Node;
 p->value = x;
 p->leftnext = NULL;
 p->rightnext = NULL;
 if (!T) return p;
 Node* temp = T;
 while (temp) {
  if (x < temp->value)
  {
   if (temp->leftnext == NULL) {
    temp->leftnext = p;
    return T;
   }
   else {
    temp = temp->leftnext;
    continue;
   }
  }
  else
  {
   if (temp->rightnext == NULL) {
    temp->rightnext = p;
    return T;
   }
   else {
    temp = temp->rightnext;
    continue;
   }
  }
 }
 exit(-1);
}
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

bool is_leaf(Node* head) {
 if (head->leftnext == NULL && head->rightnext == NULL) return true;
 else return false;
}
1
2
3

void postorder(Node* T){
if (T == NULL) return;
 else if (is_leaf(T)) {
  cout << T->value << " ";
  return;
 }
 if (T->leftnext != NULL) {
  postorder(T->leftnext);
  if(T->rightnext==NULL) cout << T->value << " ";
 }
 if (T->rightnext != NULL) {
  postorder(T->rightnext);
  cout << T->value<<" ";
 }
 return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15