采用面向对象完成二叉树（使用JavaScript如何实现二叉树遍历）

本文目录

• 使用JavaScript如何实现二叉树遍历
• 数据结构代码（用C语言） 二叉树的操作
• 全国计算机等级考试二级教程的内容简介
• 二叉树的建立及基本操作
• 计算机基础知识对程序员来说有多重要
• 计算机二级考试C语言编程环境是什么

使用JavaScript如何实现二叉树遍历

这篇文章主要介绍了JavaScript实现二叉树定义、遍历及查找的方法,结合实例形式较为详细的分析了二叉树的相关概念及javascript构建二叉树、遍历、查找二叉树的常用操作技巧,需要的朋友可以参考下
本文实例讲述了JavaScript实现二叉树定义、遍历及查找的方法。分享给大家供大家参考，具体如下：
二叉树（binary tree）
在写这篇文章之前说一下数据结构和算法这个系列，这个系列包含了很多东西，比如啥子排序，线性表，广义表，树，图这些大家都是知道的，但是这些东西我们学了之后工作中能用到的又有多少呢，据我所知绝大部分公司，一线码农，_丝，程序猿是用不到这些东西，既然这样为啥子我还要强调这个系列呢，本人觉得算法和数据结构是程序的基本功，前提想脱离一线码农，普通程序猿行列，说得通俗一点就是让自己变的更牛逼。其次语言都是想通的，只要是掌握了一门语言学习其他语言就如同顺水推舟，不费一点力气。另外还有一点就是我会一直把这个系列写下去， 虽然网上一搜一大筐，已经写烂了，但是我写作的目的有两个，第一和大家分享， 第二可以让自己更深入的理解。好了，其他的不多说了，最近复习了一下二叉树， 就先写这个，后面会依次的加上排序， 线性表，广义表。。等等
二叉树
一说到二叉树我们肯定会问，什么是二叉树，二叉树是个啥子东东，拿来有啥子用嘛，我们为啥子要学习它嘛？ 如果当初你在学习二叉树的时候你没有问过自己这些问题，那么你对它的了解也仅仅也只是了解。那我们现在来说说什么是二叉树，二叉树就是一种数据结构， 它的组织关系就像是自然界中的树一样。官方语言的定义是：是一个有限元素的集合,该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。至于为啥子要学习它，妈妈总是说，孩子，等你长大了就明白了。
二叉树的性质
性质1：二叉树第i层上的节点数目最多为2i-1(i≥1);
性质2：深度为k的二叉树至多有2k-1个结点(k≥1)。
性质3： 在任意-棵二叉树中，若叶子结点（即度为0的结点）的个数为n0，度为1的结点数为n1，度为2的结点数为n2，则no=n2+1。
二叉树的存储结构与构建
二叉树的存储方式有两种，一种顺序存储，比如:
var binaryTree = ; 一般情况下顺序存储的这种结构用的较少，另外一种存储方式就是链式存储，下面我会用代码来详细描述二叉树式结构的构建与存储方式，构建二叉树也有两种方式一种是递归方式构建，这种很简单，另一种是非递归方法构建，这种呢相对于前一种复杂一点点，不过也不用担心，我在代码中加上详细的注释，一步一步的走下去。我们现在就以26个英文字母来构建二叉树
代码如下:
var charecters = ;
在构建二叉树之前我们会用到一个节点对象，节点对象如下：（注意：关于javascript的面向对象，原型，语法特点我会放在javascript语言知识点这个系列）
/*
*二叉树的节点对象
*/
function Node() {
this.text = ’’; //节点的文本
this.leftChild = null; //节点的左孩子引用
this.rightChild = null; //节点右孩子引用
}递归构建二叉树
在构建好二叉树节点之后我们紧接着用递归来构建二叉树
var charecters = ;
function buildTree(node, i) {
var leftIndex = 2*i+1, //左孩子节点的索引
rightIndex = 2*i+2; //右孩子节点的索引
if(leftIndex 《 charecters.length) { //判断索引的长度是否超过了charecters数组的大小
var childNode = new Node(); //创建一个新的节点对象
childNode.text = charecters; //给节点赋值
node.leftChild = childNode; //给当前节点node加入左孩子节点
buildTree(childNode, leftIndex); //递归创建左孩子
}
if(rightIndex 《 charecters.length) { //下面注释参照上面的构建左孩子的节点
var childNode = new Node();
childNode.text = charecters;
node.rightChild = childNode;
buildTree(childNode, rightIndex);
}
}
//下面构造二叉树
var node = new Node();
node.text = charecters;
buildTree(node, 0); //索引i是从0开始构建非递归构建二叉树
下面是以非递归方式构建二叉树：
var root;
function createBinaryTree() {
var len = charecters.length, //数组的长度
index = 0, //索引从0开始
nodes = new Array(); //创建一个临时数组，用于存放二叉树节点
//循环创建二叉树节点存放到数组中
for (var i = 0 ; i 《 charecters.length ; i++) {
var node = new Node();
node.text = charecters;
nodes.push(node);
}
//循环建立二叉树子节点的引用
while(index 《 len) {
var leftIndex = 2*index+1, //当前节点左孩子索引
rightIndex = 2*index+2; //当前节点右孩子索引
//给当前节点添加左孩子
nodes;
//给当前节点添加右孩子
nodes;
index++;
}
root = nodes;
}二叉树的三种遍历
好了，现在我们已经成功构建了二叉树的链式结构，在构建了二叉树的链式结构后我们进入二叉树的最基本的遍历了，遍历有三种最基本的遍历，我不说想必大家都知道，先序遍历，中序遍历和后续遍历。虽然这三种遍历递归方式都比较简单，但非递归方式就不是那么容易了，当时我在实现的时候都卡了半天，真的是说起来容易做起来难啊，在实现遍历前我们首先要来实现的是栈，因为在非递归遍历的时候会用到栈，那到底什么是栈呢，这里我就简单介绍下吧，有兴趣的朋友可以去维基百科有权威的定义，栈和队列也是一种数据结构，栈存放数据的时候是先进先出，而队列是先进后出。
实现栈的对象
下面用javascript来实现栈的对象
function Stack() {
var stack = new Array(); //存放栈的数组
//压栈
this.push = function(o) {
stack.push(o);
};
//出栈
this.pop = function() {
var o = stack;
stack.splice(stack.length-1, 1);
return o;
};
//检查栈是否为空
this.isEmpty = function() {
if(stack.length 《= 0) {
return true;
}
else {
return false;
}
};
}
//使用方式如下
var stack = new Stack();
stack.push(1); //现在栈中有一个元素
stack.isEmpty(); //false , 栈不为空
alert(stack.pop()); //出栈, 打印1
stack.isEmpty(); //true, 此时栈为空，因为在调用了stack.pop()之后元素出栈了，所以为空1. 先序遍历
在实现了栈对象以后我们首先来进行先序遍历的递归方式
function firstIteration(node) {
if(node.leftChild) { //判断当前节点是否有左孩子
firstIteration(node.leftChild); //递归左孩子
}
if(node.rightChild) { //判断当前节点是否有右孩子
firstIteration(node.rightChild); //递归右孩子
}
}
//递归遍历二叉树
firstIteration(root);先序遍历的非递归方式
上面的代码大家可以在firstIteration()方法中加个alert()函数来验证是否正确。那么下面就要说说先序遍历的非递归方式，遍历思想是这样的：先访问根节点在访问左节点， 最后访问右节点。从根节点一直往下访问找左孩子节点，直到最后一个左孩子节点（将这条路径保存到栈中），然后再访问最后一个左孩子的兄弟节点（右孩子节点），之后回溯到上一层（将栈中的元素取出 就是出栈），又开始从该节点（回溯到上一层的节点）一直往下访问找左孩子节点... 直到栈中的元素为空，循环结束。
function notFirstIteration(node) {
var stack = new Stack(), //开辟一个新的栈对象
resultText = ’’; //存放非递归遍历之后的字母顺序
stack.push(root); //这个root在上面非递归方式构建二叉树的时候已经构建好的
var node = root;
resultText += node.text;
while(!stack.isEmpty()) {
while(node.leftChild) { //判断当前节点是否有左孩子节点
node = node.leftChild; //取当前节点的左孩子节点
resultText += node.text; //访问当前节点
stack.push(node); //将当前节点压入栈中
}
stack.pop(); //出栈
node = stack.pop().rightChild; //访问当前节点的兄弟节点（右孩子节点）
if(node) { //当前节点的兄弟节点不为空
resultText += node.text; //访问当前节点
stack.push(node); //将当前节点压入栈中
}
else { //当前节点的兄弟节点为空
node = stack.pop(); //在回溯到上一层
}
}
}
//非递归先序遍历
notFirstIteration(root);2. 中序遍历
只要把思路理清楚了现实起来其实还是挺容易的，只要我们熟悉了一种二叉树的非递归遍历方式，其他几种非递归方式就容易多了，照着葫芦画瓢，下面是中序遍历的递归方式，中序遍历的思想是：先访问左孩子节点，在访问根节点，最后访问右节点
var strText = "";
function secondIteration(node) {
//访问左节点
if(node.leftChild) {
if(node.leftChild.leftChild) {
secondIteration(node.leftChild);
}
else {
strText += node.leftChild.text;
}
}
//访问根节点
strText += node.text;
//访问右节点
if(node.rightChild) {
if(node.rightChild.leftChild) {
secondIteration(node.rightChild);
}
else {
strText += node.rightChild.text;
}
}
}
secondIteration(root);
alert(strText);中序遍历的非递归方式
思想是：1. 从根节点一直往下找左孩子节点，直到找到最后一个左孩子节点（用栈将此路径保存，但不访问）2.访问最后一个左孩子节点，然后再访问根节点（要先弹出栈，就是在栈中取上一层节点）3.在访问当前节点（最后一个左孩子节点）的兄弟节点（右孩子节点），这里要注意如果兄弟节点是一个叶节点就直接访问，否则是兄弟节点是一颗子树的话不能马上访问，要先来重复 1， 2，3步骤， 直到栈为空，循环结束
function notSecondIteration() {
var resultText = ’’,
stack = new Stack(),
node = root;
stack.push(node);
while(!stack.isEmpty()) {
//从根节点一直往下找左孩子节点直到最后一个左孩子节点，然后保存在栈中
while(node.leftChild) {
node = node.leftChild;
stack.push(node);
}
//弹出栈
var tempNode = stack.pop();
//访问临时节点
resultText += tempNode.text;
if(tempNode.rightChild) {
node = tempNode.rightChild;
stack.push(node);
}
}
alert(resultText);
}3. 后续遍历
最后就还剩下一种遍历方式，二叉树的后续遍历，后续遍历的思想是：先访问左孩子节点，然后在访问右孩子节点，最后访问根节点
后续遍历的递归方式
var strText = ’’;
function lastIteration(node) {
//首先访问左孩子节点
if(node.leftChild) {
if(node.leftChild.leftChild) {
lastIteration(node.leftChild);
}
else {
strText += node.leftChild.text;
}
}
//然后再访问右孩子节点
if(node.rightChild) {
if(node.rightChild.rightChild) {
lastIteration(node.rightChild);
}
else {
strText += node.rightChild.text;
}
}
//最后访问根节点
strText += node.text;
}
//中序递归遍历
lastIteration(root);
alert(strText);后续非递归遍历
后续非递归遍历的思想是：1.从根节点一直往下找左孩子节点，直到最后一个左孩子节点（将路径保存到栈中，但不访问）2.弹出栈访问最后一个左孩子节点 3.进入最后一个左孩子节点的兄弟节点，如果兄弟节点是叶节点就访问它，否则将该节点重复 1， 2步骤, 直到栈中的元素为空，循环结束。3.访问根节点
function notLastIteration() {
var strText = ’’,
stack = new Stack();
nodo = root;
stack.push(node);
while(!stack.isEmpty()) {
while(node.leftChild) {
node = node.leftChild;
stack.push(node);
}
//弹出栈
var tempNode = stack.pop();
//访问左孩子节点
strText += tempNode.text;
//访问右孩子节点
if(tempNode.rightChild) {
if(tempNode.rightChild.leftChild || tempNode.rightChild.rightChild) { //判断最后一个左孩子节点的兄弟节点是否为页节点
stack.push(tempNode.rightChild);
}
else {
strText += tempNode.rightChild.text;
}
}
}
alert(strText);
}上面是我整理给大家的，希望今后会对大家有帮助。
相关文章：
如何使用vuex实现菜单管理
详细解读Angular5.1新功能
使用nodejs如何实现gulp打包
在vue2中通过keep-alive如何使用
在webpack中有关于jquery插件的环境配置（详细教程）

数据结构代码（用C语言） 二叉树的操作

# include 《stdio.h》
# include 《malloc.h》
struct BTNode
{
int data;
struct BTNode * pLchild;//p是指针，L是左，child是孩子
struct BTNode * pRchild;
};
//函数声明
struct BTNode * CreateBTree(void);//创建树
void PreTraverseBTree(struct BTNode * pT);//先序遍历
void InTraverseBTree(struct BTNode * pT);//中序遍历
void PostTraverseBTree(struct BTNode * pT);//后续遍历
int main(void)
{
struct BTNode * pT = CreateBTree();
PreTraverseBTree(pT);
printf("\n");
InTraverseBTree(pT);
printf("\n");
PostTraverseBTree(pT);
return 0;
}
//创建树
struct BTNode * CreateBTree(void)
{
struct BTNode * pA = (struct BTNode * )malloc(sizeof(BTNode));
struct BTNode * pB = (struct BTNode * )malloc(sizeof(BTNode));
struct BTNode * pC = (struct BTNode * )malloc(sizeof(BTNode));
struct BTNode * pD = (struct BTNode * )malloc(sizeof(BTNode));
struct BTNode * pE = (struct BTNode * )malloc(sizeof(BTNode));
pA-》data = ’A’;
pB-》data = ’B’;
pC-》data = ’C’;
pD-》data = ’D’;
pE-》data = ’E’;
pA-》pLchild = pB;
pA-》pRchild = pC;
pB-》pLchild = NULL;
pB-》pRchild = NULL;
pC-》pLchild = pD;
pC-》pRchild = NULL;
pD-》pLchild = NULL;
pD-》pRchild = pE;
pE-》pLchild = NULL;
pE-》pRchild = NULL;
return pA;
}
//先序遍历
void PreTraverseBTree(struct BTNode * pT)
{ //先访问根节点，再先序访问左子树，最后先序访问右子树
if ( pT != NULL)
{
printf("%c\n",pT-》data);//访问根节点
//pT-》pLchild可以代表整个左子树
PreTraverseBTree(pT-》pLchild);
PreTraverseBTree(pT-》pRchild);
}
return;
}
//中序遍历
void InTraverseBTree(struct BTNode * pT)
{
if(pT != NULL )
{
if (NULL != pT-》pLchild)
{
InTraverseBTree(pT-》pLchild);
}
printf("%c\n",pT-》data);
if (NULL != pT-》pRchild)
{
InTraverseBTree(pT-》pRchild);
}
}
return;
}
//后续遍历
void PostTraverseBTree(struct BTNode * pT)
{
if(pT != NULL )
{
if (NULL != pT-》pLchild)
{
PostTraverseBTree(pT-》pLchild);
}
if (NULL != pT-》pRchild)
{
PostTraverseBTree(pT-》pRchild);
}
printf("%c\n",pT-》data);
}
return;
}

全国计算机等级考试二级教程的内容简介

本系列丛书依据教育部考试中心最新发布的《全国计算机等级考试大纲(2013年版)》以及作者多年对等级考试的研究编写而成，旨在帮助考生（尤其是非计算机专业的初学者）学习相关内容，顺利通过考试。
目录 　　第1章数据结构与算法　　1.1算法　　1.1.1什么是算法　　1.1.2算法复杂度　　1.2数据结构的基本概念　　1.2.1什么是数据结构　　1.2.2数据结构的图形表示　　1.2.3线性结构与非线性结构　　1.3线性表及其顺序存储结构　　1.3.1线性表的基本概念　　1.3.2线性表的顺序存储结构　　1.3.3线性表的插入运算　　1.3.4线性表的删除运算　　1.4栈和队列　　1.4.1栈及其基本运算　　1.4.2队列及其基本运算　　1.5线性链表　　1.5.1线性链表的基本概念　　1.5.2线性链表的基本运算　　1.5.3循环链表及其基本运算　　1.6树与二叉树　　1.6.1树的基本概念　　1.6.2二叉树及其基本性质　　1.6.3二叉树的存储结构　　1.6.4二叉树的遍历　　1.7查找技术　　1.7.1顺序查找　　1.7.2二分法查找　　1.8排序技术　　1.8.1交换类排序法　　1.8.2插入类排序法　　1.8.3选择类排序法　　1.8.4排序方法比较　　课后总复习　　第2章程序设计基础　　2.1程序设计方法与风格　　2.2结构化程序设计　　2.2.1结构化程序设计方法的　　重要原则　　2.2.2结构化程序的基本结构与　　特点　　2.2.3结构化程序设计的注意　　事项　　2.3面向对象的程序设计　　2.3.1面向对象方法的基本　　概念　　2.3.2面向对象方法的优点　　课后总复习　　第3章软件工程基础　　3.1软件工程基本概念　　3.1.1软件的定义及软件的特点　　3.1.2软件危机　　3.1.3软件工程　　3.1.4软件工程过程　　3.1.5软件生命周期　　3.1.6软件开发工具与开发环境　　3.2结构化分析方法　　3.2.1需求分析　　3.2.2需求分析方法　　3.2.3结构化分析方法的常用　　工具　　3.2.4软件需求规格说明书　　3.3结构化设计方法　　3.3.1软件设计概述　　3.3.2概要设计　　3.3.3详细设计　　3.4软件测试　　3.4.1软件测试的目的和准则　　3.4.2软件测试方法　　3.4.3白盒测试的测试用例设计　　3.4.4黑盒测试的测试用例设计　　3.4.5软件测试的实施　　3.5程序的调试　　3.5.1程序调试的基本概念　　3.5.2软件调试方法　　课后总复习　　第4章数据库设计基础　　4.1数据库系统的基本概念　　4.1.1数据库、数据库管理系统与数据库系统　　4.1.2数据库技术的发展　　4.1.3数据库系统的基本特点　　4.1.4数据库系统体系结构　　4.2数据模型　　4.2.1数据模型的基本概念　　4.2.2ER模型　　4.2.3层次模型　　4.2.4网状模型　　4.2.5关系模型　　4.3关系代数　　4.3.1关系代数的基本运算　　4.3.2关系代数的扩充运算　　4.3.3关系代数的应用实例　　4.4数据库设计与管理　　4.4.1数据库设计概述　　4.4.2需求分析　　4.4.3概念设计　　4.4.4逻辑设计　　4.4.5物理设计　　4.4.6数据库管理　　课后总复习　　附录　　附录A全国计算机等级考试二级公共基础知识考试大纲　　附录B参考答案

二叉树的建立及基本操作

#include 《stdio.h》
typedef struct node
{
char data;
struct node * lchild;
struct node * rchild;
}BTNode;
BTNode * PreCreate() //先序建立
{
char ch = getchar();
if (ch = ’*’)
return NULL;
else
{
BTNode *p = (BTNode *)malloc(sizeof(BTNode));
p-》data = ch;
p-》lchild = PreCreate();
p-》rchild = PreCreate();
return p;
}

}
int leafNode(BTNode *t) //求叶子节点
{
if (t == NULL)
return 0;
else
{
int lleafCount = leafNode(t-》lchild);
int rleafCount = leafNode(t-》rchild);
if (!lleafCount && !rleafCount)
return 1;
else
return lleafCount + rleafCount;
}

}
void InOrderTraverse(BTNode *t)
{
InOrderTraverse(t-》lchild);
printf("%c ", t-》data);
InOrderTraverse(t-》rchild);
}
void PostOrderTraverse(BTNode *t)
{
PostOrderTraverse(t-》lchild);
PostOrderTraverse(t-》rchild);
printf("%c ", t-》data);

}

计算机基础知识对程序员来说有多重要

非常重要，必须认真学习。
学习基础知识从来都是枯燥的，而且很多时候会给我们一个错觉，就是基础知识没有用。这主要是因为，我们未来工作以后，更多的是面向应用，更直接的就是面向工具的使用，基础知识基本是不可能直接拿出来用的，所以，大家就会觉得我只要懂应用方面的知识就好了，基础知识根本不需要去学。
就拿程序员来举例：
很多的程序员培训机构，他们并不会教任何的基础知识，直接就是教编程语言，然后设计一些案例做练习，3个月-6个月基本就结束。这样教出来的程序员能够写代码吗？当然是能的，不然这些培训机构早垮了。而很多大学本科4年读完的应届生，说不定写代码都没有这些培训几个月的学生强，大学4年对于程序员来说难道就是白费吗？
并不是的。
基础知识决定的是你未来的高度，可能你作为一个初级、中级程序员，你不一定会用到数据结构、算法、编译原理。但初中级的程序员就是你未来几十年的全部吗？
如果是的，在你30多岁的时候，应该就会面对裁员了并且很难找到下一份工作。
程序员是一个干到老学到老的工作，每天都需要去学习一点新的知识，技术也是在不断的演进，需要去了解未来的技术发展方向，这样才能够一直产生价值。而基础知识是什么呢，就是当你对技术了解越深入时，越需要用到的东西。
例如：你要做大数据的工作时，你需要数据建模，需要在海量的数据中抽取自己需要的数据，还需要不影响系统的性能，运算速度更快。那么你就必须要了解算法，了解时间复杂度。如果你曾经大学时好好的学习了这些知识，并且时不时会温习一下，那么你更高更快的胜任这份工作。
但是，对于一个只是了解应用知识的程序员来说，他需要想办法学习你用4年时间堆积起来的知识，而且还不一定有可靠的老师能够教他。
再举个例子，现在华为需要一些技术人才，来做他方舟编译器的迭代，待遇非常可观。
而这时，对于懂数据结构、懂算法、懂编译原理的人来说，查的无非就是一些应用实践的知识，这些知识只要有基础、有环境，1-2周就可以上手。
但是对于只懂应用知识的人，他可能就是看都看不懂，华为也就不可能去招聘这样的人。
所以，程序员也是有高低之分的，有的年薪百万，有的年薪可能就十来万。谁不想拿百万年薪呢？可能他们也觉得某些知识没有用，所以没有去认真的学吧。

计算机二级考试C语言编程环境是什么

• 二级C使用的是Visual C++ 6.0平台

• 现在已经不用T C了,用Visual c++6.0中文版或英文版,现在学校都用英文版的,你要考证就下个英文版的练练