# java自定义构造二叉树及其遍历

String expression = "A(B(D(,G)),C(E,F))";与该广义表对应的二叉树为

1366533767_1515.jpg

```每当遇到字母，将要创建节点

### 节点类的构建###

```public class Node {

private char data;
private Node lchild;
private Node rchild;

public Node(){

}
public char getData() {
return data;
}

public void setData(char data) {
this.data = data;
}

public Node getRchild() {
return rchild;
}

public void setRchild(Node rchild) {
this.rchild = rchild;
}

public Node getLchild() {
return lchild;
}

public void setLchild(Node lchild) {
this.lchild = lchild;
}

public Node(char ch, Node rchild, Node lchild) {
this.data = ch;
this.rchild = rchild;
this.lchild = lchild;
}

public String toString() {
return "" + getData();
}
}  ```

### 创建二叉树###

```public Node createTree(String exp) {
Node[] nodes = new Node[3];
Node b, p = null;
int top = -1, k = 0, j = 0;
char[] exps = exp.toCharArray();
char data = exps[j];
b = null;
while (j < exps.length - 1) {
switch (data) {
case '(':
top++;
nodes[top] = p;
k = 1;
break;
case ')':
top--;
break;
case ',':
k = 2;
break;
default:
p = new Node(data, null, null);
if (b == null) {
b = p;
} else {
switch (k) {
case 1:
nodes[top].setLchild(p);
break;
case 2:
nodes[top].setRchild(p);
break;
}
}
}
j++;
data = exps[j];
}
return b;
}  ```

### 递归执行三种遍历###

```    /**
* pre order recursive
*
* @param node
*/
public void PreOrder(Node node) {
if (node == null) {
return;
} else {
System.out.print(node.getData() + " ");
PreOrder(node.getLchild());
PreOrder(node.getRchild());

}
}

/**
* in order recursive
*
* @param node
*/
public void InOrder(Node node) {
if (node == null) {
return;
} else {
InOrder(node.getLchild());
System.out.print(node.getData() + " ");
InOrder(node.getRchild());
}
}

/**
* post order recursive
*
* @param node
*/
public void PostOrder(Node node) {
if (node == null) {
return;
} else {
PostOrder(node.getLchild());
PostOrder(node.getRchild());
System.out.print(node.getData() + " ");
}
}  ```

### 非递归遍历###

```前序遍历
public void PreOrderNoRecursive(Node node) {
Node nodes[] = new Node[CAPACITY];
Node p = null;
int top = -1;
if (node != null) {
top++;
nodes[top] = node;
while (top > -1) {
p = nodes[top];
top--;
System.out.print(p.getData() + " ");
if (p.getRchild() != null) {
top++;
nodes[top] = p.getRchild();
}
if (p.getLchild() != null) {
top++;
nodes[top] = p.getLchild();
}
}
}
}

public void InOrderNoRecursive(Node node) {
Node nodes[] = new Node[CAPACITY];
Node p = null;
int top = -1;
if (node != null)
p = node;
while (p != null || top > -1) {
while (p != null) {
top++;
nodes[top] = p;
p = p.getLchild();
}
if (top > -1) {
p = nodes[top];
top--;
System.out.print(p.getData() + " ");
p = p.getRchild();
}
}
}

public void PostOrderNoRecursive(Node node) {
Node[] nodes = new Node[CAPACITY];
Node p = null;
int flag = 0, top = -1;
if (node != null) {
do {
while (node != null) {
top++;
nodes[top] = node;
node = node.getLchild();
}
p = null;
flag = 1;
while (top != -1 && flag != 0) {
node = nodes[top];
if (node.getRchild() == p) {
System.out.print(node.getData() + " ");
top--;
p = node;
} else {
node = node.getRchild();
flag = 0;
}
}
} while (top != -1);
}
}  ```

67 篇文章28 人订阅

0 条评论

## 相关文章

14850

359140

38070

### Leetcode 91 Decode Ways

A message containing letters from A-Z is being encoded to numbers using the fol...

22270

### PHP数据结构（一）——顺序结构线性表

PHP数据结构（一）——顺序结构线性表 （原创内容，转载请注明来源，谢谢） 线性表的要求：存在唯一的“第一个”元素与“最后一个”元素，每个元素最多一个前驱和一个...

58090

12110

14460

8220

3.1K30

1.1K00