二叉樹的存儲和遍歷
『壹』 運用C++如何使用二叉鏈表存儲二叉樹，遍歷輸出葉子節點路徑，遞歸輸出葉子節點值，輸出樹的深度
構造的二叉樹結構如下：
『貳』 急！二叉樹的存儲結構，並完成：建立、查找、計算結點數、求高度、三種遍歷方式
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
*/
這是二叉樹的所有方法 及實現實例
還有就是需要建立節點類 你應該知道怎麼建的吧