【二叉树链表】二叉树一般采用二叉树链表存储，基本思想是二叉树的每个节点对应一个链表节点，链表节点除了二叉树节点的相关数据信息外，还设置指示左右子节点的指针。
templateclass Tstruct Node{ T data； //存储数据域及其节点的信息的NodeT *lchild； //左指针字段，存储指向左孩子的指针，如果没有左孩子，则为空NodeT *rchild； //右指针字段，存储指向右子代的指针，右子代不存在时为空}； 如图所示，二叉链表的存储结构如下：
【实现类】templateclass Tstruct Node{ T data； Node *lchild，*rchild； (； templateclasstclassbitree { public : bi tree (； //构造函数，构造一棵二叉树(~BiTree ) )； //析构函数，每个节点的存储区域void countNode (； //计算二叉树的节点数void countLeaf ()； //计算二叉树的叶节点数void countHeight ()； //计算二叉树的高度void exchange ()； //调换左右子树voidpreorder({preorder ) )； void inOrder () (inorder ) ) root )； //按中顺序void postOrder () ) postorder ) ) root )； void levelOrder () (levelorder ) )根)； //private3360intnumnode=0； //二叉树的节点数int numLeaf=0； //二叉树叶节点的数量int heightTree=0； //二叉树的高度NodeT *root； //指向根节点的头指针NodeT *creat (； //构造函数调用voidrelease(nodet*Bt )； //析构函数调用voidcountnode(nodet*Bt )； //计算二叉树的节点数voidcountleaf(nodet*Bt )； //计算二叉树叶节点个数intcountheight(nodet*Bt )； //计算二叉树的高度voidexchange(nodet*Bt )//交换左右子树voidpreorder(nodet*Bt )；//向前遍历顺序(nodet * Bt )； //中顺序为voidpostorder(nodet*Bt )； //稍后为voidlevelorder(nodet*Bt )； //分层遍历}； 【构造函数】构造函数的功能是制作一棵二叉树。 因为用前序、中序、后序三种扫描方式无法唯一决定二叉树左右部分树的状况，所以针对这个问题，可以取“#”这样的特定值作为表示二叉树各节点的空指针为空的值。
将以上处理的二叉树称为原二叉树的扩展二叉树，可以通过扩展二叉树的一个遍历序列来唯一地确定一个二叉树。
templateclasstbitreet : bi tree () { root=creat )； } templateclasstnodet * bitreet : creat () { NodeT *root； T ch； cinch； if(ch=='# ' ) root=NULL； else{ root=new NodeT； root-data=ch； root-lchild=creat (； root-rchild=creat (； } return root； }【析构函数】templateclasstbitreet :3360~bi tree () release(root )； } templateclasstvoidbitreet :3360发行版(nodet * Bt ) if ) Bt！=空值() release(Bt-lchild )； 版本(Bt-rchild )； 删除Bt； }【计算二叉树节点数】templateclasstvoidbitreet 3360: count node () count node (root )； } templateclasstvoidbitreet :3360 count node (nodet * Bt ) if ) Bt！=null}{countnode(Bt-lchild )； numNode； 计数节点(Bt-lchild )； }【计算二叉树的叶节点个数】templateclasstvoidbitreet 3360: count leaf () countleaf(root )； } templateclasstvoidbitreet :3360 count leaf (nodet * Bt ) if ) Bt！=null(if ) Bt-lchild==nullBt-rchild==null ) leafcount=leafcount 1； ELSE{countleaf(Bt-Lchild )； 计数最低(Bt-rchild )； } }返回； }【计算二叉树的高度】templateclasstvoidbitreet 3360: count height () heighttree=countheight ) root )； } templateclasstintbitreet :3360 count height (nodet * Bt ) { int lHeight=0，rHeight=0； if (Bt==空) return 0； else { l height=count height (Bt-lchild )； rheight=countheight(Bt-rchild )； returnmax(Lheight，rHeight ) 1； }【交换左右子树】templateclasstvoidbitreet :3360 exchange (() exchange ) ) root )； } templateclasstvoidbitreet :3360 exchange (nodet * Bt ) if ) Bt！=空(exchange (Bt-lchild ) )； exchange(Bt-rchild； swap(Bt-lchild，bt-rchild )； }【遍历】1.templateclasstvoidbitreet 33603360 preorder (nodet * Bt ) if ) Bt==null ) return； else{ coutbt-data； preorder(Bt-lchild )； preorder(Bt-rchild )； }2. templateclasstvoidbitreet 3360: in order (nodet * Bt ) if ) Bt==null ) return； ELSE{inorder(Bt-Lchild )； coutbt-data； inorder(Bt-rchild )； }3. templateclasstvoidbitreet 3360: postorder (nodet * Bt ) if ) Bt==null ) return； ELSE{postorder(Bt-Lchild )； Postorder(Bt-Rchild )； coutbt-data； }4. templateclasstvoidbitreet 3360: level order (nodet * Bt ) ) { queueNodeT * Q； if(Bt！=NULL ) q.push(Bt )； while (！ Q.empty () { bt=Q.front； Q.pop (； coutbt-data； if(Bt-Lchild！=NULL ) q.push(Bt-lchild )； if(Bt-Rchild！=NULL ) q.push(Bt-rchild )； }