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進行處理。