Tree
1.二叉樹的性質(zhì)
二叉樹第i層(i>=1)上最多有2^(k-1)個(gè)元素凡怎。
高度為k的兒茶素最多有2^k-1 個(gè)元素
2.二叉樹的存儲(chǔ)
分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)
ps: 從1開始算的是 這里面备埃。
二叉樹的鏈接存儲(chǔ)結(jié)構(gòu)
3.二叉樹的遍歷
重點(diǎn)掌握昼榛。
- 前序遍歷(前中后是對(duì)根結(jié)點(diǎn)來(lái)說(shuō)的)
- 中序遍歷
- 后序遍歷
- 廣度遍歷(層次遍歷刘莹,隊(duì)列)
- s形遍歷(第一列從左到右罢艾,第二列從右到左)
前中后遍歷:
根據(jù)根結(jié)點(diǎn)的位置來(lái)說(shuō)的抚恒。
層次遍歷:
在進(jìn)行層次遍歷的時(shí)候拄衰,對(duì)一層節(jié)點(diǎn)訪問(wèn)完后,在按照他們的訪問(wèn)次序?qū)Ω鱾€(gè)節(jié)點(diǎn)的左右孩子做順序便利鬼癣。就完成了對(duì)下一層從左到右的訪問(wèn)陶贼。在進(jìn)行層次遍歷時(shí)啤贩,需設(shè)置一個(gè)隊(duì)列。首先將根指針入隊(duì)拜秧,然后從隊(duì)列里面彈出來(lái)一個(gè)元素痹屹,每取出一個(gè)元素,執(zhí)行兩個(gè)操作枉氮,訪問(wèn)改元素所值得節(jié)點(diǎn)志衍。如果左右節(jié)點(diǎn)不為空,加入隊(duì)列聊替。此過(guò)程循環(huán)執(zhí)行楼肪,直到隊(duì)列為空。表示層次遍歷結(jié)束惹悄。
s遍歷
層次遍歷春叫。第一層從左到右,第二層從右到左俘侠,可以通過(guò)兩個(gè)queue實(shí)現(xiàn)象缀。
package tree;
import java.util.LinkedList;
import java.util.Queue;
public class Treesearch {
static class Node{
String value;
Node leftNode;
Node rightNode;
public Node(String value,Node left,Node right){
this.value=value;
this.leftNode=left;
this.rightNode=right;
}
}
void doSth(Node root){
System.out.print(root.value+" ");
}
void preOrder(Node root){
if(root==null) return ;
doSth(root);
preOrder(root.leftNode);
preOrder(root.rightNode);
}
void inOrder(Node root){
if(root==null) return ;
inOrder(root.leftNode);
doSth(root);
inOrder(root.rightNode);
}
void postOrder(Node root){
if(root==null) return ;
postOrder(root.leftNode);
postOrder(root.rightNode);
doSth(root);
}
void breadthOrder(Node root){
Queue<Node> queue= new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
Node node=queue.poll();
doSth(node);
if(node.leftNode!=null)
queue.add(node.leftNode);
if(node.rightNode!=null)
queue.add(node.rightNode);
}
}
void pt(LinkedList<Node> queue,int t){
if(t%2==0){
for(int i=0;i<queue.size();i++){
System.out.print(queue.get(i).value+" ");
}
}else{
for(int i=queue.size()-1;i>=0;i--){
System.out.print(queue.get(i).value+" ");
}
}
}
void s_order(Node root){
LinkedList<Node> queue1= new LinkedList<>();
LinkedList<Node> queue2= new LinkedList<>();
queue1.add(root);
int i=0;
while(queue1.size()!=0){
pt(queue1, i);
i++;
while(!queue1.isEmpty()){
Node node=queue1.poll();
//doSth(node);//如果s打印。那么控制一下參數(shù)就好爷速。
if(node.leftNode!=null)
queue2.add(node.leftNode);
if(node.rightNode!=null)
queue2.add(node.rightNode);
}
LinkedList<Node> tmp=queue1;
queue1=queue2;
queue2=tmp;
}
}
Node create(){
Node d=new Node("d", null, null);
Node e=new Node("e", null, null);
Node g=new Node("g", null, null);
Node b=new Node("b", d, e);
Node c=new Node("c", null, g);
Node a=new Node("a", b, c);
return a;
}
public static void main(String[] args) {
Treesearch s= new Treesearch();
Node root=s.create();
s.preOrder(root);
System.out.println();
s.inOrder(root);
System.out.println();
s.postOrder(root);
System.out.println();
s.breadthOrder(root);
System.out.println();
s.s_order(root);
}
}
4.線索二叉樹
通過(guò)考察各種二叉鏈表央星,不管兒叉樹的形態(tài)如何,空鏈域的個(gè)數(shù)總是多過(guò)非空鏈域的個(gè)數(shù)惫东。準(zhǔn)確的說(shuō)莉给,n各結(jié)點(diǎn)的二叉鏈表共有2n個(gè)鏈域,非空鏈域?yàn)閚-1個(gè)廉沮,但其中的空鏈域卻有n+1個(gè)颓遏。如下圖所示。
因此滞时,提出了一種方法叁幢,利用原來(lái)的空鏈域存放指針,指向樹中其他結(jié)點(diǎn)坪稽。這種指針?lè)Q為線索曼玩。
? 記ptr指向二叉鏈表中的一個(gè)結(jié)點(diǎn),以下是建立線索的規(guī)則:
? (1)如果ptr->lchild為空窒百,則存放指向中序遍歷序列中該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)黍判。這個(gè)結(jié)點(diǎn)稱為ptr的中序前驅(qū);
? (2)如果ptr->rchild為空篙梢,則存放指向中序遍歷序列中該結(jié)點(diǎn)的后繼結(jié)點(diǎn)顷帖。這個(gè)結(jié)點(diǎn)稱為ptr的中序后繼;
? 顯然,在決定lchild是指向左孩子還是前驅(qū)贬墩,rchild是指向右孩子還是后繼榴嗅,需要一個(gè)區(qū)分標(biāo)志的。因此震糖,我們?cè)诿總€(gè)結(jié)點(diǎn)再增設(shè)兩個(gè)標(biāo)志域ltag和rtag录肯,注意ltag和rtag只是區(qū)分0或1數(shù)字的布爾型變量趴腋,其占用內(nèi)存空間要小于像lchild和rchild的指針變量吊说。結(jié)點(diǎn)結(jié)構(gòu)如下所示。
其中:
? (1)ltag為0時(shí)指向該結(jié)點(diǎn)的左孩子优炬,為1時(shí)指向該結(jié)點(diǎn)的前驅(qū)颁井;
? (2)rtag為0時(shí)指向該結(jié)點(diǎn)的右孩子,為1時(shí)指向該結(jié)點(diǎn)的后繼蠢护;
? (3)因此對(duì)于上圖的二叉鏈表圖可以修改為下圖的養(yǎng)子雅宾。
package tree;
public class ThreadTree {
static class TreeNode{
int value;
int ltag;
int rtag;
TreeNode left;
TreeNode right;
}
private TreeNode pre = null;
//1.建立一顆中序線索二叉樹
void inThread(TreeNode root){
if(root ==null) return ;
inThread(root.left);
if(root.left==null){
root.ltag=1;
root.left=pre;
}
if(pre!=null && pre.right==null){
pre.right=root;
pre.rtag=1;
}
pre=root;
inThread(root.right);
}
//2.查找任意節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
TreeNode getPreNode(TreeNode node ){
if(node.ltag==1){
return node.left;
}else{
node=node.left;
while(node.rtag!=1){
node=node.right;
}
return node;
}
}
//3.查找任意節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)
TreeNode getLastNode(TreeNode node){
if(node.rtag==1){
return node.right;
}else{
node=node.right;
while(node.ltag!=1){
node=node.left;
}
return node;
}
}
//4.查找值為x的節(jié)點(diǎn)
TreeNode findNode(int x,TreeNode root){
TreeNode p=root;
if(p.value==x){
return p;
}
if(p==pre){
return null;
}
findNode(x, getLastNode(p));
return null;
}
//5. insertnode
void insert(int x){
}
}
5.樹和二叉樹的轉(zhuǎn)換
本節(jié)主要介紹樹和二叉樹的轉(zhuǎn)換,森林和二叉樹的轉(zhuǎn)換葵硕,樹的遍歷和存儲(chǔ)眉抬。
樹和二叉樹的轉(zhuǎn)換
森林轉(zhuǎn)二叉樹