原文:
给定一个 n 元树，任务是以图形方式打印 n 元树。 树的图形表示法:一种树的表示法，其中根被打印在一行中，子节点被打印在具有一定缩进量的后续行中。 例:
input:
0
/ | \
/ | \
1 2 3
/ \ / | \
4 5 6 7 8
|
9
output:
0
--- 1
| --- 4
| --- 5
--- 2
--- 3
--- 6
--- 7
| --- 9
--- 8
方法:思想是使用 遍历 n 元树，遍历节点并探索其子节点，直到所有节点都被访问，然后类似地遍历兄弟节点。 上述方法的分步算法描述如下–
- 初始化一个变量来存储节点的当前深度，对于根节点，深度为 0。
- 声明一个布尔数组来存储当前的探测深度，并在开始时将它们全部标记为 false。
- 如果当前节点是根节点，即节点深度为 0，那么只需打印该节点的数据。
- 否则，迭代从 1 到当前节点深度的循环并打印，' | '和每个探测深度的三个空格，对于非探测深度仅打印三个空格。
- 打印节点的当前值，并将输出指针移动到下一行。
- 如果当前节点是该深度的最后一个节点，则将该深度标记为非探索。
- 同样，使用递归调用探索所有子节点。
以下是上述方法的实现:
c
// c implementation to print
// n-ary tree graphically
#include
#include
#include
using namespace std;
// structure of the node
struct tnode {
int n;
list root;
tnode(int data)
: n(data)
{
}
};
// function to print the
// n-ary tree graphically
void printntree(tnode* x,
vector flag,
int depth = 0, bool islast = false)
{
// condition when node is none
if (x == null)
return;
// loop to print the depths of the
// current node
for (int i = 1; i < depth; i) {
// condition when the depth
// is exploring
if (flag[i] == true) {
cout << "| "
<< " "
<< " "
<< " ";
}
// otherwise print
// the blank spaces
else {
cout << " "
<< " "
<< " "
<< " ";
}
}
// condition when the current
// node is the root node
if (depth == 0)
cout << x->n << '\n';
// condition when the node is
// the last node of
// the exploring depth
else if (islast) {
cout << " --- " << x->n << '\n';
// no more childrens turn it
// to the non-exploring depth
flag[depth] = false;
}
else {
cout << " --- " << x->n << '\n';
}
int it = 0;
for (auto i = x->root.begin();
i != x->root.end(); i, it)
// recursive call for the
// children nodes
printntree(*i, flag, depth 1,
it == (x->root.size()) - 1);
flag[depth] = true;
}
// function to form the tree and
// print it graphically
void formandprinttree(){
int nv = 10;
tnode r(0), n1(1), n2(2),
n3(3), n4(4), n5(5),
n6(6), n7(7), n8(8), n9(9);
// array to keep track
// of exploring depths
vector flag(nv, true);
// tree formation
r.root.push_back(&n1);
n1.root.push_back(&n4);
n1.root.push_back(&n5);
r.root.push_back(&n2);
r.root.push_back(&n3);
n3.root.push_back(&n6);
n3.root.push_back(&n7);
n7.root.push_back(&n9);
n3.root.push_back(&n8);
printntree(&r, flag);
}
// driver code
int main(int argc, char const* argv[])
{
// function call
formandprinttree();
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation to print
// n-ary tree graphically
import java.util.*;
class gfg{
// structure of the node
static class tnode {
int n;
vector root = new vector<>();
tnode(int data)
{
this.n = data;
}
};
// function to print the
// n-ary tree graphically
static void printntree(tnode x,
boolean[] flag,
int depth, boolean islast )
{
// condition when node is none
if (x == null)
return;
// loop to print the depths of the
// current node
for (int i = 1; i < depth; i) {
// condition when the depth
// is exploring
if (flag[i] == true) {
system.out.print("| "
" "
" "
" ");
}
// otherwise print
// the blank spaces
else {
system.out.print(" "
" "
" "
" ");
}
}
// condition when the current
// node is the root node
if (depth == 0)
system.out.println(x.n);
// condition when the node is
// the last node of
// the exploring depth
else if (islast) {
system.out.print(" --- " x.n '\n');
// no more childrens turn it
// to the non-exploring depth
flag[depth] = false;
}
else {
system.out.print(" --- " x.n '\n');
}
int it = 0;
for (tnode i : x.root) {
it;
// recursive call for the
// children nodes
printntree(i, flag, depth 1,
it == (x.root.size()) - 1);
}
flag[depth] = true;
}
// function to form the tree and
// print it graphically
static void formandprinttree(){
int nv = 10;
tnode r = new tnode(0);
tnode n1 = new tnode(1);
tnode n2 = new tnode(2);
tnode n3 = new tnode(3);
tnode n4 = new tnode(4);
tnode n5 = new tnode(5);
tnode n6 = new tnode(6);
tnode n7 = new tnode(7);
tnode n8 = new tnode(8);
tnode n9 = new tnode(9);
// array to keep track
// of exploring depths
boolean[] flag = new boolean[nv];
arrays.fill(flag, true);
// tree formation
r.root.add(n1);
n1.root.add(n4);
n1.root.add(n5);
r.root.add(n2);
r.root.add(n3);
n3.root.add(n6);
n3.root.add(n7);
n7.root.add(n9);
n3.root.add(n8);
printntree(r, flag, 0, false);
}
// driver code
public static void main(string[] args)
{
// function call
formandprinttree();
}
}
// this code is contributed by gauravrajput1
python 3
# python3 implementation to print n-ary tree graphically
# structure of the node
class tnode:
def __init__(self, data):
self.n = data
self.root = []
# function to print the
# n-ary tree graphically
def printntree(x,flag,depth,islast):
# condition when node is none
if x == none:
return
# loop to print the depths of the
# current node
for i in range(1, depth):
# condition when the depth
# is exploring
if flag[i]:
print("| ","", "", "", end = "")
# otherwise print
# the blank spaces
else:
print(" ", "", "", "", end = "")
# condition when the current
# node is the root node
if depth == 0:
print(x.n)
# condition when the node is
# the last node of
# the exploring depth
elif islast:
print(" ---", x.n)
# no more childrens turn it
# to the non-exploring depth
flag[depth] = false
else:
print(" ---", x.n)
it = 0
for i in x.root:
it =1
# recursive call for the
# children nodes
printntree(i, flag, depth 1, it == (len(x.root) - 1))
flag[depth] = true
# function to form the tree and
# print it graphically
def formandprinttree():
nv = 10
r = tnode(0)
n1 = tnode(1)
n2 = tnode(2)
n3 = tnode(3)
n4 = tnode(4)
n5 = tnode(5)
n6 = tnode(6)
n7 = tnode(7)
n8 = tnode(8)
n9 = tnode(9)
# array to keep track
# of exploring depths
flag = [true]*(nv)
# tree formation
r.root.append(n1)
n1.root.append(n4)
n1.root.append(n5)
r.root.append(n2)
r.root.append(n3)
n3.root.append(n6)
n3.root.append(n7)
n7.root.append(n9)
n3.root.append(n8)
printntree(r, flag, 0, false)
formandprinttree();
# this code is contributed by suresh07.
c
// c# implementation to print
// n-ary tree graphically
using system;
using system.collections.generic;
class gfg
{
// structure of the node
public class tnode
{
public
int n;
public
list root = new list();
public
tnode(int data)
{
this.n = data;
}
};
// function to print the
// n-ary tree graphically
static void printntree(tnode x,
bool[] flag,
int depth, bool islast )
{
// condition when node is none
if (x == null)
return;
// loop to print the depths of the
// current node
for (int i = 1; i < depth; i)
{
// condition when the depth
// is exploring
if (flag[i] == true)
{
console.write("| "
" "
" "
" ");
}
// otherwise print
// the blank spaces
else
{
console.write(" "
" "
" "
" ");
}
}
// condition when the current
// node is the root node
if (depth == 0)
console.writeline(x.n);
// condition when the node is
// the last node of
// the exploring depth
else if (islast)
{
console.write(" --- " x.n '\n');
// no more childrens turn it
// to the non-exploring depth
flag[depth] = false;
}
else
{
console.write(" --- " x.n '\n');
}
int it = 0;
foreach (tnode i in x.root)
{
it;
// recursive call for the
// children nodes
printntree(i, flag, depth 1,
it == (x.root.count) - 1);
}
flag[depth] = true;
}
// function to form the tree and
// print it graphically
static void formandprinttree()
{
int nv = 10;
tnode r = new tnode(0);
tnode n1 = new tnode(1);
tnode n2 = new tnode(2);
tnode n3 = new tnode(3);
tnode n4 = new tnode(4);
tnode n5 = new tnode(5);
tnode n6 = new tnode(6);
tnode n7 = new tnode(7);
tnode n8 = new tnode(8);
tnode n9 = new tnode(9);
// array to keep track
// of exploring depths
bool[] flag = new bool[nv];
for(int i = 0; i < nv; i )
flag[i] = true;
// tree formation
r.root.add(n1);
n1.root.add(n4);
n1.root.add(n5);
r.root.add(n2);
r.root.add(n3);
n3.root.add(n6);
n3.root.add(n7);
n7.root.add(n9);
n3.root.add(n8);
printntree(r, flag, 0, false);
}
// driver code
public static void main(string[] args)
{
// function call
formandprinttree();
}
}
// this code is contributed by aashish1995
java 描述语言
output
0
--- 1
| --- 4
| --- 5
--- 2
--- 3
--- 6
--- 7
| --- 9
--- 8
业绩分析:
- 时间复杂度:在上面给出的方法中，有一个递归调用来探索所有花费 o(v)时间的顶点。因此，这种方法的时间复杂度将是 o(v) 。
- 辅助空间复杂度:在上面给出的方法中，有额外的空间用于存储探索深度。因此，上述方法的辅助空间复杂度为 o(v)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
