常用的数据结构（二叉树）

二叉树：就是弄一个对象，对象里边最少放着三个数据，分别是左子树，右子树和被存储的数据，然后左子树和右子树又是该对象类型，所以每一个左子树和右子树下面又是左子树，右子树和数据，这样就形成了一个倒着的树，不断的扩大，里边用的比较多就是递归。

1.java实现

package com.sjx.test1;

import java.util.Scanner;
class CBTType
{
    String data;
    CBTType left;
    CBTType right;
}


public class BinaryTree {
    static int MAXLEN=20;
    static Scanner input=new Scanner(System.in);
    CBTType InitTree()
    {
        CBTType node;
        if((node=new CBTType())!=null)
        {
            System.out.printf("请先输入一个根结点数据:
");
            node.data=input.next();
            node.left=null;
            node.right=null;
            if(node!=null)
            {
                return node;
            }
            else
            {
                return null;
            }
        }
        return null;
    }
    
    CBTType TreeFindNode(CBTType treeNode, String data)
    {
        CBTType ptr;
        if(treeNode==null)
        {
            return null;
        }
        else
        {
            if(treeNode.data.equals(data))
            {
                return treeNode;
            }
            else
            {
                if((ptr=TreeFindNode(treeNode.left, data))!=null)
                {
                    return ptr;
                }
                else if((ptr=TreeFindNode(treeNode.right, data))!=null)
                {
                    return ptr;
                }
                else
                {
                    return null;
                }
            }
        }
    }
    
    void AddTreeNode(CBTType treeNode)
    {
        CBTType pnode, parent;
        String data;
        int menusel;
        
        if((pnode=new CBTType())!=null)
        {
            System.out.print("输入二叉树结点数据：
");
            
            pnode.data=input.next();
            pnode.left=null;
            pnode.right=null;
            
            System.out.print("输入该节点的父节点数据：");
            data=input.next();
            
            parent=TreeFindNode(treeNode, data);    //查找指定数据的结点
            if(parent==null)
            {
                System.out.printf("未找到该父结点！
");
                pnode=null;
                return;
            }
            do
            {
                menusel=input.nextInt();
                if(menusel==1||menusel==2)
                {
                    if(parent==null)
                    {
                        System.out.printf("不存在父结点，请先设置父结点！
");
                    }
                    
                else
                {
                    switch(menusel)
                    {
                    case 1:
                        if(parent.left!=null)
                        {
                            System.out.printf("左子树结点不为空！
");
                        }
                        else
                        {
                            parent.left=pnode;
                        }
                        break;
                    case 2:
                        if(parent.right!=null)
                        {
                            System.out.printf("右子树结点不为空！
");
                        }
                        else
                        {
                            parent.right=pnode;
                        }
                        break;
                    default:
                            System.out.printf("无效参数！
");
                    }
                }
            }
        }while(menusel!=1&&menusel!=2);
    }
}
    
    CBTType TreeLeftNode(CBTType treeNode)
    {
        if(treeNode!=null)
        {
            return treeNode.left;
        }
        else
        {
            return null;
        }
    }
    
    CBTType TreeRightNode(CBTType treeNode)
    {
        if(treeNode!=null)
        {
            return treeNode.right;
        }
        else
        {
            return null;
        }
    }
    
    
    int TreeEmpty(CBTType treeNode)
    {
        if(treeNode!=null)
        {
            return 0;
        }
        else
        {
            return 1;
        }
    }
    
    int TreeDepth(CBTType treeNode)
    {
        int depleft, depright;
        if(treeNode==null)
        {
            return 0; //空数，深度为0
        }
        else
        {
            depleft=TreeDepth(treeNode.left);
            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 TreeNodeData(CBTType p)
    {
        System.out.printf("%s", p.data);
    }
    
    void LevelTree(CBTType treeNode)
    {
        CBTType p;
        CBTType[] q=new CBTType[MAXLEN];
        int head=0, tail=0;
        
        if(treeNode!=null)
        {
            tail=(tail+1)%MAXLEN;
            q[tail]=treeNode;
        }
        while(head!=tail)
        {
            head=(head+1)%MAXLEN;
            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;
            }
        }
    }
    
    void DLRTree(CBTType treeNode)    //先序遍历
    {
        if(treeNode!=null)
        {
            TreeNodeData(treeNode);
            DLRTree(treeNode.left);
            DLRTree(treeNode.right);
        }
    }
    
    void LDRTree(CBTType treeNode)    //中序遍历
    {
        if(treeNode!=null)
        {
            LDRTree(treeNode.left);
            TreeNodeData(treeNode);
            LDRTree(treeNode.right);
        }
    }
    
    void LRDTree(CBTType treeNode)    //后序遍历
    {
        if(treeNode!=null)
        {
            LRDTree(treeNode.left);
            LRDTree(treeNode.right);
            TreeNodeData(treeNode);
        }
    }
    
    public static void main(String[] args)
    {
        CBTType root=null;
        int menusel;
        BinaryTree t=new BinaryTree();
        root=t.InitTree();
        
        do
        {
            System.out.printf("请选择菜单添加二叉树的结点
");
            System.out.printf("0.推出	");
            System.out.printf("1.添加二叉树的结点
");
            menusel=input.nextInt();
            switch(menusel)
            {
            case 1:
                t.AddTreeNode(root);
                break;
            case 0:
                break;
            default:
                    ;
            }
        }while(menusel!=0);
    do
    {
        System.out.printf("请选择菜单遍历二叉树，输入0便是退出:
");
        System.out.printf("1.先序遍历DLR	"); //显示菜单
        System.out.printf("2.中序遍历LDR
");
        System.out.printf("3.后序遍历LRD	");
        System.out.printf("4.按层遍历
");
        menusel=input.nextInt();
        switch(menusel)
        {
        case 0:
            break;
        case 1:
            System.out.printf("先序遍历DLR的结果: ");
            t.DLRTree(root);
            System.out.printf("
");
            break;
        case 2:
            System.out.printf("中序遍历LDR的结果: ");
            t.DLRTree(root);
            System.out.printf("
");
            break;
        case 3:
            System.out.printf("后序遍历LRD的结果: ");
            t.DLRTree(root);
            System.out.printf("
");
            break;
        case 4:
            System.out.printf("按层遍历的结果: ");
            t.DLRTree(root);
            System.out.printf("
");
            break;
        default:
                ;
        }
    }while(menusel!=0);
    System.out.printf("
二叉树深度是: %d
", t.TreeDepth(root));
    
    t.ClearTree(root);    //清空二叉树
    root=null;
    }
}