【数据结构】——树和二叉树

目录

树 (Tree)

二叉树

二叉树的定义和性质

二叉树的存储结构

二叉树的运算

二叉树的遍历

树 (Tree)

树形结构：非线性数据结构，结点之间具有明确的层次关系，并且结点之间有分支，是一个递归结构。

定义：n(n≥0)个结点的有限集T。

任意一棵非空树：

• 有且仅有一个特定的称为根 (Root) 的结点
• 当n>1时，其余的结点可分为m(m>0)个互不相交的有限集T1,T2,...,T(m)，其中每个集合本身又是一棵树，称为根的子树

树的表示法：树形表示、嵌套集合表示、凹形表表示、广义表表示。

基本术语

对照上述的树 介绍各个基本术语 结点A的度为：3 结点B的度为：2 树的度为：3 叶子结点有：E J K G H I 分支结点有：A B C D F 根节点为：A B可作为子树的根，同时也是A的孩子 A是B的双亲，B C D之间互为兄弟 J的祖先有：A B F B的子孙有：E F J K 树的深度为：4

二叉树

二叉树的定义和性质

二叉树的定义和性质_South.return-CSDN博客

二叉树的存储结构

顺序存储结构

方法：从树根开始自上到下，每层从左至右地给该树中每个结点编号 (假定编号从0开始)，就能够得到一个反映整个二叉树结构的线性序列。然后以各节点的编号为下标，把每个结点的值对应存储到一个一维数组中。

图示：

链式存储结构

方法：每个结点设置三个域，即值域、左指针域和右指针域，用data表示值域，lchild和rchild分别表示指向左右子树 (孩子) 的指针域。

在一棵二叉树中，设有一个指向其根节点 (即开始结点) 的 BinTree型头指针bt及所有类型为 BinTNode的结点，就构成了二叉树的链式存储结构，称为二叉链表。

二叉树的运算

public class BinTNode {
    //定义数据
    Object data;
    //定义左指针
    BinTNode lchild;
    //定义右指针
    BinTNode rchild;

    //创建二叉树：按广义表表示二叉树结构生成二叉链表的算法
    public BinTNode CreateTree(char[] chars) {
        //定义数组
        BinTNode[] binTNodes = new BinTNode[100];
        //定义指针
        BinTNode p = null;
        //定义变量
        int top, k = -1, j = 0;
        //置空栈
        top = -1;
        //获取单个字符
        char ch = chars[j];
        //定义指针
        BinTNode b = null;

        //循环读广义表字符串中字符
        while (ch != '#') {
            switch (ch) {
                case '(':
                    //左子树
                    top++;
                    binTNodes[top] = p;
                    k = 1;
                    break;
                case ')':
                    //回退到上一层
                    top--;
                    break;
                case ',':
                    //右子树
                    k = 2;
                    break;
                default:
                    //添加元素值
                    p = new BinTNode();
                    p.data = ch;
                    p.lchild = p.rchild = null;
                    if (b == null) {
                        b = p;
                    } else {
                        switch (k) {
                            case 1:
                                binTNodes[top].lchild = p;
                                break;
                            case 2:
                                binTNodes[top].rchild = p;
                                break;
                            default:
                                break;
                        }
                    }
            }
            j++;
            ch = chars[j];
        }
        return b;
    }

    //前序遍历
    public static void Preorder(BinTNode binTNode) {
        if (binTNode != null) {
            System.out.print(binTNode.data + " ");
            Preorder(binTNode.lchild);
            Preorder(binTNode.rchild);
        }
    }

    //中序遍历
    public static void Inorder(BinTNode binTNode) {
        if (binTNode != null) {
            Inorder(binTNode.lchild);
            System.out.print(binTNode.data + " ");
            Inorder(binTNode.rchild);
        }
    }

    //后序遍历
    public static void Postorder(BinTNode binTNode) {
        if (binTNode != null) {
            Postorder(binTNode.lchild);
            Postorder(binTNode.rchild);
            System.out.print(binTNode.data + " ");
        }
    }
}

public class BinTNodeTest {
    public static void main(String[] args) {
        //定义广义表表示的树
        char[] chars = {'(', 'A', '(', 'B', '(', ',', 'D', '(', 'E', ',', 'F', ')', ')', ',', 'C', ')', ')', '#'};
        //创建对象
        BinTNode binTNode = new BinTNode();
        //创建二叉树的链式存储结构
        BinTNode binTNode1 = binTNode.CreateTree(chars);

        System.out.print("前序遍历：");
        Preorder(binTNode1);
        System.out.println();
        System.out.println();

        System.out.print("中序遍历：");
        Inorder(binTNode1);
        System.out.println();
        System.out.println();

        System.out.print("后序遍历：");
        Postorder(binTNode1);
        System.out.println();
    }
}

创建的树
运行结果

二叉树的遍历

概述：沿着某条搜索路径 (线)周游二叉树，依次对树中每个结点访问且仅访问一次。

三种递归遍历算法

总结

• 前序遍历：根左右
• 中序遍历：左根右
• 后序遍历：左右根

---