Tree

带父节点的二叉树的链式储存结构

class ChainTreeType
    {
        char NodeData; //data of nodes
        ChainTree LNode; //reference of left node
        ChainTree RNode;
        Chain PNode;
    }
    ChainTreeType root=null; //define root reference

初始化二叉树

CBTType InitTree()
    {
        CBTType node;
        if ((node=new CBTType())!=null)
        {
            System.out.println("enter a root data");
            node.data=input.next();
            node.left=null;
            node.right=null;
            
            if(node!=null)
            {
                return node;
            }
            else
            {
                return null;
            }
        }
        return null;
    }

增加结点

void AddTreeNode(CBTType treeNode)
    {
        CBTType pnode,parent;
        String data;
        int menusel;
        
        if((pnode=new CBTType())!=null)
        {
            System.out.println("enter node data");
            pnode.data=input.next();
            pnode.left=null;
            pnode.right=null;
            
            System.out.println("enter the parent's data of this node");
            data=input.next();
            
            parent= TreeFindNode(treeNOde,data);
            if(parent==null)
            {
                System.out.println("cannot find this parent node");
                pnode=null; //release memory
                return;
            }
            System.out.print("1.add this node to left\n,"
                    + "2.add this node to the right\n");
            do {
                menusel =input.nextInt();
                if(menusel ==1 || menusel ==2)
                {
                    if(parent==null)
                    {
                        System.out.println("no parent node, set parent node first");
                        
                    }else
                    {
                        switch(menusel) 
                        {
                          case 1:
                              if (parent.left!=null)
                              {
                                  System.out.println("the left node is not empty");
                              }
                              else
                              {
                                  parent.left=pnode;
                              }
                              break;
                          case 2 :
                              if (parent.right!=null)
                              {
                                  System.out.println("the right node is not empty");
                              }
                              else
                              {
                                  parent.right=pnode;
                              }
                              break;
                            default:
                                System.out.println("invalid data");
                        }
                    }
                }
            }while(menusel != 1 && menusel !=2);
        }
    }

查找结点

    CBTType TreeFindNode(CBTType treeNode, String data)
    {
        CBTType ptr;
        if (treeNode==null)
        {
            return null;
        }
        else
        {
            if (treeNOde.data.equals(data))
            {
                return treeNode;
            }
            else
            {           //search left and right recursively
                if ((ptr=TreeFindNode(treeNode.left,data))!=null)
                {
                    return ptr;
                }
                else if ((ptr=TreeFindNode(treeNode.right,data))!=null)
                {
                    return ptr;
                }
                else 
                {
                    return null;
                }
            }
        }
        
    }

获取左子树

CBTType TreeLeftNode(CBTType treeNode)
    {
        if(treeNode!= null)
        {
            return treeNode.left;
        }
        else {
            return null;
        }
    }

判断空树

int TreeIsEmpty(CBTType treeNode)
    {
        if (treeNode!=null)
        {
            return 0
        }
        else
        {
            return 1;
        }
    }

计算二叉树的深度

int TreeDepth(CBTType treeNode)
    {
        int depleft,depright;
        if (treeNode==null)
        {
            return 0;
        }
        else
        {
            depleft=TreeDepth(treeNode.left); //recursively
            depright=TreeDepth(treeNode.right);
            if (depleft>depright)
            {
                return depleft+1;
            }else
            {
                return depright+1;
            }
        }
    }

清空二叉树

 void ClearTree(CBTType treeNode)
    {
        if (treeNode!=null)
        {
            ClearTree(treeNode.left);
            ClearTree(treeNode.right);
            treeNode=null;
        }
    }

按层遍历

void levelTree (CBTType treeNode)
    {
        CBTType p;
        CBTType[] q=new CBTType[MAXLEN];//define a sequential stack
        int head =0, tail=0;
        
        if(treeNode!=null)
        {
            tail=(tail+1)%MAXLEN;
            q[tail]=treeNode;
        }
        while(head!=tail)
        {
            head=(head+1)%MAXLINE;
            p=q[head];
            TreeNodeData(p);
            if(p.left!=null)
            {
                tail=(tail+1)%MAXLEN;
                q[tail]=p.left;
            }
            if(p.right!=null)
            {
                tail=(tail+1)%MAXLEN;
                q[tail]=p.right;
            }
        }
    }

前序遍历（DLR）

void DLRTree(CBTType treeNode)
    {
        if(treeNode!=null) //treeNode is the root
        {
            TreeNodeData(treeNode);
            DLRTree(treeNode.left);
            DLRTree(treeNode.right);
        }
    }

中序遍历（LDR)

void LDRTree(CBTType treeNode)
    {
        if(treeNode!=null)
        {
            LDRTree(treeNode.left);
            TreeNodeData(treeNode);
            LDRTree(treeNode.right);
        }
    }

后序遍历（LRD)

void LRDTree(CBTType treeNode)
    {
        if (treeNode!=null)
        {
            LRDTree(treeNode.left);
            LRDTree(treeNode.right);
            TreeNodeData(treeNode);
        }
    }