二叉演算法
1. 二叉樹演算法是什麼
二叉樹是每個節點最多有兩個子樹的有序樹。通常子樹被稱作「左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用於實現二叉查找樹和二叉堆。
性質
1、在二叉樹中，第i層的結點總數不超過2^(i-1)。
2、深度為h的二叉樹最多有2^h-1個結點（h>=1)，最少有h個結點。
3、對於任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1。
2. 二叉樹 演算法
原因就在於Status CreatBitTree(BitTree e) 這個函數的參數BitTree e，既然e是參數，因此你在函數體內用e=NULL; 及e=(BitTree)malloc(sizeof(BitNode)); 來給e賦值都是沒有用的，賦值不會返回給調用處。修改的話改成引用就可以了。也就是把Status CreatBitTree(BitTree e) 這一行改成Status CreatBitTree(BitTree &e) 就行了。
還有：二叉樹演算法遞歸中序輸入是abc##de#g##f### （你這應該是前序輸入吧？）
3. 請寫出計算二叉樹的深度的演算法
typedef struct tree//二叉樹的定義
{ char data; struct tree *lchild,*rchild; }TREE,*Tree;
void create(Tree t)//創建一棵二叉樹
{ char ch; scanf("%c",&ch); if(ch=='#') t=NULL;
else { t->data=ch; create(t->lchild); create(t->rchild); }
}
int deep(Tree t)//深度演算法
{ if(!t) return 0; else { ld=deep(t->lchild); rd=deep(t->rchild);
if(ld>rd) return rd+1; else return ld+1;
}
void main()//主函數
{ Tree t; create(t); printf("%d\n",deep(t)); }
4. 二叉樹結點的演算法
一個結點的度是指該結點的子樹個數。
度為1就是指只有1個子樹（左子樹或者右子樹）。
度為2的結點個數=葉結點個數-1=69
該二叉樹的總結點數=70+80+69=219
5. 二叉樹演算法如何學習
理解是關鍵，多看書，有條件上機，對理解有幫助，慢慢就會了！！！
加油啊！！！
6. 建立二叉樹的二叉鏈表演算法
CreateBinTree(BiTree *T) *T 是一個指針， 指向T 。 輸入 0 不就退出了。不過需要多輸入幾次。
7. 編寫一個遞歸演算法，將二叉鏈表表示的二叉樹，判斷兩個二叉樹是否相同的演算法
判斷二叉樹是否為完全二叉樹。完全二叉樹的定義是，前n-1層都是滿的，第n層如有空缺，則是缺在右邊，即第n層的最右邊的節點，它的左邊是滿的，右邊是空的。以3層二叉樹為例，以下情況為完全二叉樹：[方法一]這個問題的描述已經提示了解法，採用廣度優先遍歷，從根節點開始，入隊列，如果隊列不為空，循環。遇到第一個沒有左兒子或者右兒子的節點，設置標志位，如果之後再遇到有左/右兒子的節點，那麼這不是一顆完全二叉樹。這個方法需要遍歷整棵樹，復雜度為O(N)，N為節點的總數。//二叉樹結點定義typedefstructNode{intdata;structNode*left;structNode*right;}Node;//實現廣度遍歷需要隊列Queuequeue;//第n層最右節點標志boolleftMost=false;boolProcessChild(Node*child){if(child){if(!leftMost){queue.push(child);}else{returnfalse;}}else{leftMost=true;}returntrue;}boolIsCompleteBinaryTree(Node*root){//空樹也是完全二叉樹if(!root)returntrue;//首先根節點入隊列queue.push(root);while(!queue.empty()){Node*node=queue.pop();//處理左節點if(!ProcessChild(node->left))returnfalse;//處理右節點if(!ProcessChild(node->right))returnfalse;}//廣度優先遍歷完畢，此乃完全二叉樹returntrue;}[方法二]根據完全二叉樹的定義，左邊的深度>=右邊的深度。從根節點開始，分別沿著最左最右分支下去，找到最左和最右的深度。如果左邊比右邊深1，再分別檢查以左兒子和右兒子為根的兩根樹。有點遞歸的感覺了。[Tobecontinued]
8. 二叉樹的演算法
用棧來實現。
9. 二叉樹深度的演算法
#include"stdio.h"
#include"alloc.h"
typedef
char
datatype;
typedef
struct
node
{
datatype
data;
struct
node
*lchild,
*rchild;
}
bitree;
int
k
=
1;
bitree
*Q[10];
bitree
*CREAT()
{
char
ch;
int
front,
rear;
bitree
*root,
*s;
root
=
NULL;
front
=
1;
rear
=
0;
printf("\n
=======二叉樹的建立和遍歷=======\n");
printf("
請輸入字元:
");
ch
=
getchar();
while
(ch
!=
'$')
{
s
=
NULL;
if
(ch
!=
'@')
{
s
=
malloc(sizeof(bitree));
s
->
data
=
ch;
s
->
lchild
=
NULL;
s
->
rchild
=
NULL;
}
rear++;
k
=
k++;
Q[rear]
=
s;
if
(rear
==
1)
root
=
s;
else
{
if
(s
&&
Q[front])
if
(rear
%
2
==
0)
Q[front]
->
lchild
=
s;
else
Q[front]
->
rchild
=
s;
if
(rear
%
2
==
1)
front++;
}
ch
=
getchar();
}
return
root;
}
int
COUNTER(t)
bitree
*t;
{
if
(t
==
NULL)
return
0;
else
if
(t->lchild
!=
NULL
&&
t->rchild
==
NULL
||
t->lchild
==
NULL
&&
t->rchild
!=
NULL)
return
1;
else
return
COUNTER(t->lchild)
+
COUNTER(t->rchild);
}
main()
{
int
i;
bitree
*p;
p
=
CREAT();
printf("
建立的二叉樹為:
");
for
(i
=
0;
i
<
k;
i++)
{
printf("%c
",
Q[i]
->
data);
}
printf("\n
度為1的節點數為:
");
printf("%d
",
COUNTER(p));
}
這是二叉樹的建立
遍歷
加二叉樹的度為1的結點的演算法
10. 二叉排序演算法的實現
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;
struct BinaryNode
{
char ch;//數據域
BinaryNode *leftChild;//左子節點
BinaryNode *rightChild;//右子節點
BinaryNode(BinaryNode *left=NULL,BinaryNode *right=NULL)
{
rightChild=right;
leftChild=left;
}
BinaryNode(char chz,BinaryNode *left=NULL,BinaryNode *right=NULL)
{
ch=chz;
leftChild=left;
rightChild=right;
}
};
class BinaryTree
{
private:
BinaryNode *root; //根節點
char ref;
void preOrder(BinaryNode *p); //前序遍歷
void levelOrder(BinaryNode *p); //層序遍歷
void CreateTree(BinaryNode *&p); //根據前序遍歷建立二叉樹
void deleteTree(BinaryNode *p); //釋放二叉樹
BinaryNode* CreateBinary(char *VLR,char *LVR,int preStart,int inStart,int n); //根據二叉樹的前序遍歷和中序遍歷建立二叉樹
public:
BinaryTree(){root=NULL;ref='#';} //建立空二叉樹
~BinaryTree(); //析構函數
void preOrder(); //前序遍歷
void levelOrder(); //層序遍歷
void CreateTree(); //根據前序遍歷建立二叉樹
void CreateBinary(char *VLR,char *LVR,int n); //用二叉樹的前序遍歷與後序遍歷建立二叉樹
};
void BinaryTree::deleteTree(BinaryNode *p)
//私有函數,釋放二叉樹
{
if(p!=NULL)
{
deleteTree(p->leftChild);
deleteTree(p->rightChild);
delete p;
}
}
BinaryTree::~BinaryTree() //析構函數
{
deleteTree(root);
}
void BinaryTree::preOrder(BinaryNode *p) //私有函數，前序遍歷
{
if(p!=NULL)
{
cout<<p->ch<<" ";
preOrder(p->leftChild);
preOrder(p->rightChild);
}
}
void BinaryTree::preOrder() //前序遍歷
{
preOrder(root);
}
void BinaryTree::levelOrder(BinaryNode *p) //私有函數，層序遍歷
{
deque<BinaryNode*> level; //利用隊列實現
BinaryNode *q=NULL;
if(p!=NULL)
{
level.push_back(p);
}
while(!level.empty())
{
q=level.front();
cout<<q->ch<<" ";
level.pop_front();
if(q->leftChild!=NULL)
level.push_back(q->leftChild); //左子樹入隊列
if(q->rightChild!=NULL)
level.push_back(q->rightChild); //右子樹入隊列
}
}
void BinaryTree::levelOrder() //層序遍歷
{
levelOrder(root);
}
void BinaryTree::CreateTree(BinaryNode *&p) //引用型參數的的用法*&p
{
char item;
cout<<"請輸入節點值: ";
cin>>item;
if(item!=ref) //結束標記ref
{
p=new BinaryNode(item);
CreateTree(p->leftChild); //遞歸建立左子樹
CreateTree(p->rightChild); //遞歸建立右子樹
}
else
p=NULL;
}
void BinaryTree::CreateTree()
{
CreateTree(root);
}
BinaryNode* BinaryTree::CreateBinary(char* VLR,char* LVR,int preStart,int inStart,int n) //私有函數，利用二叉樹的前序遍歷與中序遍歷建立二叉樹
{
BinaryNode *p=NULL;
if(n>0)
{
char elem=VLR[preStart];
p=new BinaryNode(elem);
int i=0;
while(i<n&&elem!=LVR[inStart+i])
i++;
p->leftChild=CreateBinary(VLR,LVR,preStart+1,inStart,i);
p->rightChild=CreateBinary(VLR,LVR,preStart+i+1,inStart+i+1,n-i-1);
}
return p;
}
void BinaryTree::CreateBinary(char *VLR,char *LVR,int n) //利用二叉樹的前序遍歷與中序遍歷建立二叉樹
{
root=CreateBinary(VLR,LVR,0,0,n);
}
int main()
{
BinaryTree tree;
tree.CreateTree();
cout<<"該二叉樹的前序遍歷為: ";
tree.preOrder();
cout<<endl;
cout<<"該二叉樹的層遍序歷為: ";
tree.levelOrder();
cout<<endl;
return 0;
}