发布于

计算机入门的一点经验和对迷茫的一些分析

最近感觉自己在计算机方面有点入门了，而且恰好前几天和研一的新生聚餐，被问道一些所谓的“经验”方面的问题，所以在这里总结一下在前一个阶段自学计算机的一些尝试，也希望给看到这篇博文的自学计算机方面的人一点参考吧。

首先说明一下，自考研到目前为止，自己看过的书籍（这里所指的看过，是几乎都看完了或者看完至少一大半以上，这样我才能对书做一个评价）。

考研考的是东南大学计算机的自主命题935，科目包括数据结构，计组，操作系统。我用的书是根据统招408来的那三本，即：

同时参考了程杰所作的那本《大话数据结构》，不过当时没敲代码（这点很不对）。当时备考还用过配套的王道的那三本书，就不一一列出了。

复试是C++笔试，用过的书分别是：

之后研一，看过的书分别有：

现在正在开始补数据结构算法方面的内容，看的是《数据结构与算法分析——C语言描述（原书第2版）》。

我所经历过的阶段这里也说明一下，如果你也是这些方面的初学者，也许有点参考意义。

  1. 上网搜集资料，查找经验。网上的推荐书籍有一堆，每个方面的书籍都有很多经典之作，比如计算机入门必看CSAPP啦，C语言是K&R啦，C++是《C++Primer》啦，算法必须看《算法导论》啦，SICP绝对是培养编程思维的神书之类的。总之，网上有浩若烟海的经典书籍是必读的。然后，每本书自己都想细读一番。
  2. 自己实践。显然，在本科阶段把上面这些书自己研究一遍还有点可能，但是在研究生这个阶段，有了导师给布置的任务，而且还是初学者，不太可能把这些一一翻阅。于是开始找一条收益较高的方案。网上推荐的是快速入门C++看《Accelerated C++》，我也是从这本书开始重新敲C++代码的。同时快速的翻看了一遍《CSAPP》。
  3. 入门，有了自己的学习方向。这也就是现在了，当然以后的方向可能还有变化，不过确实现在感觉对计算机编程方面自学有了一点感悟了。

如果你也是初学者，我的一些建议是：

  • 看书尽量找国外书籍看，国内的书籍大多数不适合自学。
  • 如果你的基础确实不太多，可以从以下思路考虑：一门编程语言，数据结构和算法，操作系统，计算机网络。当然，这个更多的是针对互联网企业的后台开发岗位吧，确实我对前端和APP开发不了解。
  • 每个方向的书籍两本就好，一般书籍的侧重可能不同，交叉着看能帮助理解。如果书籍太多的话，可能就会脱离自己上机实践了。前期你不可能看完那么多书的。经典书后面的课后习题，尽量做。
  • 编程语言和算法互相学习可能效果更好一点。比如看数据结构的时候用编程语言自己实现一遍，多用一些编程语言的一些知识要点。同时，看到数据结构，算法的时候，可以考虑到lintcode上面刷刷类似的题目。
  • 从网上大神的反馈和校招的情况看，编程能力、算法等基础很重要。

推荐的书籍以及考虑的参考顺序：

编程语言方面，因为我是看的C/C++，所以对JAVA不太懂，不过熟悉哪门语言都是要大量的敲代码，而不仅仅是看书。下面C/C++如果没时间就先看C++吧。看C的话主要是关注指针那块。

  1. 《C程序设计语言（第2版）》K&R那本
  2. 《C和指针》。上面那本书讲的太精炼了，参照这本书可以对C有一个了解
  3. 《Accelerated C++》。这本书最大的好处是把C++很多常用的语法和STL的一些用法给呈现出来了，而不像普通的C++书籍那样按部就班罗列知识点。
  4. 《C++大学教程》。和上面那本书对照着看。

再强调一遍，编程语言练习也就是自己多敲代码才是重要的，不要抱着书看完一遍又看一遍。

数据结构和算法：

  1. 《大话数据结构》，程杰。入门算是不错的书了，有C的代码，自己敲过一遍理解更深。
  2. 《数据结构与算法分析——C语言描述（原书第2版）》。我选这本书是因为它比较薄，上来直接啃《算法导论》我个人感觉有点太难了。

计算机基础书籍：

  1. 《深入理解计算机系统》。这本书入门计算机绝对没问题，包括了操作系统，汇编，硬件，还有网络的一些简单的东西，现在既然硬件那块需求不大，可以暂时不看吧。

我这条路在入门上面绝对能走通，不过每个人选择的书籍可能不同，也不用都照着来。方向大抵如此，同时，给出一个我看过的较全的书单：《程序员必读书单 1.0》。同样，这个书单也是仅作参考，前期你不可能都掌握的。别贪全，前期要把那些常常出现的问题给解决。

同时，再把自己所说的“入门”给定义或者说明一下，给你一个参照，以防你也是初学，而我又太low，把你带坑里。

之前，我敲代码时出错了是照着书上给的代码改自己的代码。有些确实是不懂，有些是感觉进度确实不能太慢，不然容易陷入细节的思考，还有就是时间拉太长了可能会学了后面的忘了前面的。现在，敲代码会自己设置断点改错，能够明白一些C语言的指针方面错误所在了。

简单的说就是：之前是被动输入，现在能主动输入了。即，把一些从前学过的C++、数据结构的知识进行组合，实现一些自己想到的功能，并且改错的时候能想通一些指针的特性了。这样融合起来学习，能够更好的理解书上的知识。

所以我感觉自己入门了。

我博客中前两篇文章的内容是二叉树的实现，本来其实感觉太简单不想贴出来的，不过想想可以给这篇文章做个铺垫。不信你可以对照着看一下，把《二叉树的实现以及相关操作C/C++》中的代码改写成《二叉树类的实现》中的类，就会遇到很多难题。我自己写的时候想避开《C++大学教程》上的一些方式，不过最后还是没避开，用其他方式我实现不了。当然，也许你写的代码会比我的更简洁。

同样，这里给出一个我看过的不错的入门建议，可以参考：如何从只会 C++ 语法的水平到达完成项目编写软件的水平？。我有空也会尝试的。

最后想到昨天有几个新生说迷茫，正好我也借这篇文章谈谈这个话题吧。

迷茫很正常。研一的新生可能因为刚刚开学，环境变了，同时看到以前的同学或者现在这个行业工作的人们工资很高，而自己能力不足，对未来有点担心。同时，可能是有了导师的直接管理而且感觉导师分配的任务和自己想要尝试的事情不太有交集。简单地说，其实迷茫就是对未来或多或少的担忧。

未来谁知道呢？对吧。没发生的总是没发生，谁也不能说自己的努力方向一定正确，自己的愿景一定实现。

仔细观察我们可以发现，除了大学之前我们没有过太多的迷茫感，在高考填志愿那时开始，很多人多少都会对未来有些迷茫了。因为在那之前，我们更多是在既定的轨道被动进行教育的。我们在规定的时间上课，规定的时间放学，规定的时间完成作业，每隔一段时间会被排名，从而评估你的成绩。更重要的是，那个时候我们不用直接为自己的行为负责，因为父母会给我们埋单。大学之后，我们要进行更多的选择，对自己的行为负责。同时，评估人的标准渐渐变得不那么单一了：有的人社团混的很好，人际交往让人羡慕；有的人会玩乐器，乐队在自己学校小有名气；有的人竞赛屡获佳绩，让人自愧不如。这些都会使我们努力的方向迷失，从而感觉迷茫。

现在，可能你迷茫的是一些学习方法。未来，你可能还会迷茫自己的择业，孩子的学校选择，不同城市到底安家到哪，等等。

那么在迷茫的时候，该做些什么呢？

  1. 上网搜集你所想要努力方向的资料，查找经验。
  2. 进行实践。
  3. 将自己的实践和努力的成果进行分析，修正。
  4. 重复进行2，3步。

然后，你也会找到自己的方向的。所以我在开始将我努力的过程给描述了一遍。

这里再分享一个经验：迷茫的最大敌人是拖延。

相信聪明的你，能更快地找到属于自己的那条道路。

发布于

二叉树类的实现

最近看数据结构看到二叉树的时候，自己实现了一下，同时写成了类，正好复习一下以前看C++的一些知识。代码如下。

// BiTNode.h
// 参照《c++大学教程》中P639页编写
// 模版结点BiTNode类的声明

#ifndef BITNODE_H
#define BITNODE_H

// 声明BiNTree类型
template<typename NODETYPE> class BiTree;

template<typename NODETYPE>
class BiTNode
{
	// 声明友元BiNTree类，使得BiTree类可以访问BiTNode类中的private成员
	friend class BiTree<NODETYPE>;

public:
	BiTNode(const NODETYPE &d) 
		: lchild(0), 
			data(d),
			rchild(0)
	{
	}

	NODETYPE getData() const
	{
		return data;
	}

private:
	BiTNode<NODETYPE> *lchild;
	NODETYPE data;
	BiTNode<NODETYPE> *rchild;
};

#endif

// BiTree.h
// 链表二叉树类模版的定义

#ifndef BITREE_H
#define BITREE_H

#include <iostream>
#include <iomanip>
#include "BiTNode.h"
#include <queue>
#include <stack>
using namespace std;

typedef int Status;

#define OK	1
#define ERROR	0
#define TRUE	1
#define FALSE	0

template<typename NODETYPE>
class BiTree
{
public:
	BiTree();

	void CreateBiTree();
	void DestroyBiTree();
	Status BiTreeEmpty();
	NODETYPE Root();

	int BiTreeDepth();
	int BiTreeDepthNonRecursion();

	void PreOrderTraverse();
	void PreOrderNonRecursion();
	void InOrderTraverse();
	void InOrderNonRecursion();
	void PostOrderTraverse();
	void PostOrderNonRecursion();
	void LevelOrderTraverse();

	void PrintLast();
	void PrintByDepth();

private:
	BiTNode<NODETYPE> *rootPtr;

	// utility function
	void visit(BiTNode<NODETYPE> *p);
	void CreateBiTreeHelper(BiTNode<NODETYPE> **T);
	void DestroyBiTreeHelper(BiTNode<NODETYPE> **T);
	int BiTreeDepthHelper(BiTNode<NODETYPE> *T);

	// 用helper函数的原因是对二叉树进行遍历要传入参数
	void PreOrderTraverseHelper(BiTNode<NODETYPE> *T);
	void InOrderTraverseHelper(BiTNode<NODETYPE> *T);
	void PostOrderTraverseHelper(BiTNode<NODETYPE> *T);
};

template<typename NODETYPE>
BiTree<NODETYPE>::BiTree()
{
	rootPtr = 0;
}

template<typename NODETYPE>
Status BiTree<NODETYPE>::BiTreeEmpty()
{
	if (rootPtr)
		return FALSE;
	else
		return TRUE;
}

template<typename NODETYPE>
void BiTree<NODETYPE>::CreateBiTree()
{
	CreateBiTreeHelper(&rootPtr);
}

// 按前序输入二叉树中结点的值（一个字符）
// #表示空树，构造二叉链表表示二叉树T。
template<typename NODETYPE>
void BiTree<NODETYPE>::CreateBiTreeHelper(BiTNode<NODETYPE> **T)
{
	NODETYPE val;

	cin >> val;

	if (val == '#')
		*T = NULL;
	else
	{
		*T = new BiTNode<NODETYPE>(val);
		CreateBiTreeHelper(&(*T)->lchild);
		CreateBiTreeHelper(&(*T)->rchild);
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::DestroyBiTree()
{
	DestroyBiTreeHelper(&rootPtr);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::DestroyBiTreeHelper(BiTNode<NODETYPE> **T)
{
	if (*T)
	{
		if ((*T)->lchild)
			DestroyBiTreeHelper(&(*T)->lchild);
		if ((*T)->rchild)
			DestroyBiTreeHelper(&(*T)->rchild);
		free(*T);
		*T = NULL;
	}
}

template<typename NODETYPE>
int BiTree<NODETYPE>::BiTreeDepth()
{
	return BiTreeDepthHelper(rootPtr);
}

template<typename NODETYPE>
int BiTree<NODETYPE>::BiTreeDepthHelper(BiTNode<NODETYPE> *T)
{
	int i, j;

	if (!T)
		return 0;

	if (T->lchild)
		i = BiTreeDepthHelper(T->lchild);
	else 
		i = 0;
	if (T->rchild)
		j = BiTreeDepthHelper(T->rchild);
	else
		j = 0;

	return i > j ? i+1 : j+1;
}

template<typename NODETYPE>
NODETYPE BiTree<NODETYPE>::Root()
{
	if (!rootPtr)
		return ' ';
	else
		return rootPtr->data;
}

// 借用层次遍历的思想，实现非递归形式求出二叉树深度
template<typename NODETYPE>
int BiTree<NODETYPE>::BiTreeDepthNonRecursion()
{
	if (!rootPtr)
		return 0;

	BiTNode<NODETYPE> *p; // 工作指针，每次记录从队列队首弹出的结点
	BiTNode<NODETYPE> *back; // 记录每层二叉树的最右边的结点。此结点在每次遍历一层之后的队列队尾
	int level = 0; // 层数，初始值为0
	queue<BiTNode<NODETYPE> *> Q;

	Q.push(rootPtr);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back) // 如果p == 每层的最右边的结点，则层数+1，同时重新赋值队尾结点
		{
			level++;
			if (!Q.empty()) // 如果队列为空，则下一步的操作出错。主要用于防止最后一个结点弹出队列之后的那次操作
				back = Q.back();
		}
	}

	return level;
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PreOrderTraverse()
{
	PreOrderTraverseHelper(rootPtr);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PreOrderTraverseHelper(BiTNode<NODETYPE> *T)
{
	if (!T)
		return;

	visit(T);
	PreOrderTraverseHelper(T->lchild);
	PreOrderTraverseHelper(T->rchild);
}

// 前序遍历非递归形式
template<typename NODETYPE>
void BiTree<NODETYPE>::PreOrderNonRecursion()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	stack<BiTNode<NODETYPE> *> S; // 借助栈实现非递归的前序遍历

	p = rootPtr;
	while (p || !S.empty())
	{
		while (p) 
		{
			visit(p); // 在每次入栈之前进行访问
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			S.pop();
			p = p->rchild;
		}
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::InOrderTraverse()
{
	InOrderTraverseHelper(rootPtr);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::InOrderTraverseHelper(BiTNode<NODETYPE> *T)
{
	if (!T)
		return;

	InOrderTraverseHelper(T->lchild);
	visit(T);
	InOrderTraverseHelper(T->rchild);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::InOrderNonRecursion()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	stack<BiTNode<NODETYPE> *> S;

	p = rootPtr;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			S.pop();
			visit(p); // 在每次出栈之时进行访问
			p = p->rchild;
		}
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PostOrderTraverse()
{
	PostOrderTraverseHelper(rootPtr);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PostOrderTraverseHelper(BiTNode<NODETYPE> *T)
{
	if (!T)
		return;

	PostOrderTraverseHelper(T->lchild);
	PostOrderTraverseHelper(T->rchild);
	visit(T);
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PostOrderNonRecursion()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	BiTNode<NODETYPE> *r; // 用于记录栈中弹出的结点的右子树是否访问过
	stack<BiTNode<NODETYPE> *> S;

	p = rootPtr;
	r = NULL;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			if (p->rchild && p->rchild != r) // 此结点的右子树尚未入栈
			{
				p = p->rchild;
				S.push(p);
				p = p->lchild;
			}
			else
			{
				S.pop();
				visit(p); // 每次出栈时访问结点
				r = p;
				p = NULL;
			}
		}
	}

}

template<typename NODETYPE>
void BiTree<NODETYPE>::LevelOrderTraverse()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	BiTNode<NODETYPE> *back; // 操作中记录队列尾部的指针
	queue<BiTNode<NODETYPE> *> Q; // 使用辅助队列

	Q.push(rootPtr);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();
		visit(p);

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PrintLast()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	BiTNode<NODETYPE> *back; // 操作中记录队列尾部的指针
	queue<BiTNode<NODETYPE> *> Q; // 使用辅助队列

	Q.push(rootPtr);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back)
		{
			visit(p);
			if (!Q.empty())
				back = Q.back(); // 更新back指针的位置
		}
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::PrintByDepth()
{
	if (!rootPtr)
		return;

	BiTNode<NODETYPE> *p;
	BiTNode<NODETYPE> *back; // 操作中记录队列尾部的指针
	queue<BiTNode<NODETYPE> *> Q; // 使用辅助队列

	Q.push(rootPtr);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();
		visit(p);

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back)
		{
			cout << endl;
			if (!Q.empty())
				back = Q.back(); // 更新back指针的位置
		}
	}
}

template<typename NODETYPE>
void BiTree<NODETYPE>::visit(BiTNode<NODETYPE> *p)
{
	cout << left << setw(5) << p->data;
}

#endif

为了省事，main函数有些代码直接使用了前面一篇文章里面c的代码。

// main.h
#include <iostream>
#include "BiTree.h"
using namespace std;

int main()
{
	int i;
	BiTree<char> T;
	char e1;
	
	//StrAssign(str,"ABDH#K###E##CFI###G#J##");

	T.CreateBiTree();

	printf("构造空二叉树后,树空否？%d(1:是 0:否) 树的深度: %d\n",T.BiTreeEmpty(), T.BiTreeDepthNonRecursion());
	e1 = T.Root();
	printf("二叉树的根为: %c\n",e1);

	printf("\n前序遍历二叉树:\n");
	//T.PreOrderTraverse();
	T.PreOrderNonRecursion();

	printf("\n中序遍历二叉树:\n");
	T.InOrderTraverse();
	//T.InOrderNonRecursion();

	printf("\n后序遍历二叉树:\n");
	//T.PostOrderTraverse();
	T.PostOrderNonRecursion();

	printf("\n层次遍历二叉树:\n");
	T.LevelOrderTraverse();

	printf("\n每行二叉树的最右边的结点为:\n");
	T.PrintLast();

	printf("\n按层次输出每行的结点:\n");
	T.PrintByDepth();

	T.DestroyBiTree();
	printf("\n清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",T.BiTreeEmpty(),T.BiTreeDepth());
	i = T.Root();
	if(!i)
		printf("树空，无根\n");

	getchar();
	getchar();
	return 0;
}

写这个代码的时候，感觉自己计算机编程入门了——之前写代码主要都是照着书写，出错了更多都是照着书查找错误。写这个二叉树类的时候有个地方指针出错了，自己设断点改错，改了很久。所以入门的一些经验在下面一篇文章里面谈谈吧。

参考资料：
1.《大话数据结构》
2.《C++大学教程（第七版）》

发布于

二叉树的实现以及相关操作C/C++

夏天看机器学习之余，把C语言给过了一遍，现在开始数据结构的学习了。最近看的二叉树，照着书实现了一下。

其中包括二叉树的一些基本操作：初始化，建立，销毁，判空，深度和几种遍历。因为书上没给出非递归的遍历的非递归形式，自己这边给总结一下。代码本来是用C写的，但是其中有些功能的实现需要用到队列或者栈，直接调用C++的STL了。如下是相关代码。



#include "string.h"
#include "stdio.h"    
#include "stdlib.h"   
#include "math.h"  
#include <queue>
#include <stack>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */

typedef int Status;

typedef char TElemType;
TElemType Nil = ' ';

/* 用于构造二叉树********************************** */
int index=1;
typedef char String[24]; /*  0号单元存放串的长度 */
String str;

Status StrAssign(String T,char *chars)
{ 
	int i;
	if(strlen(chars)>MAXSIZE)
		return ERROR;
	else
	{
		T[0]=strlen(chars);
		for(i=1;i<=T[0];i++)
			T[i]=*(chars+i-1);
		return OK;
	}
}
/* ************************************************ */

typedef struct BiTNode
{
	TElemType data;
	struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

Status InitBiTree(BiTree *T);
void CreateBiTree(BiTree *T);
void DestroyBiTree(BiTree *T);
Status BiTreeEmpty(BiTree T);
TElemType Root(BiTree T);
TElemType Value(BiTree p);
void visit(BiTree T);

int BiTreeDepth(BiTree T);
int BiTreeDepthNonRecursion(BiTree T);
int BiTreeDepthNonRecursion2(BiTree T);

void PreOrderTraverse(BiTree T);
void PreOrderNonRecursion(BiTree T);
void InOrderTraverse(BiTree T);
void InOrderNonRecursion(BiTree T);
void PostOrderTraverse(BiTree T);
void PostOrderNonRecurion(BiTree T);
void LevelOrderTraverse(BiTree T);

void PrintLastInEachLevel(BiTree T);
void PrintLevelOrderByLevel(BiTree T);

int main()
{
	int i;
	BiTree T;
	TElemType e1;
	InitBiTree(&T);
	
	//StrAssign(str,"ABDH#K###E##CFI###G#J##");

	CreateBiTree(&T);

	printf("构造空二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepthNonRecursion2(T));
	e1=Root(T);
	printf("二叉树的根为: %c\n",e1);

	printf("\n前序遍历二叉树:\n");
	PreOrderTraverse(T);
	//PreOrderNonRecursion(T);

	printf("\n中序遍历二叉树:\n");
	InOrderTraverse(T);
	//InOrderNonRecursion(T);

	printf("\n后序遍历二叉树:\n");
	PostOrderTraverse(T);
	//PostOrderNonRecurion(T);

	printf("\n层次遍历二叉树:\n");
	//LevelOrderTraverse(T);
	PrintLevelOrderByLevel(T);
	printf("\n输出每层的最后一个结点:\n");
	PrintLastInEachLevel(T);
	
	DestroyBiTree(&T);
	printf("\n清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
	i=Root(T);
	if(!i)
		printf("树空，无根\n");
	
	getchar();
	getchar();
	return 0;
}

//* 构造空二叉树T */
Status InitBiTree(BiTree *T)
{
	*T = NULL;
	return OK;
}

// 按前序输入二叉树中结点的值（一个字符）
// #表示空树，构造二叉链表表示二叉树T。 
void CreateBiTree(BiTree *T)
{
	TElemType ch;

	scanf("%c", &ch);

	if (ch == '#')
		(*T) = NULL;
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		if (!*T)
			exit(OVERFLOW);
		(*T)->data = ch;
		CreateBiTree(&(*T)->lchild);
		CreateBiTree(&(*T)->rchild);
	}
}

// 初始条件: 二叉树T存在。操作结果: 销毁二叉树T 
void DestroyBiTree(BiTree *T)
{
	if (*T)
	{
		if ((*T)->lchild)
			DestroyBiTree(&(*T)->lchild);
		if ((*T)->rchild)
			DestroyBiTree(&(*T)->rchild);
		free(*T);
		*T = NULL;
	}
}

// 初始条件：二叉树存在
// 操作结果：若T为空，则返回TRUE；否则返回FALSE
Status BiTreeEmpty(BiTree T)
{
	if (!T)
		return TRUE;
	else
		return FALSE;
}

// 初始条件：二叉树存在
// 操作结果：返回T的根
TElemType Root(BiTree T)
{
	if (!T)
		return Nil;
	else
		return T->data;
}

// 初始条件：节点存在
// 操作结果：输出结点的数据域
void visit(BiTNode *p)
{
	if (p)
		printf("%c ", p->data);
}

// 初始条件：二叉树存在
// 操作结果：返回二叉树深度
// 递归实现
int BiTreeDepth(BiTree T)
{
	if (!T)
		return 0;

	int i, j;

	if (T->lchild)
		i = BiTreeDepth(T->lchild); // 递归求出左子树高度
	else
		i = 0;

	if (T->rchild)
		j = BiTreeDepth(T->rchild); // 递归求出右子树高度
	else
		j = 0;

	return i > j ? i+1 : j+1;
}

// 求二叉树高度的非递归形式
int BiTreeDepthNonRecursion(BiTree T)
{
	if (!T)
		return 0;

	queue<BiTNode *> Q; // 借助队列实现层次遍历，从而求出高度
	BiTNode *p; // 记录队列头部
	BiTNode *back; // 记录队列尾部指针
	int level = 0; // 队列高度

	Q.push(T);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back)
		{
			level++;
			if (!Q.empty()) // 防止最后Q为空时出错
				back = Q.back();
		}
	}

	return level;
}

// 求二叉树高度的非递归形式
int BiTreeDepthNonRecursion2(BiTree T)
{
	BiTNode *Q[MAXSIZE]; // 借助队列实现层次遍历，从而求出高度。此时用数组实现队列
	int level = 0; // 二叉树高度
	int last = 0; // 每层次最后一个结点
	int front = -1; // 队列头指针
	int rear = -1; // 队列尾指针
	BiTNode *p;

	Q[++rear] = T;
	last = rear;
	while (front < rear) // 队列不空
	{
		p = Q[++front];

		if (p->lchild)
			Q[++rear] = p->lchild;
		if (p->rchild)
			Q[++rear] = p->rchild;

		if (front == last)
		{
			level++;
			if (front < rear)
				last = rear;
		}
	}

	return level;
}

// 初始条件：二叉树存在
// 操作结果：前序遍历二叉树
void PreOrderTraverse(BiTree T)
{
	if (!T)
		return;

	visit(T);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

// 前序遍历非递归形式
void PreOrderNonRecursion(BiTree T)
{
	if (!T)
		return;

	stack<BiTNode *> S; // 借助栈实现非递归遍历
	BiTNode *p;

	p = T;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			visit(p); // 在每次入栈时进行访问
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top(); 
			S.pop();
			p = p->rchild;
		}
	}
}

// 初始条件：二叉树存在
// 操作结果：中序遍历二叉树
void InOrderTraverse(BiTree T)
{
	if (!T)
		return;

	InOrderTraverse(T->lchild);
	visit(T);
	InOrderTraverse(T->rchild);
}

// 中序遍历二叉树非递归形式
void InOrderNonRecursion(BiTree T)
{
	if (!T)
		return;

	stack<BiTNode *> S;
	BiTNode *p;
	
	p = T;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			S.pop();
			visit(p); // 每次从栈中弹出的时候访问结点
			p = p->rchild;
		}
	}
}


// 初始条件：二叉树存在
// 操作结果：后序递归遍历二叉树
void PostOrderTraverse(BiTree T)
{
	if (!T)
		return;

	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	visit(T);
}

// 后序遍历非递归形式
// 难点是分清栈中弹出根结点时，是从左子树弹出还是右子树弹出。所以使用辅助指针r。
void PostOrderNonRecurion(BiTree T)
{
	if (!T)
		return;

	stack<BiTNode *> S;
	BiTNode *p;
	BiTNode *r; // 用指针r记录最近访问的结点

	p = T;
	r = NULL;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			p = p->lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			if (p->rchild && p->rchild != r) // 如果右子树存在，且未访问过
			{
				p = p->rchild;
				S.push(p);
				p = p->lchild;
			}
			else
			{
				S.pop();
				visit(p);
				r = p;
				p = NULL;
			}
		}
	}
}

// 初始条件：二叉树存在
// 操作结果：层次遍历二叉树
void LevelOrderTraverse(BiTree T)
{
	if (!T)
		return;

	queue<BiTNode *> Q; // 借助队列实现层次遍历
	BiTNode *p;

	Q.push(T);
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();
		visit(p); // 每次弹出的时候访问结点

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);
	}
}

// 初始条件：二叉树存在
// 操作结果：访问每层二叉树最右边的结点
void PrintLastInEachLevel(BiTree T)
{
	if (!T) // 如果树为空，则返回
		return;

	queue<BiTNode *> Q;
	BiTNode *p;
	BiTNode *back; // 指向每层最后一个结点的指针

	Q.push(T);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back)
		{
			visit(p);
			if (!Q.empty())
				back = Q.back();
		}
	}
}

// 初始条件：二叉树存在
// 操作结果：分行输出每层二叉树的结点
void PrintLevelOrderByLevel(BiTree T)
{
	if (!T)
		return;

	queue<BiTNode *> Q;
	BiTNode *p;
	BiTNode *back; // 记录每层最右边的结点，从而实现分行输出

	Q.push(T);
	back = Q.back();
	while (!Q.empty())
	{
		p = Q.front();
		Q.pop();
		visit(p);

		if (p->lchild)
			Q.push(p->lchild);
		if (p->rchild)
			Q.push(p->rchild);

		if (p == back)
		{
			putchar('\n');
			if (!Q.empty())
				back = Q.back();
		}
	}
}

本身感觉现在这些在计算机专业里面应该是太基础的东西了，不想贴出来的，但是确实这个算是一个里程碑吧——感觉自己对编程有点入门了。下一篇会把用类实现的二叉树的代码贴上来，之后再写点自学编程上面的一些感悟或者说一些经验吧。

参考资料：

1.《大话数据结构》

发布于

顺序单链表插入新节点的一种方法

在学习链表的时候我们都接触过单链表插入新结点的问题。其中有一类就是在顺序链表中插入新节点，并保持链表的递增或者递减性质。

最近看《C和指针》一书中提到了一种方法，我个人感觉不错，并且思想非常好。

这是最常见的思维：

//sll_node.h  
  
typedef struct Node  
{  
    int value;  
    Node *next;  
} Node;  

#include "sll_node.h"  
#include <stdio.h>  
  
#define TRUE    1  
#define FALSE   0  
  
// insertNode:把newValue的值插入到递增排序的链表中，正确返回TRUE，错误返回FALSE  
// rootp是链表的头指针。  
int insertNode(Node **rootp, int newValue)  
{  
    Node *newNode; // 新节点的指针  
    Node *previous; // 当前指针的前一个指针  
    Node *current; // 当前指针  
  
    current = *rootp; // 初始化  
    previous = NULL;  
  
    // 查找插入的位置  
    while (current != NULL && current->value < newValue)
    {
        previous = current;
        current = current->next;
    }
  
    // 给新节点分配空间  
    newNode = (Node *)malloc(sizeof(Node));  
    if (newNode == NULL)  
        return FALSE;  
    newNode->value = newValue;  
  
    // 更改新节点的前驱和后继节点  
    newNode->next = current;  
    if (previous == NULL) // 此时插入节点的为链表中第一个节点，修改头指针  
        *rootp = newNode;  
    else  
        previous->next = newNode;

    return TRUE;
}

我以前编写的时候也会用这样的方法：一个当前指针和指向当前指针之前的指针，这样需要讨论原链表是否为空。书中提到了一种抽象，每次插入新的节点，都是改变一个指向这个新节点的指针以及指向下一个节点，这样可以省略讨论插入的节点是否为第一个节点的步骤。代码如下：

#include "sll_node.h"
#include <stdio.h>

#define	FALSE	0
#define TRUE	1

// insertNode2:把newValue的值插入到递增排序的链表中，正确返回TRUE，错误返回FALSE
// nextp是指向当前节点的指针，最初是头指针
int insertNode2(Node **nextp, int newValue)
{
	Node *newNode; // 新节点指针
	Node *current; // 当前节点指针

	current = *nextp; // 最初当前节点为nextp指针指向的节点
	// 查找新插入节点的位置
	while (current != NULL && current->value < newValue)
	{
		nextp = &current->next;
		current = current->next;
	}

	// 为新节点分配内存
	newNode = (Node *)malloc(sizeof(Node));
	if (newNode == NULL)
		return FALSE;
	newNode->value = newValue;

	// 统一了插入的步骤。即：每次插入，都是前一个指针指向新节点，新节点指向下一个节点
	*nextp = newNode;
	newNode->next = current;

	return TRUE;
}

main函数

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "sll_node.h"

int insertNode(Node **rootp, int newValue);
int insertNode2(Node **nextp, int newValue);

int main()
{
	srand(time(0));

	Node *head = (Node *)malloc(sizeof(Node));
	head->next = NULL;

	for (int i = 0; i < 5; i++)
	{
		int temp = rand() % 50;
		printf("%d\n", temp);
		//insertNode(&head,temp);
		insertNode2(&head,temp);
	}
	
	Node *p = head->next;
	while (p != NULL)
	{
		printf("%d\n", p->value);
		p = p->next;
	}

	getchar();
	getchar();
	return 0;
}

因为我个人没有经过正经的课堂训练，自己考研才接触编程、数据结构之类的。看了很多对自学编程提的建议都是多编写，并且要有抽象的思想，所以将这个方法写了下来，可能对很对科班出身的人不算什么问题了吧。

我感觉这个抽象很好，希望是给自己编程道路的一个好的开端吧:)

同时，因为我在初学时发现测试代码也会花费很多时间，所以将完成的代码都贴了上来，而不仅仅是函数，希望也能帮助到更多的想我这样的初学者吧。