当前位置：首页 > news >正文

树状打印二叉树的类Java、Go、PHP

news 来源：原创 2024/5/11 4:19:10

说明和效果

   树的结构示例：1/   \2       3/ \     / \4   5   6   7

树状打印二叉树Java代码

  static class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}//打印二叉树的类// TreeOperation.javastatic class TreeNodeShow {/*树的结构示例：1/   \2       3/ \     / \4   5   6   7*/// 用于获得树的层数public static int getTreeDepth(TreeNode root) {return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));}private static void writeArray(TreeNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {// 保证输入的树不为空if (currNode == null) return;// 先将当前节点保存到二维数组中res[rowIndex][columnIndex] = String.valueOf(currNode.val);// 计算当前位于树的第几层int currLevel = ((rowIndex + 1) / 2);// 若到了最后一层，则返回if (currLevel == treeDepth) return;// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）int gap = treeDepth - currLevel - 1;// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值if (currNode.left != null) {res[rowIndex + 1][columnIndex - gap] = "/";writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);}// 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值if (currNode.right != null) {res[rowIndex + 1][columnIndex + gap] = "\\";writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);}}public static void show(TreeNode root) {if (root == null) System.out.println("EMPTY!");// 得到树的深度int treeDepth = getTreeDepth(root);// 最后一行的宽度为2的（n - 1）次方乘3，再加1// 作为整个二维数组的宽度int arrayHeight = treeDepth * 2 - 1;int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;// 用一个字符串数组来存储每个位置应显示的元素String[][] res = new String[arrayHeight][arrayWidth];// 对数组进行初始化，默认为一个空格for (int i = 0; i < arrayHeight; i++) {for (int j = 0; j < arrayWidth; j++) {res[i][j] = " ";}}// 从根节点开始，递归处理整个树// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');writeArray(root, 0, arrayWidth / 2, res, treeDepth);// 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可for (String[] line : res) {StringBuilder sb = new StringBuilder();for (int i = 0; i < line.length; i++) {sb.append(line[i]);if (line[i].length() > 1 && i <= line.length - 1) {i += line[i].length() > 4 ? 2 : line[i].length() - 1;}}System.out.println(sb.toString());}}
}

使用例子：
TreeNodeShow.show(new TreeNode(1));

树状打印二叉树Go代码

type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}//打印二叉树的类
// TreeOperation.javatype TreeNodeShow struct {
}func (ts TreeNodeShow) getTreeDepth(root *TreeNode) int {if root == nil {return 0}L := ts.getTreeDepth(root.Left)R := ts.getTreeDepth(root.Right)ans := Lif ans < R {ans = R}return ans + 1
}func (ts TreeNodeShow) writeArray(currNode *TreeNode, rowIndex int, columnIndex int,res [][]string, treeDepth int) {// 保证输入的树不为空if currNode == nil {return}// 先将当前节点保存到二维数组中res[rowIndex][columnIndex] = strconv.Itoa(currNode.Val)// 计算当前位于树的第几层currLevel := ((rowIndex + 1) / 2)// 若到了最后一层，则返回if currLevel == treeDepth {return}// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）gap := treeDepth - currLevel - 1// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值if currNode.Left != nil {res[rowIndex+1][columnIndex-gap] = "/"ts.writeArray(currNode.Left, rowIndex+2, columnIndex-gap*2, res, treeDepth)}// 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值if currNode.Right != nil {res[rowIndex+1][columnIndex+gap] = "\\"ts.writeArray(currNode.Right, rowIndex+2, columnIndex+gap*2, res, treeDepth)}
}func (ts TreeNodeShow) show(root *TreeNode) {if root == nil {fmt.Println("EMPTY!")}// 得到树的深度treeDepth := ts.getTreeDepth(root)// 最后一行的宽度为2的（n - 1）次方乘3，再加1// 作为整个二维数组的宽度arrayHeight := treeDepth*2 - 1arrayWidth := (2<<(treeDepth-2))*3 + 1// 用一个字符串数组来存储每个位置应显示的元素res := make([][]string, arrayHeight)for x := 0; x < arrayHeight; x++ {res[x] = make([]string, arrayWidth)}// 对数组进行初始化，默认为一个空格for i := 0; i < arrayHeight; i++ {for j := 0; j < arrayWidth; j++ {res[i][j] = " "}}// 从根节点开始，递归处理整个树// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');ts.writeArray(root, 0, arrayWidth/2, res, treeDepth)// 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可//for (String[] line : res) {for _, line := range res {sb := ""for i := 0; i < len(line); i++ {sb = sb + line[i]if len(line[i]) > 1 && i <= len(line)-1 {//i += line[i].length() > 4 ? 2 : line[i].length() - 1;if len(line[i]) > 4 {i = i + 2} else {i = len(line[i]) - 1}//i =i+ len(line[i]) > 4 ? 2 : len(line[i]) - 1;}}fmt.Println(sb)}}

使用：

TreeNodeShow.show(new TreeNode(1));

使用

node1 := TreeNode{1, nil, nil}
node1.Left = &TreeNode{2, nil, nil}
node1.Left.Left = &TreeNode{3, nil, nil}node1.Right = &TreeNode{5, nil, nil}
node1.Right.Left = &TreeNode{4, nil, nil}
node1.Right.Right = &TreeNode{6, nil, nil}
ts := TreeNodeShow{}
ts.show(&node1)

树状打印二叉树PHP代码

   class TreeNode{var $val;var $left = NULL;var $right = NULL;function __construct($val){$this->val = $val;}
}//PHP打印二叉树的类
// TreeOperation.java
class TreeNodeShow {/*树的结构示例：1/   \2       3/ \     / \4   5   6   7*/// 用于获得树的层数public static function getTreeDepth($root) {if($root ==null) return 0;$deepLeft = self::getTreeDepth($root->left);$deepRight = self::getTreeDepth($root->right);$max = $deepLeft;if($max < $deepRight){$max = $deepRight;}return  1 + $max;}private static function writeArray($currNode, $rowIndex, $columnIndex, &$res, $treeDepth) {// 保证输入的树不为空if ($currNode == null) return;// 先将当前节点保存到二维数组中$res[$rowIndex][$columnIndex] = $currNode->val;// 计算当前位于树的第几层$currLevel = intval(($rowIndex + 1) / 2);// 若到了最后一层，则返回if ($currLevel == $treeDepth) return;// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）$gap = $treeDepth - $currLevel - 1;// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值if ($currNode ->left != null) {$res[$rowIndex + 1][$columnIndex - $gap] = "/";self::  writeArray($currNode -> left, $rowIndex + 2, $columnIndex - $gap * 2, $res, $treeDepth);}// 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值if ($currNode -> right != null) {$res[$rowIndex + 1][$columnIndex + $gap] = "\\";self::writeArray($currNode->right, $rowIndex + 2, $columnIndex + $gap * 2, $res, $treeDepth);}}public static function show($root) {if ($root == null) echo "EMPTY!".PHP_EOL;// 得到树的深度$treeDepth = self:: getTreeDepth($root);// 最后一行的宽度为2的（n - 1）次方乘3，再加1// 作为整个二维数组的宽度$arrayHeight = $treeDepth * 2 - 1;$arrayWidth = (2 << ($treeDepth - 2)) * 3 + 1;// 用一个字符串数组来存储每个位置应显示的元素$res = array();// 对数组进行初始化，默认为一个空格for ($i = 0; $i < $arrayHeight; $i++) {for ($j = 0; $j < $arrayWidth; $j++) {$res[$i][$j] = " ";}}// 从根节点开始，递归处理整个树// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');self:: writeArray($root, 0, intval($arrayWidth / 2), $res, $treeDepth);// 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可/**  for (String[] line : res) {StringBuilder sb = new StringBuilder();for (int i = 0; i < line.length; i++) {sb.append(line[i]);if (line[i].length() > 1 && i <= line.length - 1) {i += line[i].length() > 4 ? 2 : line[i].length() - 1;}}System.out.println(sb.toString());}*/for ($x=0;$x<count($res);$x++ ) {$sb = '';$line = $res[$x];if(gettype($line) =='NULL') continue;if(gettype($line) ==NULL) continue;//var_dump('长度：'.count($line).'  类型：'.(gettype($line)));for ($i = 0; $i < count($line); $i++) {$sb.=$line[$i];if (strlen($line[$i]) > 1 && $i <= count($line) - 1) {$i .= strlen($line[$i]) > 4 ? 2 : strlen($line[$i]) - 1;}}echo $sb.PHP_EOL;}}}使用：
$node1 = new TreeNode(1);
$node1->left = new TreeNode(2);
$node1->left->left = new TreeNode(3);
$node1->right = new TreeNode(5);
$node1->right->left= new TreeNode(4);
$node1->right->right= new TreeNode(6);TreeNodeShow::show($node1);