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

数据结构和算法——树结构

news 2025/6/25 16:27:19

二叉树

又叫二叉排序树。

节点是数量为， $2^{n}-1$ ，n为层数。

满二叉树：所有的叶子节点都在最后一层。

完全二叉树：如果所有叶子节点都在最后一层和倒数第二层，而且每个叶子节点都有左右子节点。

前序遍历

1、先输出当前节点（初始是root节点）。

2、如果左子节点不为空，则递归继续前序遍历。

3、如果右子节点不为空，则递归继续前序遍历。

class HeroNode {private int no;private String name;private HeroNode left, right;
}

    public HeroNode preOrderSearch(int no) {if (this.no == no) {return this;}HeroNode resNode;if (this.left != null) {resNode = this.left.preOrderSearch(no);if (resNode != null) {return resNode;}}if (this.right != null) {resNode = this.right.preOrderSearch(no);if (resNode != null) {return resNode;}}return null;}

中序遍历

1、如果当前节点的左子节点不为空，则递归中序遍历。

2、输出当前节点。

3、如果当前节点的右子节点不为空，则递归中序遍历。

    public HeroNode infixOrderSearch(int no) {HeroNode resNode;if (this.left != null) {resNode = this.left.infixOrderSearch(no);if (resNode != null) {return resNode;}}if (this.no == no) {return this;}if (this.right != null) {resNode = this.right.infixOrderSearch(no);if (resNode != null) {return resNode;}}return null;}

后序遍历

1、如果当前节点的左子节点不为空，则递归后序遍历。

2、如果当前节点的右子节点不为空，则递归后序遍历。

3、输出当前节点。

    public HeroNode postOrderSearch(int no) {HeroNode resNode;if (this.left != null) {resNode = this.left.postOrderSearch(no);if (resNode != null) {return resNode;}}if (this.right != null) {resNode = this.right.postOrderSearch(no);if (resNode != null) {return resNode;}}if (this.no == no) {return this;}return null;}

二叉树节点的删除，如果是中间节点，则整个中间节点都删除。

    public void delNode(int no) {if (this.no == no) {return;}if (this.left != null) {if (this.left.no == no) {this.left = null;} else {this.left.delNode(no);}}if (this.right != null) {if (this.right.no == no) {this.right = null;} else {this.right.delNode(no);}}}

顺序存储二叉树

顺序二叉树通常是完全二叉树。

第n(n是下标)个元素的左子节点为 2 * n + 1

第n个元素的右子节点为 2 * n + 2

第n个元素的父节点为 (n - 1) / 2

堆排序用到顺序存储二叉树的结构。

线索化二叉树

充分的利用到了叶子节点的空指针。

class HeroNode {private int no;private String name;private HeroNode left, right;private int leftType; // 0 指向的是左子树 1指向前驱节点private int rightType; // 0 指向的是右子树 1指向后继节点
}

对线索二叉树进行中序线索化的方法

    public void threadedNodes(HeroNode node) {if (node == null) {return;}threadedNodes(node.getLeft()); // 先线索化左子树// 再线索化当前节点if (node.getLeft() == null) { // 前驱node.setLeft(pre);node.setLeftType(1);}if (pre != null && pre.getRight() == null) { // 后继pre.setRight(node);pre.setRightType(1);}pre = node;threadedNodes(node.getRight()); // 最后线索化右子树}

线索化二叉树的中序遍历

 class ThreadedBinaryTree {private HeroNode root;private HeroNode pre = null; // 指向前驱节点public void threadedList() {HeroNode node = root;while (node != null) {while (node.getLeftType() == 0) { // 到左下角node = node.getLeft();}System.out.println(node);while (node.getRightType() == 1) {node = node.getRight();System.out.println(node);}node = node.getRight();}}
}