本文實例講述了JavaScript實現(xiàn)二叉樹定義、遍歷及查找的方法。分享給大家供大家參考，具體如下：

二叉樹（binary tree）

在寫這篇文章之前說一下數(shù)據(jù)結(jié)構(gòu)和算法這個系列，這個系列包含了很多東西，比如啥子排序，線性表，廣義表，樹，圖這些大家都是知道的，但是這些東西我們學了之后工作中能用到的又有多少呢，據(jù)我所知絕大部分公司，一線碼農(nóng)，屌絲，程序猿是用不到這些東西，既然這樣為啥子我還要強調(diào)這個系列呢，本人覺得算法和數(shù)據(jù)結(jié)構(gòu)是程序的基本功，前提想脫離一線碼農(nóng)，普通程序猿行列，說得通俗一點就是讓自己變的更牛逼。其次語言都是想通的，只要是掌握了一門語言學習其他語言就如同順水推舟，不費一點力氣。另外還有一點就是我會一直把這個系列寫下去， 雖然網(wǎng)上一搜一大筐，已經(jīng)寫爛了，但是我寫作的目的有兩個，第一和大家分享， 第二可以讓自己更深入的理解。好了，其他的不多說了，最近復(fù)習了一下二叉樹， 就先寫這個，后面會依次的加上排序， 線性表，廣義表。。。。等等

二叉樹

一說到二叉樹我們肯定會問，什么是二叉樹，二叉樹是個啥子東東，拿來有啥子用嘛，我們?yōu)樯蹲右獙W習它嘛？ 如果當初你在學習二叉樹的時候你沒有問過自己這些問題，那么你對它的了解也僅僅也只是了解。那我們現(xiàn)在來說說什么是二叉樹，二叉樹就是一種數(shù)據(jù)結(jié)構(gòu)， 它的組織關(guān)系就像是自然界中的樹一樣。官方語言的定義是：是一個有限元素的集合,該集合或者為空、或者由一個稱為根的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。至于為啥子要學習它，媽媽總是說，孩子，等你長大了就明白了。

二叉樹的性質(zhì)

性質(zhì)1：二叉樹第i層上的節(jié)點數(shù)目最多為2i-1(i≥1);
性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點(k≥1)。
性質(zhì)3： 在任意-棵二叉樹中，若葉子結(jié)點（即度為0的結(jié)點）的個數(shù)為n0，度為1的結(jié)點數(shù)為n1，度為2的結(jié)點數(shù)為n2，則no=n2+1。

二叉樹的存儲結(jié)構(gòu)與構(gòu)建

二叉樹的存儲方式有兩種，一種順序存儲，比如:
var binaryTree = ['a', 'b', 'c', 'd', 'e', 'f', 'h', 'i']; 這就是一顆二叉樹，假設(shè)binaryTree[i]是二叉樹的一個節(jié)點，那么它的左孩子節(jié)點 leftChild = binaryTree[i*2+1]那么相應(yīng)的右孩子節(jié)點 rightChild = binaryTree[i*2+2]; 一般情況下順序存儲的這種結(jié)構(gòu)用的較少，另外一種存儲方式就是鏈式存儲，下面我會用代碼來詳細描述二叉樹式結(jié)構(gòu)的構(gòu)建與存儲方式，構(gòu)建二叉樹也有兩種方式一種是遞歸方式構(gòu)建，這種很簡單，另一種是非遞歸方法構(gòu)建，這種呢相對于前一種復(fù)雜一點點，不過也不用擔心，我在代碼中加上詳細的注釋，一步一步的走下去。我們現(xiàn)在就以26個英文字母來構(gòu)建二叉樹