数据结构与算法之美-二叉树基础(上）

树

节点的定义

树中的元素称之为节点

高度的定义

节点的高度：节点到叶子节点的最长路径

树的高度：跟节点的高度

深度的定义

根节点到这个节点所经历的边的个数

层的定义

节点的深度+1

 

二叉树

满二叉树

除了叶子结点外每个节点都有左右两个子节点

完全二叉树

叶子结点都在最低下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大

表示、存储一颗二叉树

链式存储法

每个结点有三个字段，其中一个存储数据，另两个是指向左右子节点的指针。

顺序存储法(基于数组)

根节点存储在下标i=1的位置，左子节点存储在下标2*i=2的位置，右子节点存储在2*i+1=3的位置，以此类推。

如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。

我们只要知道根节点存储的位置，这样就可以通过下标计算，把整棵树都串起来。

为了方便计算子节点，根节点会存储在下标为 1 的位置

二叉树的遍历

前序遍历

对于树中的任意节点来说，先打印这个节点，然

后再打印它的左子树，最后打印它的右子树。

中序遍历

对于树中的任意节点来说，先打印它的左子树，

然后再打印它本身，最后打印它的右子树。

后序遍历

对于树中的任意节点来说，先打印它的左子树，

然后再打印它的右子树，最后打印这个节点本身。

层序遍历

从树的第一层开始从左到右打印节点

 

实际上，二叉树的前、中、后序遍历就是一个递归的过程。

比如，前序遍历，其实就是先打印根节点，然后再递归地打印左子树，最后递归地打印右子树。

二叉树以及二叉树遍历代码实现

二叉树节点类

代码按照标准书写，完全可以简化为公有字段去掉属性和实例构造器。

internal sealed class Node{
    private int data;//数据
    private Node left;//左子节点指针
    private Node right;//右子节点指针
    //私有字段对应的公共属性
    public int Data{
        get { return data; }
        set { data = value; }
    }
    public Node Left{
        get { return left; }
        set { left = value; }
    }
    public Node Right{
        get { return right; }
        set { right = value; }
    }
    //无参、有参实例构造器
    public Node(){
        data = 0;
        left = null;
        right = null;
    }
    public Node(int data){
        this.data = data;
        left = null;
        right = null;
    }
}

二叉树类

internal sealed class BinaryTree{
    private Node root;//根节点
    public Node Root{
        get { return root; }
        set { root = value; }
    }
    //无参、有参实例构造器
    public BinaryTree(){
        root = null;
    }
    public BinaryTree(Node root){
        this.root = root;
    }
    //前序遍历
    public void PreOrder(Node root){
        if (root == null) return;
        Console.Write(root.Data+",");
        PreOrder(root.Left);
        PreOrder(root.Right);
    }
    //中序遍历
    public void InOrder(Node root){
        if (root == null) return;
        InOrder(root.Left);
        Console.Write(root.Data + ",");
        InOrder(root.Right);
    }
    //后序遍历
    public void PostOrder(Node root){
        if (root == null) return;
        PostOrder(root.Left);
        PostOrder(root.Right);
        Console.Write(root.Data + ",");
    }
    //层序遍历
    public void LevelOrder(Node root){
        Queue<Node> q = new Queue<Node>();
        Node p = root;
        q.Enqueue(p);
        while (q.Count != 0){
            Node node = q.Dequeue();
            Console.Write(node.Data+",");
            if (node.Left != null) q.Enqueue(node.Left);
            if (node.Right != null) q.Enqueue(node.Right);
        }
    }
}

测试用程序类

class Program{
    static void Main(string[] args){
        BinaryTree binary = new BinaryTree();//声明二叉树类实例
        //声明节点
        var a = new Node(1);
        var b = new Node(2);
        var c = new Node(3);
        var d = new Node(4);
        var e = new Node(5);
        var f = new Node(6);
        var g = new Node(7);
        //设置根节点和左右子节点
        binary.Root = a;
        a.Left = b;
        a.Right = c;
        b.Left = d;
        b.Right = e;
        c.Left = f;
        c.Right = g;
        //前序、中序、后序、层序遍历输出
        binary.PreOrder(a);
        Console.WriteLine();
        binary.InOrder(a);
        Console.WriteLine();
        binary.PostOrder(a);
        Console.WriteLine();
        binary.LevelOrder(a);
        Console.ReadKey();
    }
}

测试结果

1,2,4,5,3,6,7,
4,2,5,1,6,3,7,
4,5,2,6,7,3,1,
1,2,3,4,5,6,7,