23树存储结构
1. 二叉树的存储结构是怎样的有哪些类型的存储结构对应的c语言描述是
楼上回答的是树的存储，不是二叉树的存储，主要如下：
1、顺序存储：适用于完全二叉树，如果根从1开始编号，则第i结点的左孩子编号为2i，右孩子为2i+1，双亲编号为(i/2）下取整，空间紧密
2、二叉链表：适用于普通二叉树，每个结点除了数据外，还有分别指向左右孩子结点的指针，存储n个结点有n+1个空指针域，存储密度小于顺序存储，但是适用范围广，缺陷是正常遍历只能从双亲向孩子，退回来一般需要借助栈（或者用递归，其实也是栈）
3、三叉链表：同样适用于普通二叉树，结点除了数据外，还有左右孩子与双亲的指针，存储密度低于二叉链表，但是可以非常方便地在二叉树中遍历，不需要其他辅助工具
2. 急！二叉树的存储结构，并完成：建立、查找、计算结点数、求高度、三种遍历方式
public class BinaryTree<E> //二叉树类
{
protected BinaryNode<E> root; //根结点
public BinaryTree() //构造空二叉树
{
root=null;
}
public BinaryTree(BinaryNode<E> root) //构造指定根结点的二叉树
{
this.root=root;
}
public boolean isEmpty() //判断是否空二叉树
{
return this.root==null;
}
public BinaryNode<E> getRoot() //返回二叉树的根结点
{
return this.root;
}
//6.3.3 二叉树的遍历
public void preOrder() //先根次序遍历二叉树
{
System.out.print("\n先根序列： ");
preOrder(root);
}
private void preOrder(BinaryNode<E> p) //先根次序遍历以p结点为根的子二叉树
{
if(p!=null) //若二叉树不空
{
System.out.print(p.data+" "); //访问当前结点
preOrder(p.left); //按先根次序遍历当前结点的左子树
preOrder(p.right); //按先根次序遍历当前结点的右子树
}
}
public void inOrder() //中根次序遍历二叉树
{
System.out.print("\n中根序列： ");
inOrder(root);
}
private void inOrder(BinaryNode<E> p) //中根次序遍历以p结点为根的子二叉树
{
if (p!=null)
{
inOrder(p.left); //中根次序遍历左子树
System.out.print(p.data+" ");
inOrder(p.right); //中根次序遍历右子树
}
}
public void postOrder() //后根次序遍历二叉树
{
System.out.print("\n后根序列： ");
postOrder(root);
}
private void postOrder(BinaryNode<E> p) //后根次序遍历以p结点为根的子二叉树
{
if (p!=null)
{
postOrder(p.left);
postOrder(p.right);
System.out.print(p.data+" ");
}
}
//【例6.1】 构造并遍历二叉树。
//3. 基于遍历的操作
public int count() //求一棵二叉树中所有结点个数
{
return count(root);
}
public int count(BinaryNode<E> p) //求以p结点为根的子树的结点个数
{
if (p!=null)
return 1+count(p.left)+count(p.right);
else
return 0;
}
public int depth() //求二叉树的深度
{
return depth(root);
}
public int depth(BinaryNode<E> p) //求以p结点为根的子树的深度，后根次序遍历
{
if (p!=null)
{
int ld = depth(p.left); //求左子树的深度
int rd = depth(p.right);
return (ld>=rd) ? ld+1 : rd+1;
}
return 0;
}
public BinaryNode<E> search(E value) //查找值为value的结点
{
return search(root, value);
}
public BinaryNode<E> search(BinaryNode<E> p, E value) //在以p为根的子树中查找值为value的结点
{ //先根次序遍历，返回查找到结点，若未找到返回null
BinaryNode<E> find=null; //记载找到结点
if (p!=null && value!=null)
{
if (p.data.equals(value))
find = p; //查找成功
else
{
find = search(p.left, value); //在左子树中查找
if (find==null)
find=search(p.right, value); //若左子树中未找到，则继续在右子树中查找
}
}
return find; //返回找到结点
}
public BinaryNode<E> getParent(BinaryNode<E> node) //返回指定结点node的父母结点
{ //若空树、未找到或node为根，返回null
if (root==null || node==null || node==root)
return null;
return getParent(root, node);
}
public BinaryNode<E> getParent(BinaryNode<E> p, BinaryNode<E> node)
{ //在以p为根的子树中查找并返回node结点的父母结点
BinaryNode<E> find=null; //记载找到结点
if (p!=null)
{
if (p.left==node || p.right==node)
find = p; //查找成功
else
{
find = getParent(p.left, node); //在左子树中查找
if (find==null)
find = getParent(p.right, node); //若左子树中未找到，则继续在右子树中查找
}
}
return find; //返回找到的父母结点
}
//6.3.4 构造二叉树
// 1、以先根、中根次序遍历序列建立二叉树
public BinaryTree(String prestr,String instr) //1、以先根、中根次序遍历序列建立二叉树
{
root=create(prestr,instr);
//root=create2(prestr,instr);
}
public BinaryNode create(String prestr, String instr)
{
BinaryNode<String> p=null;
int k,n;
String first,presub,insub;
n=prestr.length();
if(n>0)
{
System.out.print("prestr="+prestr+"\t instr="+instr);
first=prestr.substring(0,1);
p=new BinaryNode<String>(first);
k=instr.indexOf(first);
System.out.println("\t first="+first+"\t k="+k);
presub=prestr.substring(1,k+1);
insub=instr.substring(0,k);
p.left=create(presub,insub);
presub=prestr.substring(k+1,n);
insub=instr.substring(k+1,n);
p.right=create(presub,insub);
}
return p;
}
public BinaryNode create2(String instr, String poststr) //以中根、后根次序遍历序列建立二叉树
{
BinaryNode<String> p=null;
int k,n;
String last,postsub,insub;
n=poststr.length();
if(n>0)
{
System.out.print("instr="+instr+"\t poststr="+poststr);
last=poststr.substring(poststr.length()-1,poststr.length());
p=new BinaryNode<String>(last);
k=instr.indexOf(last);
System.out.println("\t last="+last+"\t k="+k);
postsub=poststr.substring(0,k);
insub=instr.substring(0,k);
p.left=create2(insub,postsub);
postsub=poststr.substring(k,n-1);
insub=instr.substring(k+1,n);
p.right=create2(insub,postsub);
}
return p;
}
// 2、以标明空子树的先根序列构造一棵二叉树
public BinaryTree(E[] preorder) //2、以标明空子树的先根序列构造一棵二叉树
{
root=create(preorder);
}
private int i=0;
private BinaryNode<E> create(E[] preorder) //创建一棵子树，当前结点值是preorder[i]
{ //返回所创建子树的根结点
BinaryNode<E> p = null;
if (i<preorder.length)
{
E elem=preorder[i];
i++;
if (elem!=null)
{
p = new BinaryNode<E>(elem); //建立p结点
p.left = create(preorder); //建立p的左子树
p.right = create(preorder); //建立p的右子树
}
}
return p;
}
// 3、以广义表表示建立二叉树
public BinaryTree(String GenListStr)
{
System.out.println("GenListStr="+GenListStr);
if(GenListStr.length()>0)
root=create(GenListStr); //以GenListStr的全部元素建立一棵二叉树
}
public BinaryNode create(String GenListStr) //以GenListStr的部分元素（从i开始）建立一棵子树
{
BinaryNode p=null;
char ch=GenListStr.charAt(i);
if(ch>='A' && ch<='Z') //大写字母
{
p=new BinaryNode<String>(ch+""); //建立结点
i++; //跳过大写字母
ch=GenListStr.charAt(i);
if(ch=='(')
{
i++; //跳过(
p.left=create(GenListStr); //建立左子树
i++; //跳过#
p.right=create(GenListStr); //建立右子树
i++; //跳过）
}
}
if(ch=='#')
i++; //跳过#
return p; //ch非大写字母时，返回null
}
//【例6.2】 输出二叉树中指定结点的所有祖先结点。
//6.3.5 二叉树的插入和删除操作
public void insert(BinaryNode<E> p, E element, boolean leftChild) //插入元素element作为p结点的孩子
{ //若leftChild为true，插入结点作为左孩子，否则作为右孩子
if (p!=null)
{
BinaryNode<E> q = new BinaryNode<E>(element);
if (leftChild)
{
q.left = p.left; //p结点的原左孩子成为q结点的左孩子
p.left = q; //q结点作为p结点的左孩子
}
else
{
q.right = p.right; //p结点的原右孩子成为q结点的右孩子
p.right = q; //q结点作为p结点的右孩子
}
}
}
public void insert(BinaryNode<E> p, E element) //插入元素element作为p结点的左孩子
{
insert(p, element, true);
}
public void remove(BinaryNode<E> p, boolean leftChild) //删除p结点的左/右子树
{ //若leftChild为true，删除左子树，否则删除右子树
if (p!=null)
{
if (leftChild)
p.left = null;
else
p.right = null;
}
}
public void remove(BinaryNode<E> p) //删除p结点的左子树
{
remove(p, true);
}
//6.3.6 二叉树遍历的非递归算法
public void preOrderTraverse() //先根次序遍历二叉树的非递归算法
{
System.out.print("先根次序遍历（非递归）： ");
LinkedStack<BinaryNode<E>> stack = new LinkedStack<BinaryNode<E>>(); //创建一个空栈
BinaryNode<E> p = this.root;
while(p!=null || !stack.isEmpty()) //p非空或栈非空时
if(p!=null)
{
System.out.print(p.data+" "); //访问结点
stack.push(p); //p结点入栈
p=p.left; //进入左子树
}
else //p为空且栈非空时
{
p=stack.pop(); //p指向出栈结点
p=p.right; //进入右子树
}
System.out.println();
}
public void inOrderTraverse() //中根次序遍历二叉树的非递归算法
{
System.out.print("中根次序遍历（非递归）： ");
LinkedStack<BinaryNode<E>> stack = new LinkedStack<BinaryNode<E>>(); //创建一个空栈
BinaryNode<E> p = this.root;
while(p!=null || !stack.isEmpty()) //p非空或栈非空时
if(p!=null)
{
stack.push(p); //p结点入栈
p=p.left; //进入左子树
}
else //p为空且栈非空时
{
p=stack.pop(); //p指向出栈结点
System.out.print(p.data+" "); //访问结点
p=p.right; //进入右子树
}
System.out.println();
}
//后根次序未写
//6.3.7 二叉树的层次遍历
public void levelOrder() //按层次遍历二叉树
{
LinkedQueue<BinaryNode<E>> que=new LinkedQueue<BinaryNode<E>>(); //创建一个空队列
BinaryNode<E> p=this.root;
System.out.print("层次遍历： ");
while(p!=null)
{
System.out.print(p.data+ " ");
if(p.left!=null)
que.enqueue(p.left); //p的左孩子结点入队
if(p.right!=null)
que.enqueue(p.right); //p的右孩子结点入队
p = que.dequeue(); //p指向出队结点
}
System.out.println();
}
//第6章习题
public void leaf() //遍历输出叶子结点
{
leaf(root);
}
private void leaf(BinaryNode<E> p) //先根次序遍历，输出叶子结点，3种遍历次序结果一样
{
if(p!=null)
{
if (p.isLeaf())
System.out.print(p.data+" ");
leaf(p.left);
leaf(p.right);
}
}
public int countLeaf() //求一棵二叉树中所有叶子结点个数
{
return countLeaf(root);
}
private int countLeaf(BinaryNode<E> p) //求以p结点为根的子树的叶子结点个数
{
if (p==null)
return 0;
if (p.isLeaf())
return 1;
return countLeaf(p.left)+countLeaf(p.right);
}
public BinaryTree(BinaryTree<E> bitree) //以已知的bitree构造二叉树
{
this.root = (bitree.root);
}
private BinaryNode<E> (BinaryNode<E> p) //复制以p根的子二叉树
{
BinaryNode<E> q = null;
if(p!=null)
{
q = new BinaryNode<E>(p.data);
q.left = (p.left); //复制左子树
q.right = (p.right); //复制右子树
}
return q; //返回建立子树的根结点
}
public boolean equals(Object obj) //比较两棵二叉树是否相等
{
if (obj == this)
return true;
if (obj instanceof BinaryTree)
{
BinaryTree<E> bitree = (BinaryTree)obj;
return equals(this.root, bitree.root);
}
return false;
}
private boolean equals(BinaryNode<E> p, BinaryNode<E> q) //判断以p和q结点为根的两棵子树是否相等
{ //递归方法
if(p==null && q==null)
return true;
if(p!=null && q!=null)
return (p.data.equals(q.data)) && equals(p.left, q.left) && equals(p.right, q.right);
return false;
}
public boolean replace(E old, E value) //将首次出现的值为old结点值替换为value
{
BinaryNode<E> find=search(old); //查找值为old的结点
if(find!=null)
find.data = value; //替换结点元素值
return find!=null;
}
public void replaceAll(E old, E value) //将值为old的结点全部替换为value
{
replaceAll(root, old, value);
}
private void replaceAll(BinaryNode<E> p, E old, E value) //在以p为根的子树中实现全部替换
{
if(p!=null)
{
if(p.data.equals(old))
p.data = value;
replaceAll(p.left, old, value);
replaceAll(p.right, old, value);
}
}
public static void main(String args[])
{
String[] preorder = {"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","H"};
BinaryTree<String> bitree = new BinaryTree<String>(preorder);
preorder[0]="Z";
bitree.preOrder();
bitree.inOrder();
bitree.postOrder();
System.out.println("\n结点个数： "+bitree.count());
System.out.println("高度： "+bitree.depth());
System.out.print("叶子结点： ");
bitree.leaf();
System.out.println(" , 共"+bitree.countLeaf()+"个");
BinaryTree<String> bitree2 = new BinaryTree<String>(bitree);
System.out.println("两棵二叉树相等? "+bitree.equals(bitree2));
System.out.println("第2棵二叉树替换(\"D\",\"F\")： "+bitree2.replace("D","F"));
System.out.println("两棵二叉树相等? "+bitree.equals(bitree2));
System.out.println("第2棵二叉树全部替换(\"F\",\"Y\") ");
bitree2.replaceAll("F","Y");
bitree2.preOrder();
BinaryNode<String> find = bitree.search("D"); //查找
bitree.insert(find, "Z");
System.out.println("插入Z作为 "+find.data+" 的左孩子\n");
bitree.levelOrder();
bitree.preOrderTraverse();
bitree.inOrderTraverse();
String[] preorder2 = {"A","B",null,null,"C"}; //标明空子树的先根序列
BinaryTree<String> bitree3 = new BinaryTree<String>(preorder2);
bitree3.preOrder();
bitree3.inOrder();
bitree3.postOrder();
/*
BinaryTree<String> bitree4 = new BinaryTree<String>(preorder2);
bitree4.root = bitree4.create(preorder2); //错，i越界，私有化可避免问题
bitree4.preOrder();
*/
String[] preorder3 = {"D","B","A",null,null,"C",null,null,"E"}; //二叉排序树
BinaryTree<String> bitree5 = new BinaryTree<String>(preorder3);
bitree5.inOrder();
System.out.println("\n二叉排序树? "+bitree5.isSorted());
}
//第8章习题
public boolean isSorted() //判断一棵二叉树是否为二叉排序树
{
return isSorted(this.root);
}
public boolean isSorted(BinaryNode<E> p)
{
boolean yes = true;
if (p!=null)
{
if (!(p.data instanceof Comparable))
return false;
Comparable cmpobj = (Comparable)p.data;
if ((p.left==null || p.left!=null && cmpobj.compareTo(p.left.data)>0) &&
(p.right==null || p.right!=null && cmpobj.compareTo(p.right.data)<0))
{
yes = isSorted(p.left);
if (yes)
yes = isSorted(p.right);
}
else
yes = false;
}
return yes;
}
}
/*
程序运行结果如下：
先根序列： A B D G C E F H
中根序列： D G B A E C H F
后根序列： G D B E H F C A
结点个数： 8
高度： 4
叶子结点： G E H , 共3个
两棵二叉树相等? true
第2棵二叉树替换("D","F")： true
两棵二叉树相等? false
第2棵二叉树全部替换("F","Y")
先根序列： A B Y G C E Y H
第1棵二叉树查找： D
层次遍历： A B C D E F Z G H
先根次序遍历（非递归）： A B D Z G C E F H
中根次序遍历（非递归）： Z D G B A E C H F
先根序列： A B D G C E F H
中根序列： D G B A E C H F
后根序列： G D B E H F C A
中根序列： A B C D E
二叉排序树? true
*/
这是二叉树的所有方法 及实现实例
还有就是需要建立节点类 你应该知道怎么建的吧
3. 二叉树类及其实现
二叉树结点类
1 using System;
2 public class Node
3 {
4 //成员变量
5 private object _data; //数据
6 private Node _left; //左孩子
7 private Node _right; //右孩子
8 public object Data
9 {
10 get { return _data; }
11 }
12 public Node Left //左孩子
13 {
14 get { return _left; }
15 set { _left = value; }
16 }
17 public Node Right //右孩子
18 {
19 get { return _right; }
20 set { _right = value; }
21 }
22 //构造方法
23 public Node(object data)
24 {
25 _data = data;
26 }
27 public override string ToString()
28 {
29 return _data.ToString();
30 }
31 }
32
Node类专门用于表示二叉树中的一个结点，它很简单，只有三个属性：Data表示结点中的数据；Left表示这个结点的左孩子，它是Node类型；Right表示这个结点的右孩子，它也是Node类型。
【例6-1 BinaryTree.cs】二叉树集合类
1 using System;
2 public class BinaryTree
3 { //成员变量
4 private Node _head; //头指针
5 private string cStr; //用于构造二叉树的字符串
6 public Node Head //头指针
7 {
8 get { return _head; }
9 }
10 //构造方法
11 public BinaryTree(string constructStr)
12 {
13 cStr = constructStr;
14 _head = new Node(cStr[0]); //添加头结点
15 Add(_head, 0); //给头结点添加孩子结点
16 }
17 private void Add(Node parent, int index)
18 {
19 int leftIndex = 2 * index + 1; //计算左孩子索引
20 if (leftIndex < cStr.Length) //如果索引没超过字符串长度
21 {
22 if (cStr[leftIndex] != '#') //'#'表示空结点
23 { //添加左孩子
24 parent.Left = new Node(cStr[leftIndex]);
25 //递归调用Add方法给左孩子添加孩子节点
26 Add(parent.Left, leftIndex);
27 }
28 }
29 int rightIndex = 2 * index + 2;
30 if (rightIndex < cStr.Length)
31 {
32 if (cStr[rightIndex] != '#')
33 { //添加右孩子
34 parent.Right = new Node(cStr[rightIndex]);
35 //递归调用Add方法给右孩子添加孩子节点
36 Add(parent.Right, rightIndex);
37 }
38 }
39 }
40 public void PreOrder(Node node) //先序遍历
41 {
42 if (node != null)
43 {
44 Console.Write(node.ToString()); //打印字符
45 PreOrder(node.Left); //递归
46 PreOrder(node.Right); //递归
47 }
48 }
49 public void MidOrder(Node node) //中序遍历
50 {
51 if (node != null)
52 {
53 MidOrder(node.Left); //递归
54 Console.Write(node.ToString()); //打印字符
55 MidOrder(node.Right); //递归
56 }
57 }
58 public void AfterOrder(Node node) //后继遍历
59 {
60 if (node != null)
61 {
62 AfterOrder(node.Left); //递归
63 AfterOrder(node.Right); //递归
64 Console.Write(node.ToString()); //打印字符
65 }
66 }
67 }
68
BinaryTree是一个二叉树的集合类，它属于二叉链表，实际存储的信息只有一个头结点指针（Head），由于是链式存储结构，可以由Head指针出发遍历整个二叉树。为了便于测试及添加结点，假设BinaryTree类中存放的数据是字符类型，第5行声明了一个字符串类型成员cStr，它用于存放结点中所有的字符。字符串由满二叉树的方式进行构造，空结点用‘#’号表示（参考本章“二叉树存储结构”这一小节中的“顺序存储结构”）。图6.13所示的二叉树可表示为：“ABCDE#F”。
11～16行的构造方法传入一个构造字符串，并在Add()方法中根据这个字符串来构造二叉树中相应的结点。需要注意，这个构造方法只用于测试。
17～39行的Add()方法用于添加结点，它的第一个参数parent表示需要添加孩子结点的双亲结点，第二个参数index表示这个双亲结点的编号（编号表示使用顺序存储结构时它在数组中的索引，请参考本章“二叉树存储结构”这一小节中的“顺序存储结构”）。添加孩子结点的方法是先计算孩子结点的编号，然后通过这个编号在cStr中取出相应的字符，并构造新的孩子结点用于存放这个字符，接下来递归调用Add()方法给孩子结点添加它们的孩子结点。注意，这个方法只用于测试。
40～48行代码的PreOrder()方法用于先序遍历，它的代码跟之前所讲解的先序遍历过程完全一样。
49～57行代码的MidOrder()方法用于中序遍历。
58～66行代码的AfterOrder()方法用于后序遍历。
以上三个方法都使用了递归来完成遍历，这符合二叉树的定义。
【例6-1 Demo6-1.cs】二叉树深度优先遍历测试
1 using System;
2 class Demo6_1
3 {
4 static void Main(string[] args)
5 { //使用字符串构造二叉树
6 BinaryTree bTree = new BinaryTree("ABCDE#F");
7 bTree.PreOrder(bTree.Head); //先序遍
8 Console.WriteLine();
9 bTree.MidOrder(bTree.Head); //中序遍
10 Console.WriteLine();
11 bTree.AfterOrder(bTree.Head); //后序遍
12 Console.WriteLine();
13 }
14 }
15
运行结果：
ABDECF
DBEACF
DEBFCA
6.3.2 二叉树的宽度优先遍历
之前所讲述的二叉树的深度优先遍历的搜索路径是首先搜索一个结点的所有子孙结点，再搜索这个结点的兄弟结点。是否可以先搜索所有兄弟和堂兄弟结点再搜索子孙结点呢？
由于二叉树结点分属不同的层次，因此可以从上到下、从左到右依次按层访问每个结点。它的访问顺序正好和之前所述二叉树顺序存储结构中的结点在数组中的存放顺序相吻合。如图6.13中的二叉树使用宽度优先遍历访问的顺序为：ABCDEF。
这个搜索过程不再需要使用递归，但需要借助队列来完成。
（1） 将根结点压入队列之中，开始执行步骤(2)。
（2） 若队列为空，则结束遍历操作，否则取队头结点D。
（3） 若结点D的左孩子结点存在，则将其左孩子结点压入队列。
（4） 若结点D的右孩子结点存在，则将其右孩子结点压入队列，并重复步骤(2)。
【例6-2 BinaryTreeNode.cs.cs】二叉树结点类，使用例6-1同名文件。
【例6-2 LevelOrderBinaryTree.cs】包含宽度优先遍历方法的二叉树集合类
打开例6-1的【BinaryTree.cs】文件，在BinaryTree类中添加如入方法后另存为LevelOrderBinaryTree.cs文件。
1 public void LevelOrder() //宽度优先遍历
2 {
3 Queue queue = new Queue(); //声明一个队例
4 queue.Enqueue(_head); //把根结点压入队列
5 while (queue.Count > 0) //只要队列不为空
6 {
7 Node node = (Node)queue.Dequeue(); //出队
8 Console.Write(node.ToString()); //访问结点
9 if (node.Left != null) //如果结点左孩子不为空
10 { //把左孩子压入队列
11 queue.Enqueue(node.Left);
12 }
13 if (node.Right != null) //如果结点右孩子不为熔
14 { //把右孩子压入队列
15 queue.Enqueue(node.Right);
16 }
17 }
18 }
【例6-2 Demo6-2.cs】二叉树宽度优先遍历测试
1 using System;
2 class Demo6_2
3 {
4 static void Main(string[] args)
5 { //使用字符串构造二叉树
6 BinaryTree bTree = new BinaryTree("ABCDE#F");
7 bTree.LevelOrder();
8 }
9 }
运行结果：ABCDEF
4. 完全二叉树的存储结构通常采用顺序存储结构()
正确。
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。
(4)23树存储结构扩展阅读：
判断一棵树是否是完全二叉树的思路
1、如果树为空，则直接返回错。
2、如果树不为空：层序遍历二叉树。
如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列。
如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树。
如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树。
5. 二叉树的顺序存储结构怎么放
此结构是将二叉树的所有结点，
按照一定的次序，存储到一片连续的存储单元中。
因此，必须将结点排成一个适当的线性序列，
使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。
这种结构特别适用于近似满二叉树。
在一棵具有n个结点的近似满二叉树中，
我们从树根起，自上层到下层，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列
6. 二叉树通常链式结构还有什么结构
二叉树就物理结构来分可以分成：顺序存储结构和链式存储结构。
（1）顺序存储结构：
顺序存储结构，顾名思义就是二叉树的数据元素存放在一组连续的存储单元中。其主要有一下几个特点：
①逻辑上相邻的两个元素在物理位置上也是相邻的；
②操作删除和插入的时候，需要整体移动元素；
③需要预先分配空间，不能动态增长；
（2）链式存储结构：
链式存储结构中二叉树的每个结点至少包含三个域：数据域、左指针域和右指针域。其二叉树是通过指针实现，链式存储结构有以下几个特点：
①逻辑上相邻的两个元素在物理位置上不一定是相邻的；
②操作删除和插入的时候，不需要整体移动元素；只需要修改相应的指针即可；
③不需要预先分配空间；
④存储指针本身会消耗一定的存储的空间；
7. 树的存储表示是什么
树的存储结构根据应用的不同而不同，有的从双亲的角度考虑，引出了双亲表示法，有的从孩子的角度考虑，给出孩子表示法，还有的从孩子和兄弟的角度来讨论。这些都是人们在大量的应用中所使用的不同形式的存储结构，这里介绍常用的双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法。
1.双亲表示法由树的定义可知，树中每个结点都有且仅有一个双亲结点，根据这一特性，可以用一组连续的一维数组来存储树中的各个结点（一般按层次存储），数组中的一个元素对应树中的一个结点，其中包括结点的数据信息以及该结点的双亲在数组中的下标。树的这种存储方法称为双亲表示法，双亲表示法的结点结构如图1所示，其中，data表示数据域，存储树中结点的数据信息，parent表示指针域，存储该结点的双亲在数组中的下标。
1.双亲表示法的存储结构2）双亲表示法示例图1所示的树的双亲表示如图1所示，这是一棵树及其双亲表示法的存储结构。根结点A无双亲，所以parent的值为－1，G、H和I的parent值为4，表示它们的双亲是下标为4的结点E。这种存储结构利用任一结点的双亲是唯一的性质，可以方便地直接找到任一结点的双亲结点，但求结点的孩子结点时需要扫描整个数组。
图1树的双亲表示法示例
8. 树的存储结构
常用的有：1、双亲表示，2、孩子链表表示，3、双亲孩子链表表示，4、孩子兄弟链表表示
9. 二叉树 两种存储结构的优缺点
顺序存储可能会浪费空间，但是读取某个指定的节点的时候效率比较高，链式存储相对二叉树比较大的时候浪费空间较少，但是读取某个指定节点的时候效率偏低O(nlogn)。
在数据的顺序存储中，由于每个元素的存储位置都可以通过简单计算得到，所以访问元素的时间都相同；而在数据的链接存储中，由于每个元素的存储位置保存在它的前驱或后继结点中，所以只有当访问到其前驱结点或后继结点后才能够按指针访问到。
(9)23树存储结构扩展阅读：
分类：
顺序存储方法它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
链接存储方法它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。
10. 数据结构，树的常用存储方式
存入文本文件，每行：孩子节点-父节点。
这样也方便用Hadoop进行处理。