C/C++，树算法——二叉树（BTree）的基本数据结构

本文主要是介绍C/C++，树算法——二叉树（BTree）的基本数据结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 文本格式

using System;

// A BTree
class Btree
{
    public BTreeNode root; // Pointer to root node
    public int t; // Minimum degree

    // Constructor (Initializes tree as empty)
    Btree(int t)
    {
        this.root = null;
        this.t = t;
    }

    // function to traverse the tree
    public void traverse()
    {
        if (this.root != null)
            this.root.traverse();
        Console.WriteLine();
    }

    // function to search a key in this tree
    public BTreeNode search(int k)
    {
        if (this.root == null)
            return null;
        else
            return this.root.search(k);
    }
}

// A BTree node
class BTreeNode
{
    int[] keys; // An array of keys
    int t; // Minimum degree (defines the range for number of keys)
    BTreeNode[] C; // An array of child pointers
    int n; // Current number of keys
    bool leaf; // Is true when node is leaf. Otherwise false

    // Constructor
    BTreeNode(int t, bool leaf) {
        this.t = t;
        this.leaf = leaf;
        this.keys = new int[2 * t - 1];
        this.C = new BTreeNode[2 * t];
        this.n = 0;
    }

    // A function to traverse all nodes in a subtree rooted with this node
    public void traverse() {

        // There are n keys and n+1 children, traverse through n keys
        // and first n children
        int i = 0;
        for (i = 0; i < this.n; i++) {

            // If this is not leaf, then before printing key[i],
            // traverse the subtree rooted with child C[i].
            if (this.leaf == false) {
                C[i].traverse();
            }
            Console.Write(keys[i] + " ");
        }

        // Print the subtree rooted with last child
        if (leaf == false)
            C[i].traverse();
    }

    // A function to search a key in the subtree rooted with this node.
    public BTreeNode search(int k) { // returns NULL if k is not present.

        // Find the first key greater than or equal to k
        int i = 0;
        while (i < n && k > keys[i])
            i++;

        // If the found key is equal to k, return this node
        if (keys[i] == k)
            return this;

        // If the key is not found here and this is a leaf node
        if (leaf == true)
            return null;

        // Go to the appropriate child
        return C[i].search(k);

    }
}
 

2 代码格式

using System;// A BTree
class Btree
{public BTreeNode root; // Pointer to root nodepublic int t; // Minimum degree// Constructor (Initializes tree as empty)Btree(int t){this.root = null;this.t = t;}// function to traverse the treepublic void traverse(){if (this.root != null)this.root.traverse();Console.WriteLine();}// function to search a key in this treepublic BTreeNode search(int k){if (this.root == null)return null;elsereturn this.root.search(k);}
}// A BTree node
class BTreeNode
{int[] keys; // An array of keysint t; // Minimum degree (defines the range for number of keys)BTreeNode[] C; // An array of child pointersint n; // Current number of keysbool leaf; // Is true when node is leaf. Otherwise false// ConstructorBTreeNode(int t, bool leaf) {this.t = t;this.leaf = leaf;this.keys = new int[2 * t - 1];this.C = new BTreeNode[2 * t];this.n = 0;}// A function to traverse all nodes in a subtree rooted with this nodepublic void traverse() {// There are n keys and n+1 children, traverse through n keys// and first n childrenint i = 0;for (i = 0; i < this.n; i++) {// If this is not leaf, then before printing key[i],// traverse the subtree rooted with child C[i].if (this.leaf == false) {C[i].traverse();}Console.Write(keys[i] + " ");}// Print the subtree rooted with last childif (leaf == false)C[i].traverse();}// A function to search a key in the subtree rooted with this node.public BTreeNode search(int k) { // returns NULL if k is not present.// Find the first key greater than or equal to kint i = 0;while (i < n && k > keys[i])i++;// If the found key is equal to k, return this nodeif (keys[i] == k)return this;// If the key is not found here and this is a leaf nodeif (leaf == true)return null;// Go to the appropriate childreturn C[i].search(k);}
}

这篇关于C/C++，树算法——二叉树（BTree）的基本数据结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---