建樹的存儲結構
二叉樹存儲結構採用鏈式存儲結構，對於滿二叉樹與完全二叉樹可以按層序進行順序4.3關系代數關系資料庫系統的特點之一是它建立在數據理論的基礎之上，有
Ⅱ 急！二叉樹的存儲結構，並完成：建立、查找、計算結點數、求高度、三種遍歷方式
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
*/
這是二叉樹的所有方法 及實現實例
還有就是需要建立節點類 你應該知道怎麼建的吧
Ⅲ 採用順序存儲方法和鏈式存儲方法分別畫出圖6.1所示二叉樹的存儲結構。【在線等】
線性是線性，順序是順序，線性是邏輯結構，順序是儲存結構，兩者不是一個概念。線性是指一個節點只有一個子節點，而樹，或二叉樹一個節點後有多個子節點，且子節點不能相互聯系。
順序存儲可能會浪費空間(在非完全二叉樹的時候)，但是讀取某個指定的節點的時候效率比較高。
鏈式存儲相對二叉樹比較大的時候浪費空間較少，但是讀取某個指定節點的時候效率偏低。
二叉樹的順序存儲，尋找後代節點和祖先節點都非常方便，但對於普通的二叉樹，順序存儲浪費大量的存儲空間，同樣也不利於節點的插入和刪除。因此順序存儲一般用於存儲完全二叉樹。
鏈式存儲相對順序存儲節省存儲空間，插入刪除節點時只需修改指針，但回尋找指定節點時很不方便。不過普通答的二叉樹一般是用鏈式存儲結構。
(3)建樹的存儲結構擴展閱讀：
(1)完全二叉樹——若設二叉樹的高度為h，除第h層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。
(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。
(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別於AVL演算法），它是一棵二叉排序樹，且具有以下性質：是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。
二叉樹是樹的一種特殊情形，是一種更簡單而且應用更加廣泛的樹。
Ⅳ 用c語言編寫：建立一棵以二叉鏈表結構存儲的二叉樹，並對其進行遍歷。求該二叉樹中的結點個數等操作。
存儲結構
typedef struct {
int weight;
int parent, lchild, rchild;
} HTNode ,*HuffmanTree; // 動態分配數組存儲huffman樹
演算法設計
void createHuffmantree(){
ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);// 動態分配數組存儲huffman樹,0號單元未用
// m:huffman 樹中的結點數（m=2*n-1）
for (i=1;i<=m;++i)
ht[i].parent= ht[i]->lch= ht[i]->rch=0;
for (i=1;i<=n;++i)
ht[i].weight=w[i]; //初始化，w[i]：n個葉子的權值
for (i=n+1;i<=m,++i) ｛ //建哈夫曼樹
select(i-1),s1,s2); //在ht[k](1<=k<=i-1)中選擇兩個雙親域為零而權值取最小的結點 :s1和s2
ht[s1].parent= ht[s2].parent=i;
ht[i].lch=s1;
ht[i].rch=s2;
ht[i].weight=ht[s1].weight + ht[s2].weight ;
};
}
Ⅳ 樹的存儲表示是什麼
樹的存儲結構根據應用的不同而不同，有的從雙親的角度考慮，引出了雙親表示法，有的從孩子的角度考慮，給出孩子表示法，還有的從孩子和兄弟的角度來討論。這些都是人們在大量的應用中所使用的不同形式的存儲結構，這里介紹常用的雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法。
1.雙親表示法由樹的定義可知，樹中每個結點都有且僅有一個雙親結點，根據這一特性，可以用一組連續的一維數組來存儲樹中的各個結點（一般按層次存儲），數組中的一個元素對應樹中的一個結點，其中包括結點的數據信息以及該結點的雙親在數組中的下標。樹的這種存儲方法稱為雙親表示法，雙親表示法的結點結構如圖1所示，其中，data表示數據域，存儲樹中結點的數據信息，parent表示指針域，存儲該結點的雙親在數組中的下標。
1.雙親表示法的存儲結構2）雙親表示法示例圖1所示的樹的雙親表示如圖1所示，這是一棵樹及其雙親表示法的存儲結構。根結點A無雙親，所以parent的值為－1，G、H和I的parent值為4，表示它們的雙親是下標為4的結點E。這種存儲結構利用任一結點的雙親是唯一的性質，可以方便地直接找到任一結點的雙親結點，但求結點的孩子結點時需要掃描整個數組。
圖1樹的雙親表示法示例
Ⅵ 數據結構 c語言版二叉樹(1) 建立一棵含有n個結點的二叉樹，採用二叉鏈表存儲；
#include<stdio.h>
#include<stdlib.h>
typedef struct node *tree_pointer;
struct node{
char ch;
tree_pointer left_child,right_child;
};
tree_pointer root=NULL;
tree_pointer create(tree_pointer ptr)
{
char ch;
scanf("%c",&ch);
if(ch==' ')
ptr=NULL;
else{
ptr=(tree_pointer)malloc(sizeof(node));
ptr->ch=ch;
ptr->left_child=create(ptr->left_child);
ptr->right_child=create(ptr->right_child);
}
return ptr;
}
void preorder(tree_pointer ptr)
{
if(ptr){
printf("%c",ptr->ch);
preorder(ptr->left_child);
preorder(ptr->right_child);
}
}
void inorder(tree_pointer ptr)
{
if(ptr){
inorder(ptr->left_child);
printf("%c",ptr->ch);
inorder(ptr->right_child);
}
}
void postorder(tree_pointer ptr)
{
if(ptr){
postorder(ptr->left_child);
postorder(ptr->right_child);
printf("%c",ptr->ch);
}
}
void main()
{
printf("構建一個二叉樹（結點數為n)：\n");
root=create(root);
printf("前序遍歷二叉樹：\n");
preorder(root);
printf("\n");
printf("中序遍歷二叉樹：\n");
inorder(root);
printf("\n");
printf("後序遍歷二叉樹：\n");
postorder(root);
printf("\n");
}
Ⅶ 數據結構，樹的常用存儲方式
存入文本文件，每行：孩子節點-父節點。
這樣也方便用Hadoop進行處理。