二叉樹的建立演算法

⑴ 數據結構-二叉樹的創建

如果要在內存中建立一個如下左圖這樣的樹，wield能讓每個結點確認是否有左右孩子，我們對它進行擴展，變成如下右圖的樣子，也就是將二叉樹中的每個結點的空指針引出一個虛結點，其值為一個特定值，比如」#」，稱之為擴展二叉樹。擴展二叉樹就可以做到一個遍歷序列確定一棵二叉樹了。如前序遍歷序列為AB#D##C##。

//創建樹方法二
intCreateTree2(BiTree*t)
{
charch;
scanf("%c",&ch);

if(ch=='#')
{
(*t)=NULL;
}
else
{
(*t)=(BiTree)malloc(sizeof(BitNode));
if((*t)==NULL)
{
fprintf(stderr,"malloc()errorinCreateTree2. ");
returnERROR;
}

(*t)->data=ch;
CreateTree2(&((*t)->lchild));
CreateTree2(&((*t)->rchild));
}
returnOK;
}

其實建立二叉樹，也是利用了遞歸的原理。只不過在原來應該列印結點的地方，改成生成結點、給結點賦值的操作而已。因此，完全可以用中序或後序遍歷的方式實現二叉樹的建立，只不過代碼里生成結點和構造左右子樹的代碼順序交互一下即可。

⑵ 二叉樹的建立

// 中序遍歷偽代碼：非遞歸版本，用棧實現，版本2
void InOrder2(TNode* root)
{
Stack S;
if( root != NULL )
{
S.push(root);
}
while ( !S.empty() )
{
TNode* node = S.pop();
if ( node->bPushed )
{ // 如果標識位為true,則表示其左右子樹都已經入棧，那麼現在就需要訪問該節點了
Visit(node);
}
else
{ // 左右子樹尚未入棧，則依次將 右節點，根節點，左節點 入棧
if ( node->right != NULL )
{
node->right->bPushed = false; // 左右子樹均設置為false
S.push(node->right);
}
node->bPushed = true; // 根節點標志位為true
S.push(node);
if ( node->left != NULL )
{
node->left->bPushed = false;
S.push(node->left);
}
}
}
}
對比先序遍歷，這個演算法需要額外的增加O(n)的標志位空間。另外，棧空間也擴大，因為每次壓棧的時候都壓入根節點與左右節點，因此棧空間為O(n)。時間復雜度方面，每個節點壓棧兩次，作為子節點壓棧一次，作為根節點壓棧一次，彈棧也是兩次。因此無論從哪個方面講，這個方法效率都不及InOrder1。

後序

void postOrder(TreeNode<T> *root)
{
stack<TreeNode<T>*> st;
TreeNode<T> *p = root;
TreeNode<T> *pre = NULL;//pre表示最近一次訪問的結點

while(p || st.size()!=0)
{
//沿著左孩子方向走到最左下 。
while(p)
{
st.push(p);
p = p->left;
}
//get the top element of the stack
p = st.top();
//如果p沒有右孩子或者其右孩子剛剛被訪問過
if(p->right == NULL || p->right == pre)
{
/ isit this element and then pop it
cout << "visit: " << p->data << endl;
st.pop();
pre = p;
p = NULL;

}
else
{
p = p->right;

}
}//end of while(p || st.size()!=0)

}
怎麼樣

⑶ 二叉樹演算法

二叉樹的演算法主要分為三種：先序遍歷，中序遍歷和後序遍歷。二叉樹（Binary Tree）是n（n>=0）個節點的有限集合，該集合或者空集（稱為空二叉樹），或者由一個根節點和兩棵互不相交的，分別稱為根節點的左子樹和右子樹的二叉樹組成。

(3)二叉樹的建立演算法擴展閱讀

二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的'子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^（i 1）個結點;深度為k的二叉樹至多有2^k 1個結點;對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0 = n2 + 1。二叉樹演算法常被用於實現二叉查找樹和二叉堆。

概念

編輯 語音

二叉樹是每個節點最多有兩個子樹的有序樹。通常子樹被稱作「左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用於實現二叉查找樹和二叉堆。

基本形態：

二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹演算法有五種基本形態：

(1)空二叉樹——(a)

(2)只有一個根結點的二叉樹——(b);

(3)右子樹為空的二叉樹——(c);

(4)左子樹為空的二叉樹——(d);

(5)完全二叉樹——(e)

注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。

⑷ 二叉樹怎麼操作

1.構造二叉樹給定一棵二叉樹，要對它進行操作必須先把它存儲到計算機中，二叉樹的存儲可以採用順序存儲結構，也可以採用鏈式存儲結構，鏈式存儲結構有二叉鏈表和三叉鏈表等。在這里主要討論二叉鏈表存儲結構。

（1）以先序遞歸遍歷思想建立二叉樹。

①建立二叉樹的根結點；②先序建立二叉樹的左子樹；③先序建立二叉樹的右子樹。

（2）構造二叉樹的操作演算法。

輸入一個二叉樹的先序序列，構造這棵二叉樹。為了保證唯一地構造出所希望的二叉樹，在鍵入這棵樹的先序序列時，需要在所有空二叉樹的位置上填補一個特殊的字元，比如#。在演算法中，需要對每個輸入的字元進行判斷，如果對應的字元是#，則在相應的位置上構造一棵空二叉樹；否則，創建一個新結點。整個演算法結構以先序遍歷遞歸演算法為基礎，二叉樹中結點之間的指針連接是通過指針參數在遞歸調用返回時完成的。

⑸ 二叉樹演算法

二叉樹是沒有度為1的結點。
完全二叉樹定義：
若設二叉樹的高度為h，除第
h
層外，其它各層
(1～h-1)
的結點數都達到最大個數，第
h
層從右向左連續缺若干結點，這就是完全二叉樹。
完全二叉樹葉子結點的演算法：
如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1~n的結點一一對應，這棵二叉樹稱為完全二叉樹。
可以根據公式進行推導，假設n0是度為0的結點總數（即葉子結點數），n1是度為1的結點總數，n2是度為2的結點總數，由二叉樹的性質可知：n0＝n2＋1，則n=
n0＋n1＋n2（其中n為完全二叉樹的結點總數），由上述公式把n2消去得：n=
2n0+n1－1，由於完全二叉樹中度為1的結點數只有兩種可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合並成一個公式：n0＝（n＋1）/2
，就可根據完全二叉樹的結點總數計算出葉子結點數。
因此葉子結點數是(839+1)/2=420

⑹ 怎樣理解遞歸建立二叉樹演算法

遞歸=傳遞+回歸，即任務的下放和結果的回收。
這個需要自己慢慢體會，其實所有遞歸演算法實質上都是一樣的，理解了就萬變不離其宗了。
create（node
*root）
{
root=new
node；
寫上關於root的信息//初始化root節點
if(root滿足自定義的條件)//自定義一個遞歸的條件，即傳遞和回歸的界限，這是必須的。
{
create(root->lchild);//建左子樹
create(root->rchild);//建右子樹
}
}
總體上來看，建一顆樹，每一次調用creat（）都是只創建一個節點，把剩下的任務下放給create（root->lchild)和create(root->rchild)
，而這兩個也會重復第一個create（root）的做法，實質體現的是任務的不斷下放，當達到最後的回歸的界限的，結果又將不斷回收，對應的是函數的不斷返回，實質是退棧的過程。這個過程其實經歷了一個不斷進棧和不斷出棧的過程，對應的是任務的不斷下放和不斷提交，最後棧空，即告全部任務完成！

⑺ 二叉樹基本演算法

#include <iostream.h>
typedef struct BiTNode
{
char data;
int bit;
struct BiTNode *lchild,*rchild,*parent;
}BiTNode;

void InitBT(BiTNode *&t)//1、初始化，不帶頭結點
{
t=NULL;
}

/*void InitBT(BiTNode *t)//初始化，帶頭結點
{
t=new BiTNode;
t->lchild=t->rchild=t->parent=NULL;
}*/

int EmptyBT(BiTNode *t)//判斷隊空
{
if(t==0)
return 1;
else
return 0;
}

BiTNode *creatBT(BiTNode *t,int b)//2、創建二叉樹
{
BiTNode *p;
char ch;
cin>>ch;
if(ch=='#')return 0;
else
{
p=new BiTNode;
p->data=ch;
p->parent=t;
p->bit=b;
t=p;
t->lchild=creatBT(t,0);
t->rchild=creatBT(t,1);
}
return t;
}

void preorder(BiTNode *t)//3、先序遍歷
{
if(!EmptyBT(t))
{
cout<<t->data;
preorder(t->lchild);
preorder(t->rchild);
}
}

void inorder(BiTNode *t)//中序遍歷
{
if(!EmptyBT(t))
{
inorder(t->lchild);
cout<<t->data;
inorder(t->rchild);
}
}

void postorder(BiTNode *t)//後序遍歷
{
if(!EmptyBT(t))
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data;
}
}

void coutBT(BiTNode *t,int &m,int &n,int &i)//4、計算二叉樹中葉子結點、度為2的結點和度為1的結點的個數
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
m++;//葉子結點
else if((t->lchild!=0) && (t->rchild!=0))
i++;//度為2的結點
else
n++;//度為1的結點
coutBT(t->lchild,m,n,i);
coutBT(t->rchild,m,n,i);
}
}

void coutNode(BiTNode *t,int &k)//5、求二叉樹中結點個數
{
if(!EmptyBT(t))
{
k++;
coutNode(t->lchild,k);
coutNode(t->rchild,k);
}
}

int BTdepth(BiTNode *t)//6、求二叉樹的深度
{
int i,j;
if(EmptyBT(t))
return 0;
else
{
i=BTdepth(t->lchild);
j=BTdepth(t->rchild);
return (i>j?i:j)+1;
}
}

int Xdepth(BiTNode *t,char x)//7、查找x的層數
{
int num1,num2,n;
if(t==NULL)
return 0;
else{
if(t->data==x)
return 1;
num1=Xdepth(t->lchild,x);
num2=Xdepth(t->rchild,x);
n=num1+num2;
if(num1!=0||num2!=0)
n++;
return n;
}
}

static int flag;
void SearchChild(BiTNode *t,int k)//8、查找第k個結點的左右孩子
{
if(!EmptyBT(t))
{
if(k==0)
{
cout<<"位置不能為0!"<<endl;
return;
}
else
{
flag++;
if(flag==k)
{
if(t->lchild==0)
cout<<"無左孩子! ";
else
cout<<"左孩子為："<<(t->lchild->data)<<" ";
if(t->rchild==0)
cout<<"無右孩子!"<<endl;
else
cout<<"右孩子為："<<(t->rchild->data)<<endl;
}
else
{
SearchChild(t->lchild,k);
SearchChild(t->rchild,k);
}
}
}
}

int Xancestor(BiTNode *t,char x)//9、查找x結點祖先
{
int n,num1,num2;
if(t==NULL)
return 0;
else
{
if(t->data==x)
return 1;
num1=Xancestor(t->lchild,x);
num2=Xancestor(t->rchild,x);
n=num1+num2;
if(n!=0)
{
n++;
cout<<t->data<<" "<<endl;
}
}
}

void BTNodePath(BiTNode *t)//10、輸出所有葉子結點路徑
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
{
cout<<t->data<<"的路徑為：";
for(BiTNode *p=t;p!=0;p=p->parent)
cout<<p->data;
cout<<endl;
}
else
{
BTNodePath(t->lchild);
BTNodePath(t->rchild);
}
}
}

void BTNodebit(BiTNode *t)//11、輸出所有葉子結點編碼
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
{
cout<<t->data<<"的編碼為：";
for(BiTNode *p=t;p->parent!=0;p=p->parent)
cout<<p->bit;
cout<<endl;
}
else
{
BTNodebit(t->lchild);
BTNodebit(t->rchild);
}
}
}

void main()
{
BiTNode *t;
int m,n,i,d,q,k;
char x;
cout<<"1、初始化..."<<endl;
InitBT(t);

cout<<"2、創建二叉樹..."<<endl;
t=creatBT(t,0);

cout<<"3.1、先序遍歷..."<<endl;
preorder(t);
cout<<endl;
cout<<"3.2、中序遍歷..."<<endl;
inorder(t);
cout<<endl;
cout<<"3.3、後序遍歷..."<<endl;
postorder(t);
cout<<endl;

m=n=i=0;
cout<<"4、計算葉子結點，度為1的結點和度為2的結點的個數..."<<endl;
coutBT(t,m,n,i);
cout<<"葉子結點個數為："<<m<<endl;
cout<<"度為1的結點個數為："<<n<<endl;
cout<<"度為2的結點個數為："<<i<<endl;

q=0;
cout<<"5、計算結點個數..."<<endl;
coutNode(t,q);
cout<<"結點個數為："<<q<<endl;

d=0;
cout<<"6、計算深度..."<<endl;
d=BTdepth(t);
cout<<"深度為："<<d<<endl;

cout<<"7、求x的層數..."<<endl;
cout<<"輸入x：";
cin>>x;
if(Xdepth(t,x)==0)
cout<<"x不存在！"<<endl;
else
cout<<Xdepth(t,x)<<endl;

cout<<"8、輸入要查找孩子的結點在先序遍歷中的位置k（不等於0）：";
cin>>k;
SearchChild(t,k);
if(k>flag)
cout<<"位置超出長度!"<<endl;

cout<<"9、查詢結點的所有祖先，請輸入結點x：";
cin>>x;
int num;
num=Xancestor(t,x);
if(num==0)
cout<<"結點不存在！"<<endl;
if(num==1)
cout<<"根結點無祖先！"<<endl;

cout<<"10、輸出所有葉子結點路徑（葉→根）："<<endl;
BTNodePath(t);

cout<<"11、輸出所有葉子結點編碼（葉→根）："<<endl;
BTNodebit(t);
}