1、栈和队列

1、关于只给出了入栈序列和出栈序列中的一个然后判断另一个的合法性的问题？

例：给定一个入栈序列 a, b, c, d, e, f;然后判断 cabdef、bdaefc 这些出栈序列是否合法

1
2
cabdef:我们可以发现，第一个出栈的元素为c，其前面没有对应的入栈序列中c前面的a和b，所以我们知道在c出栈的前一刻，栈中是这样的——abc(栈底->栈顶)，由此我们可以推断出c后面的出栈序列一定是这样的—— ...b...a...，其中省略号的地方可以有数据也可以没有数据，进而我们可以判断c(ab)defc是非法的出栈序列
bdaefc:我们可以发现，第一个出栈的元素是b，我们无法由此判断是否合法，所以接着往后看，接下来的一个元素为d,其前面没有对应的入栈序列中d前面的a和c,根据入栈序列我们可以推断出d后面的出栈序列一定是这样的—— ...c...a...，其中省略号的地方可以有数据也可以没有数据，进而我们可以判断bd(a)ef(c)是非法的出栈序列

2、链表

1、如何判断两个链表是否有交点且交点的位置？

2、如何判断一个链表中是否有环并求出环的入口位置？

3、树的基本操作

顺序存储

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<iostream>
#include<vector>
#include<string>
using namespace std;
template <class T>
class Bitree {
public:
	void createBitree();//建树
	void chengchiDisplay();//层次遍历
	void preDisplay(int ptr);//先序遍历
	void midDisplay(int ptr);//中序遍历
	void backDisplay(int ptr);//后序遍历
	void buildByPreAndMid();//通过先序遍历和中序遍历建树
	T handleBuildByPreAndBack(vector<T> preArr, int pl, int pr, vector<T> midArr, int il, int ir);
	int findRoot(T root, vector<T> midArr, int il, int ir);//查找root在midArr中的位置 
public:
	vector<T> tree;
	int treeNodeNumber;//树结点的个数	
};
template <class T>
void Bitree<T>::createBitree() {
	cout << "请输入结点的个数：";
	cin >> this->treeNodeNumber;
	this->tree.resize(this->treeNodeNumber + 1);
	cout << endl;
	cout << "请按顺序输入相关结点的值：";
	int tempNum = this->treeNodeNumber;
	T tempTreeNode;
	for(int i = 1; i <= this->treeNodeNumber; i++) {
		cin >> tempTreeNode;
		tree[i] = tempTreeNode;
	}
}

template <class T>
void Bitree<T>::chengchiDisplay() {
	for(int i = 1; i <= this->treeNodeNumber; i++) {
		cout << this->tree[i] << " ";
	}cout << endl;
}

template <class T>
void Bitree<T>::preDisplay(int ptr) {
	if(ptr <= this->treeNodeNumber) {
		cout << this->tree[ptr] << " ";
		preDisplay(2 * ptr);
		preDisplay(2 * ptr + 1);
	}
}

template <class T>
void Bitree<T>::midDisplay(int ptr) {
	if(ptr <= this->treeNodeNumber) {
		midDisplay(2 * ptr);
		cout << this->tree[ptr] << " ";
		midDisplay(2 * ptr + 1);
	}
}

template <class T>
void Bitree<T>::backDisplay(int ptr) {
	if(ptr <= this->treeNodeNumber) {
		backDisplay(2 * ptr);
		backDisplay(2 * ptr + 1);
		cout << this->tree[ptr] << " ";
	}
}

template <class T>
int Bitree<T>::findRoot(T root, vector<T> midArr, int il, int ir) {
	for(int i = il; i <= ir; i++) {
		if(midArr[i] == root) {
			return i;
		}
	}
	return -1;
}

template <class T>
T Bitree<T>::handleBuildByPreAndBack(vector<T> preArr, int pl, int pr, vector<T> midArr, int il, int ir) {
	if(pl == 1) this->tree[pl] = preArr[pl];
	T root = preArr[pl];
	int k = this->findRoot(preArr[pl], midArr, il, ir);
	if (k > il && 2 * pl < preArr.size()) {
		this->tree[2 * pl] = handleBuildByPreAndBack(preArr, pl + 1, k - il + pl, midArr, il, k - 1);
	}
	if (k < ir && 2 * pl + 1 < preArr.size()) {
		this->tree[2 * pl + 1] = handleBuildByPreAndBack(preArr, k - il + pl + 1, pr, midArr, k + 1, ir);
	}
	return root;
}

template <class T>
void Bitree<T>::buildByPreAndMid() {
	cout << "请输入结点的个数：";
	int n;
	cin >> n;
	
	this->tree.resize(n + 1);
	this->treeNodeNumber = n;
	
	vector<T> preArr(n + 1);
	vector<T> midArr(n + 1);
	cout << endl;
	cout << "请输入中序遍历序列："; 
	T temp;
	for(int i = 1; i <= n; i++) {
		cin >> temp;
		midArr[i] = temp;	
	}cout << endl; 
	cout << "请输入先序遍历序列："; 
	for(int i = 1; i <= n; i++) {
		cin >> temp;
		preArr[i] = temp;	
	}cout << endl;
	this->handleBuildByPreAndBack(preArr, 1, n, midArr, 1, n);	
}

int main() {
	Bitree<int> T;
	T.buildByPreAndMid();
	//T.createBitree();
	cout << "层次遍历：";
	T.chengchiDisplay();
	cout << "先序遍历：";
	T.preDisplay(1);cout << endl;
	cout << "中序遍历：";
	T.midDisplay(1);cout << endl;
	cout << "后序遍历：";
	T.backDisplay(1);cout << endl;
    
	return 0;
}

链式存储

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
using namespace std;

typedef struct Node
{//定义二叉树结构
    char data;
    struct Node *lchild,*rchild;
}*BiTree,BiTNode;

void CreateBiTree(BiTree &T)
{//先序创建二叉树
    char ch;
    cin>>ch;
    if(ch=='#') T=NULL;
    else{
        T=new BiTNode;
        T->data=ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
void InOrderTraverse(BiTree T)
{//中序遍历
    if(T)
    {
        InOrderTraverse(T->lchild);
        cout<<T->data;
        InOrderTraverse(T->rchild);
    }
}
void PreOrderTraverse(BiTree T)
{//先序遍历
    if(T)
    {
        cout<<T->data;
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}
void PostOrderTraverse(BiTree T)
{//后序遍历
    if(T)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout<<T->data;
    }
}
void Copy(BiTree T,BiTree &NewT)
{//二叉树的复制
    if(T==NULL)
        NewT=NULL;
    else
    {
        NewT=new BiTNode;
        NewT->data=T->data;
        Copy(T->lchild,NewT->lchild);
        Copy(T->rchild,NewT->rchild);
    }
}
int Depth(BiTree T)
{//树的深度
    if(T==NULL)
        return 0;
    else
    {
        int m=Depth(T->lchild);
        int n=Depth(T->rchild);
        if(m>n) return (m+1);
        else return (n+1);
    }
}
int NodeCount(BiTree T)
{//统计二叉树中结点的个数
    if(T==NULL) return 0;
    else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int LeafCount(BiTree T)
{//统计二叉树中叶子结点的个数
    if(!T) return 0;
    if(!T->lchild &&!T->rchild){
		//如果二叉树左子树和右子树皆为空,说明该二叉树根节点为叶子节点,加1.
        return 1;
    }else{
        return LeafCount(T->lchild)+LeafCount(T->rchild);
    }
}
int Node_1_Count(BiTree T)
{//统计二叉树的度为1的结点个数
    if(!T) return 0;
    if((!T->lchild)&&(T->rchild)||(T->lchild)&&(!T->rchild))
        return 1 + Node_1_Count(T->lchild) + Node_1_Count(T->rchild);
    else
        return Node_1_Count(T->lchild) + Node_1_Count(T->rchild);
}
void PrintAllPath(BiTree T, char path[], int pathlen)
{//二叉树中从每个叶子结点到根结点的路径
  int i;
  if(T != NULL) {
    path[pathlen] = T->data; //将当前结点放入路径中
    if(T->lchild == NULL && T->rchild == NULL) {//叶子结点
        for(i = pathlen; i >= 0; i--)
            cout << path[i] << " " ;
      cout << endl;
    }else{
      PrintAllPath(T->lchild, path, pathlen + 1);
      PrintAllPath(T->rchild, path, pathlen + 1);
    }
  }
}
void ExChangeTree(BiTree &T)
{//构造函数，使用递归算法进行左右结点转换
    BiTree temp;
    if(T!=NULL){//判断T是否为空，非空进行转换，否则不转换
        temp=T->lchild;
        T->lchild=T->rchild;//直接交换节点地址
        T->rchild=temp;
        ExChangeTree(T->lchild);
        ExChangeTree(T->rchild);
    }
}
void DblOrderTraverse(BiTree T)
{//二叉树的双序遍历
    if(T)
    {
        cout<<T->data;
        DblOrderTraverse(T->lchild);
        cout<<T->data;//访问两遍
        DblOrderTraverse(T->rchild);
    }
}
int main()
{
    BiTree T;
    //测试例子AB#CD##E##F#GH###
    cout<<"先序遍历输入(以#结束):";
    CreateBiTree(T);
    cout<<"中序遍历输出:";
    InOrderTraverse(T);
    cout<<endl<<"先序遍历输出:";
    PreOrderTraverse(T);
    cout<<endl<<"后序遍历输出:";
    PostOrderTraverse(T);
    cout<<endl<<"树的深度:"<<Depth(T);
    cout<<endl<<"结点的个数:"<<NodeCount(T);
    cout<<endl<<"叶结点的个数:"<<LeafCount(T);
    cout<<endl<<"度为1的结点个数:"<<Node_1_Count(T);
    cout<<endl<<"二叉树中从每个叶子结点到根结点的所有路径："<<endl;
    char path[256];
    int pathlen=0;
    PrintAllPath(T,path,pathlen);//
    //交换二叉树每个结点的左孩子和右孩子
    BiTree tem=T;//直接复制一颗树，在不改变原树的前提下，对临时树进行交换。
    ExChangeTree(tem);
    cout<<"先序遍历输出交换后的结果:";
    PreOrderTraverse(tem);
    cout<<endl<<"双序遍历输出:";
    DblOrderTraverse(T);
    return 0;
}