本文主要是介绍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）的基本数据结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
