1.节点度数不超过2的树称作二叉树

深度为k的节点，之多2^k个

含n个节点，高度为h的二叉树中：h<n<2^(k+1)

n=k+1时，化为一条单链

n=2^(k+1)-1时，为满二叉树

2.二叉树描述多叉树

凡是有根且有序的树，均可以用二叉树描述

首先将多叉树采用firstChild()和nextSibling()方法进行表示

3.二叉树的实现：

BinNode的组成：lChild,parent,rChild,data,height,npl,color

4.计算树的规模(采用递归)

int size(){    int s=1;    if(lChild)        s+=lChild->size();    if(rChild)            s+=rChild->size();    return s;}

5.高度更新

空树的高度为-1

#define stature(p) ((p) ? (p) -> height  :  -1)

任意节点的高度等于其左子树的高度和右子树的高度的较大者加一

int update( x ){    return x->height=1+max(stature(x->lChild), stature(x->rChild));}

更新V及其历代祖先的高度

void updateHightAbove(x){     while(x){          updateHeight(x);          x=x->parent;     }}

6.节点插入算法

7.遍历

先序(V | L | R)，中序(L | V | R)，后序(L | R | V)

递归实现 void traverse(BinNodePosi(T) x, VST & visit){     if(!x) return;     visit(x->data);     traverse(x->lChild, visit);     traverse(x->rChild, visit);}//T(n)=O(1)+T(a)+T(n-a-1)=O(n)

使用迭代实现先序遍历 思路一：使用栈 void travPre(BinNodePosi(T) x, VST & visit){    Stack
     
       S;    if(x) S.push(x);    while(!S.empty()){        x=S.pop();        visit(x->data);        if(HasRChild(*x))               S.push(x->rChild);        if(HasLChild(*x))              S.push(x->lChild);    }} java实现： public static void main(String[] args){
       Node header = createTree();      Stack
      
        nodeStack=new Stack
       
        ();   if(headler!=null)    nodeStack.push(header);      while(!nodeStack.empty()){
        Node node=nodeStack.pop();    System.out.println(node.getData());    if(node.getRchild()!=null)     nodeStack.push(node.getRchild());    if(node.getLchild()!=null)     nodeStack.push(node.getLchild());   }  } 思路二：首先自顶向下依次访问左侧链的节点，每访问一个节点，将其右节点入栈，然后自底向上的依次访问每个层次上的右子树  public static void travPre(Node x){
       Stack
        
          s=new Stack
         
          ();   while(true){
        visitAlongLeftBranch(x,s);    if(s.empty())     break;    x=s.pop();   }  }  public static void visitAlongLeftBranch(Node x,Stack
          
            s){   while(x!=null){    System.out.println(x.getData());    s.push(x.getRchild());    x=x.getLchild();   }  }
          
         
        
       
      
     

 中序遍历

当子树的根被扫描到后，会将其控制权转交到左孩子

public static void travIno(Node x){        Stack
     
       s=new Stack
      
       ();        while(true){            goAlongLeftBranch(x,s);            if(s.empty())                break;            x=s.pop();            System.out.print(x.getData());            x=x.getRchild();        }        }        public static void goAlongLeftBranch(Node x,Stack
       
         s){        while(x!=null){            s.push(x);            x=x.getLchild();        }    }
       
      
     

层次遍历：使用队列

根节点先入列，然后取出并访问，将该节点的左、右节点先后入队，如此循环

8.二叉树反向重构

[先序|后序] + 中序

preorder: r     L     R

inorder: L     r     R

思路：首先根据preorder中的r，在inorder找到r的位置并将L和R分解出来，再根据的inorder中的L和R，将preorder的L和R分解出来

[先序+后序] x 真

真二叉树：节点的度为0和2